Discussion :

[anissben]

bonjour,
voila ,
je suis débutant en caml et je dois résoudre se problème
mon pb: retourner le maximum dans une liste
jusqu'ici , voici mon code ::

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let max2 x y = if x>y then x else y ;;

let rec max_list l= match l with 
[] -> ??????
|x::reste -> max2 x (max_list reste) ;;

je compare deux a deux et a la fin j'ai le maximum mais quoi mettre dans ????? et est-ce le bon code pour ce pb, mrc pour vos réponses...

[anissben]

c'est bon j'ai trouver , pour ceux qui la voudraient :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let max2 x y = if x>y then x else y;;
 
let rec max_list l = match l with 
[] -> 0 
|x::reste -> max2 x (max_list reste) ;;

merci quand même pour ceux qui ont essayer

[alex_pi]

teste ta fonction sur la liste [-1; -2] pour voir ?

[Jedai]

Essayer d'attribuer un maximum à une liste vide n'a pas de sens, excepté peut-être si tu peux représenter moins l'infini dans ton système de numération, et encore... A priori, une fonction maximum devrait juste échouer (avec une exception) dans ce cas, pas renvoyer un mensonge comme 0.

En Haskell :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

maximum = foldl1' max

Sachant que foldl1' est une version stricte de foldl1 qui lui-même est un foldl restreint aux listes non-vides :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
foldl1 :: (a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
foldl1 _ []     = undefined

Rappelons que foldl est l'équivalent de fold_left en OCaml :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
foldl :: (a -> b) -> a -> [b] -> a
foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

--
Jedaï

[alex_pi]

@Jedai: confronté à quelqu'un débutant *clairement* dans le domaine de l'algorithmique et de la programmation en général, et en tout cas dans celui de la programmation fonctionnelle, je ne suis vraiment pas sûr que lui balancer une syntaxe différente, autant pour les termes que pour les types, soit un choix pédagogiquement intéressant... :-\

[Jedai]

La syntaxe n'est pas très différente néanmoins ? Ok, en OCaml, ça donnerait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
let max x y = if x < y then y else x
let maximum = function
  | x :: xs -> List.fold_left max x xs
  | [] -> failwith "maximum of an empty list !\n"

Mais bon, c'est pratiquement la même chose.

--
Jedaï

[SpiceGuid]

Une solution casuistique (qui préserve la structure de monoïde) :

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

let list_max l = List.fold_right max l

[alex_pi]

Une solution casuistique (qui préserve la structure de monoïde) :

Code OCaml :

Sélectionner tout - Visualiser dans une fenêtre à part

let list_max l = List.fold_right max l

Euh, c'est quoi l'intérêt de prendre le fold non tail_rec ?

[Jedai]

Euh, c'est quoi l'intérêt de prendre le fold non tail_rec ?

En Haskell ça pourrait avoir un intérêt si max n'était pas strict en son second argument, par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
max True _ = True
max False b = b

(max == (||) dans ce cas, mais on peut imaginer plus complexe)

Dans ce cas, le fold_right peut conclure plus vite (et il n'y aura aucun risque de stack overflow). C'est pour ça que la définition de or est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
or :: [Bool] -> Bool
or = foldr (||) False

Evidemment, pour un langage strict comme OCaml, le choix de fold_right laisse songeur...

--
Jedaï