Re: Intéressant, mais Haskell

En fait, c'est pour construire la fonction : raisonner directement sur le type récursif est moins évident que d'utiliser sa contrepartie qui ne l'est pas. On peut plus facilement trouver les idées qui vont mener au code : ici pour savoir « comment faire pousser un arbre ». On peut le faire sans, mais à mon avis l'enchaînement logique est beaucoup plus simple (ça coule tout seul) quand on regarde la version non récursive.

D'ailleurs, en haskell, on utilise souvent pour les listes les fonctions fold, unfold, filter, map. Or les deux dernières se codent à partir d'un fold facilement, donc on les enlève. Maintenant, regardons le type de fold et unfold, que font ces fonctions ?

• fold :: (b -> a -> b) -> b -> [a] -> b
• unfold :: (b -> Maybe (a,b)) -> b -> [a]

Elles permettent toute deux de prendre une fonction « simple » (qui travaille sur les types a et b directement) et d'en faire une fonction « compliquée » sur une liste. Mais ... Cette fonction simple, sur quoi est-elle en train de travailler plus précisément ?

1. Maybe (a,b) <=> Paire a b = Cons a b | Nil .... Précisément la « contrepartie non-récursive » de la liste
2. (b -> a -> b) <=> (a,b) -> b : ici il nous manque un Maybe, tout simplement parce qu'il vient de l'autre argument ! (b -> a -> b) -> b pour la définition de fold est équivalent à Maybe (a,b) -> b.

Regardons maintenant ce que cela donne :

1. fold :: (Paire a b -> b) -> [a] -> b
2. unfold :: (b -> Paire a b) -> b -> [a]

De manière systématique, on peut prendre des fonctions simples qui « réduisent » des paires, pour réduire des listes. De manière identique, on peut prendre des fonctions qui construisent des paires, pour construire des listes. On a bien réduit le problème à une chose « plus simple ».

Il est toutefois vrai que c'est exagéré de dire qu'un type récursif, c'est compliqué. Il n'y pas bien grande différence entre foldr (+) 0 et sum [] = 0 ; sum (x:xs) = x + sum xs.

J'espère avoir répondu à ta question :-).