Pour revenir sur le sujet du fold (avant de parler de ce que j'ai voulu dire en parlant d'ordre) voilà pourquoi il est naturel de dire que la fonction proposée dans le journal est un fold. Alors, pour cela il faut savoir ce qu'on entend par fold. C'est là que la divergence d'opinion provient : tu veux que ce soit une fonction qui ait une signature plus ou moins proche de celle sur des collections de même nature que les listes (tableaux, etc ...), tandis qu'on peut interpréter cette signature comme une spécification d'un concept plus général.
Très rapidement, je vais expliquer d'où provient cette spécialisation. Passer ce paragraphe si c'est déjà connu.
Je vais généraliser d'une manière grossière (on peut faire mieux) mais les types en ocaml (somme et produits) permettent de construire une algèbre de termes. La construction est très simple, c'est construire le type des arbres avec pour noeuds les constructeurs (et le nombre de fils correspondants à constructeur). Cette construction généralise clairement celle des listes.
Si on se demande maintenant d'où vient le fold, on comprend que c'est une fonction d'évaluation sur les listes, qui part d'une graine et qui accumule un résultat. Une manière totalement générale de faire ceci sur des termes arbitraires c'est de mettre des graines sur les feuilles, et faire remonter les valeurs en les combinant en fonction des noeuds.
Comme pour la liste les noeuds sont toujours de type concaténation, il suffit de donner une unique fonction de combinaison de valeurs, et comme il y a une seule fin de liste (la liste vide) il suffit de donner une valeur comme graine.
Il y a donc de très bonnes raisons pour dire que ces deux choses sont similaires, au point qu'on puisse les nommer de manière identique (comme une grosse fonction fold polymorphique qui déciderait en fonction de la structure comment agir).
Pour revenir sur la notion d'ordre, c'était simplement pour dire que si tu veux utiliser la « vraie » fonction fold, elle ne peut faire des combinaisons que locales, et accumuler un résultat. Pour un arbre, il est possible d'écrire les noeuds dans une liste (par exemple avec un parcours), mais appliquer un fold séquentiel dessus semble très étrange (vu qu'il ne respectera presque aucune propriété) sauf si on sait que l'opérateur vérifie des hypothèses très fortes. Je voulais simplement dire que pour un arbre, l'opération « importante » c'est de faire des branchements, et donc proposer une fonction « linéaire » de réduction c'est très souvent impossible.
[^] # Re: Exemple judicieux ?
Posté par Aluminium95 . En réponse à la dépêche Apprendre la programmation fonctionnelle avec le MOOC OCaml. Évalué à 2.
En effet je n'ai pas été très clair.
Pour revenir sur le sujet du fold (avant de parler de ce que j'ai voulu dire en parlant d'ordre) voilà pourquoi il est naturel de dire que la fonction proposée dans le journal est un fold. Alors, pour cela il faut savoir ce qu'on entend par fold. C'est là que la divergence d'opinion provient : tu veux que ce soit une fonction qui ait une signature plus ou moins proche de celle sur des collections de même nature que les listes (tableaux, etc ...), tandis qu'on peut interpréter cette signature comme une spécification d'un concept plus général.
Très rapidement, je vais expliquer d'où provient cette spécialisation. Passer ce paragraphe si c'est déjà connu.
Je vais généraliser d'une manière grossière (on peut faire mieux) mais les types en ocaml (somme et produits) permettent de construire une algèbre de termes. La construction est très simple, c'est construire le type des arbres avec pour noeuds les constructeurs (et le nombre de fils correspondants à constructeur). Cette construction généralise clairement celle des listes.
Si on se demande maintenant d'où vient le fold, on comprend que c'est une fonction d'évaluation sur les listes, qui part d'une graine et qui accumule un résultat. Une manière totalement générale de faire ceci sur des termes arbitraires c'est de mettre des graines sur les feuilles, et faire remonter les valeurs en les combinant en fonction des noeuds.
Comme pour la liste les noeuds sont toujours de type
concaténation, il suffit de donner une unique fonction de combinaison de valeurs, et comme il y a une seule fin de liste (la liste vide) il suffit de donner une valeur comme graine.Il y a donc de très bonnes raisons pour dire que ces deux choses sont similaires, au point qu'on puisse les nommer de manière identique (comme une grosse fonction
foldpolymorphique qui déciderait en fonction de la structure comment agir).Pour revenir sur la notion d'ordre, c'était simplement pour dire que si tu veux utiliser la « vraie » fonction fold, elle ne peut faire des combinaisons que locales, et accumuler un résultat. Pour un arbre, il est possible d'écrire les noeuds dans une liste (par exemple avec un parcours), mais appliquer un fold séquentiel dessus semble très étrange (vu qu'il ne respectera presque aucune propriété) sauf si on sait que l'opérateur vérifie des hypothèses très fortes. Je voulais simplement dire que pour un arbre, l'opération « importante » c'est de faire des branchements, et donc proposer une fonction « linéaire » de réduction c'est très souvent impossible.