l'usage en ocaml est de nommer le reduce "fold", et pas votre catamorphisme
Et c'est ce que fait notre fonction fold : un reduce via la fonction g. Ce qu'il y a c'est que dans une liste, ou une collection séquentielle ou linéarisée, on peut attaquer la structure par deux bouts : le début ou la fin, d'où le fold_left et le fold_right.
Dans le cas des arbres binaires, on attaque nécessaire par la racine puis on descend dans les branches pour finir sur les bouts de la structure que sont les feuilles où l'on applique la fonction f, puis l'on réduit la structure via la fonction g. C'est bien une généralisation du cas sur les listes dont le nom technique général est catamorphisme. Voilà une série d'articles en F# sur le sujet, le premier commence par les listes :
La différence est seulement dans le fait que l'on ne réduit pas une liste et un arbre de la même façon.
P.S : tu as raison pour le code du fold_list : si elle est vide on renvoie une exception (ou None si on veut renvoyer un type 'a option) ou alors on passe par des listes qui ne peuvent être vides comme type 'a coll = End of 'a | Cons of 'a * 'a coll — les arbres étant garantis d'être non vides par construction.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
[^] # Re: Exemple judicieux ?
Posté par kantien . En réponse à la dépêche Apprendre la programmation fonctionnelle avec le MOOC OCaml. Évalué à 1.
Et c'est ce que fait notre fonction
fold: un reduce via la fonctiong. Ce qu'il y a c'est que dans une liste, ou une collection séquentielle ou linéarisée, on peut attaquer la structure par deux bouts : le début ou la fin, d'où lefold_leftet lefold_right.Dans le cas des arbres binaires, on attaque nécessaire par la racine puis on descend dans les branches pour finir sur les bouts de la structure que sont les feuilles où l'on applique la fonction
f, puis l'on réduit la structure via la fonctiong. C'est bien une généralisation du cas sur les listes dont le nom technique général est catamorphisme. Voilà une série d'articles en F# sur le sujet, le premier commence par les listes :La différence est seulement dans le fait que l'on ne réduit pas une liste et un arbre de la même façon.
P.S : tu as raison pour le code du
fold_list: si elle est vide on renvoie une exception (ouNonesi on veut renvoyer un type'a option) ou alors on passe par des listes qui ne peuvent être vides commetype 'a coll = End of 'a | Cons of 'a * 'a coll— les arbres étant garantis d'être non vides par construction.Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.