[Ocaml] Explication de List.fold left et right

Bonjour,
Le titre est explicite, j'aimerai avoir une explication sur ces deux fonctions avec si possible un ou deux exemples à chaque fois.
J'ai cherché sur le net mais la pluspart du temps les explications sont en anglais.
Merci pour votre aide.
Dark3

Code:

---

1 2 3

let rec fold_left f a = function | [] -> a | h::t -> fold_left f (f a h) t

---

Autrement dit : fold_left f a [x1; x2;...; xn] = f (... (f (f a x1) x2)...) xn
Peut-être optimisé par une tail recursion

Code:

---

1 2 3

let rec fold_right f b = function | [] -> b | h::t -> f h (fold_right f b t)

---

Autrement it : fold_right f b [x1; x2;...; xn] = f x1 ( f x2 (... ( f b xn)))))))
Ne peut pas être optimisé avec une tail recursion

Code:

---

let sum = fold_left (+) 0

---

NB : Avec un opérateur infixe en paramètre, fold_left et fold_right peuvent être plus facile à comprendre.
fold_left (+) a [x1; x2;...; xn] = a + x1 + x2...+ xn
(si l'opérateur est associatif à gauche)

fold_right (+) b [x1; x2;...; xn] = x1 + (x2 + (... (xn + b)))))))

--
Jedaï

Merci pour cette réponse ultra rapide.
La chose qui me pose problème c'est l'élément que l'on doit mettre en paramètre dans les deux cas à part la fonction et la liste.
J'ai cru comprendre qu'il sagissait peut-être d'un élément neutre ?
Dark3

Il n'y a aucune contrainte sur cet élément, il s'agit simplement de la "graîne" du fold, autrement dit l'élément initial.
Par contre il est vrai que lorsque l'on désire simplement employer les fold pour appliquer un opérateur entre les éléments de sa liste (comme pour faire la somme des éléments), cet élément initial doit être un élément neutre de l'opérateur (à droite pour fold_right, à gauche pour fold_left) de façon à obtenir le résultat souhaité.

--
Jedaï

Bonjour, j'ai un peu mieux compris cette fonction, je l'ai utilisé en parallele avec mon aute post, c'est à dire enlever les doublons d'une liste, et ca donne ça :

Code:

---

let fonction1 l = List.fold_left (fun lu x-> if List.mem x lu then lu else x::lu) [] l;;

---

Par contre je n'ai pas encore réussi à le faire avec fold_right.
Dark3

edit : je rajoute la version fold_right (je cherchais pas depuis tout à l'heure)

Code:

---

let fonction2 l = List.fold_right (fun x lu-> if List.mem x lu then lu else x::lu) l [];;

---

Citation:

---

Envoyé par Dark3

Bonjour, j'ai un peu mieux compris cette fonction, je l'ai utilisé en parallele avec mon aute post, c'est à dire enlever les doublons d'une liste, et ca donne ça :

Code:

---

let fonction1 l = List.fold_left (fun lu x-> if List.mem x lu then lu else x::lu) [] l;;

---

Par contre je n'ai pas encore réussi à le faire avec fold_right.
Dark3

---

Oui, c'est une bonne façon d'écrire une élimination de doublon, d'autant qu'avec fold_left, tu as une récursion terminale (tail recursion), contrairement à ta fonction précédente.

--
Jedaï

Voici un exemple dans lequel la valeur initiale n'est pas un élément neutre:

Code:

---

let list_max l = List.fold_left (fun a b -> if b > a then b else a) (List.hd l) l

---

En fait cela correspond à l'element initial par rapport à la fonction passé en argument à fold_left, ou ce n'est pas ça ?
Dark3

Citation:

---

Envoyé par Jedai

Il n'y a aucune contrainte sur cet élément, il s'agit simplement de la "graîne" du fold, autrement dit l'élément initial.

---

Oui.

--
Jedaï