Re: Intéressant, mais Haskell

Oh, ce n'est pas vraiment spécifique à Haskell ça. En fait, tu as un type récursif :

data Tree a = Node [(a,Tree a)]

Or traiter un type récursif c'est pas toujours facile. Du coup tu généralise, en regardant son homologue non récursif :

data Tree' a b = Node' [(a,b)]

On remarque que le deuxième est un type « normal », c'est à dire non récursif. Tu peux ensuite (formellement) écrire

Tree a <=> Tree' a (Tree a)

Car on remplace b par Tree a et on a des structures identiques (au nom du constructeur près).

Pour simplifier, on peut prendre le type liste :

data Liste a = Cons a (Liste a) | Vide

Sa contrepartie non-récursive est

data Paire a b = Cons' a b | Vide

Et on remarque bien que : Liste a <=> Paire a (Liste a).
Mieux tu peux définir le type récursif comme étant le type T a tel que Paire a (T a) = T a. Ce qui se comprend comme : une liste c'est un type tel que si je le met dans une paire, c'est encore une liste.

Quel intérêt ? Et bien, cela donne automatiquement une manière de « faire pousser » la structure. Pour nous c'était un arbre, pour la liste c'est pareil, il existe une fonction unfold qui permet de le faire.

Par exemple, on déduit la signature de unfold pour les listes :

Paire a b = Cons' a b | Vide
Liste a <=> Fixe (Paire a)
unfoldFinal :: b -> Liste a -- Ce que l'on veut 
f :: (b -> Paire a b) -- Ce que l'on sait faire 
unfold :: (b -> Paire a b) -> b -> Liste a

Mieux, tu as aussi l'inverse (ie : partir d'une liste et arriver à une valeur).

foldFinal :: Liste a -> b -- Ce que l'on veut 
f :: Paire a b -> b -- Ce que l'on sait faire 
fold :: (Paire a b -> b) -> Liste a -> b
-- Exemple d'utilisation quand a = b = Nombre 
somme :: [Nombre] -> Nombre -- Ce que l'on veut 
add :: Paire Nombre Nombre -> Nombre -- Ce que l'on sait faire 
add Vide = 0
add (Cons' x y) = x + y
somme liste = fold add list

Il faudrait que je retrouve un article qui en parlait de manière plus générale. En tout cas la page wikipédia anglaise est assez bien faite.