Discussion :

[Dark3]

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

[Jedai]

Code :

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

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 :

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

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 :

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

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ï

[Dark3]

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

[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.
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ï

[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 :

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

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 :

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

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

[Jedai]

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 :

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

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ï

[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ï