Re: Intéressant, mais Haskell

Les types récursifs, en C on le fait avec des pointeurs

Je crois comprendre la difficulté alors. Le fait est que en C tu penses à la construction effective du type, alors que là c'est purement théorique. On peut même l'écrire « mathématiquement » de manière indépendante du langage sous-jacent : un type est un ensemble de valeurs, et un type paramétré est une fonction qui prend en argument des types pour en construire un autre.

Quand tu parles de pointeurs, tu rentres déjà dans le détail de la réalisation. C'est le constructeur ! Par exemple, quand on écrit :

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

On dit au compilateur : quelque soit le type a que tu me donnes, je peux construire un nouveau type Tree a, et pour le construire j'utilise la fonction Node, à laquelle je donne une liste de couples de type (a, Tree a). La définition est récursive, car pour construire un élément de type Tree a, je peux avoir besoin d'en construire un de type Tree a ... Mais en pratique, la construction se fait « à la main » de manière très simple :

vide :: Tree a -- ici le type a est quelconque, vide est un élément « commun à tous les types d'arbres »
vide = Node [] -- C'est bien un arbre valide, selon la construction donnée 
simple :: Tree Int -- ici on spécifie le type 
simple = Node [(8, vide)] -- C'est bien un arbre, car vide est un arbre !

Au final, ce sont effectivement des pointeurs : la structure Node contient un pointeur vers une liste, qui est elle même simplement chaînée par des pointeurs. Les valeurs de la listes sont des pointeurs vers des couples de pointeurs ... etc. Mais cette considération est « inutile » au niveau où on travaille.