comment implémenter des listes doublement liées

Il n'est pas vraiment pratique d'avoir une liste doublement liée dans Haskell, car vous devez tout construire en même temps.

Par exemple, imaginez que vous avez une liste [1, 2, 3, 4, 5] que vous voulez faire doublement chaînée. Maintenant, imaginons comment la liste est représentée:

data DoubleList a
  = LeftEnd  a (DoubleList a)
  | Middle   a (DoubleList a) (DoubleList a)
  | RightEnd a (DoubleList a)

(j'utilise deux différents constructeurs pour les deux extrémités pour plus de simplicité)

Pour construire la liste ci-dessus, vous devez d'abord construire le premier élément:

let e1 = LeftEnd  1 ...

Mais pour construire le premier élément, vous avez déjà besoin d'avoir le deuxième élément:

let e1 = LeftEnd  1 e2
    e2 = Middle   2 e1 ...

Et pour le deuxième élément, vous avez besoin du troisième, etc:

let e1 = LeftEnd  1 e2
    e2 = Middle   2 e1 e3
    e3 = Middle   3 e2 e4
    e4 = Middle   4 e3 e5
    e5 = RightEnd 5 e4

C'est possible dans Haskell en raison d'une évaluation paresseuse; cette stratégie s'appelle " attacher le noeud "(et vous n'avez pas à littéralement tout mettre en un seul bloc let; vous pouvez diviser la construction en fonctions)

Mais, en d'autres termes, pour faire une liste doublement liée, vous devez tout construire en même temps, et si jamais vous voulez en changer une partie, vous devez soit pour utiliser une fermeture à glissière ou simplement en faire une copie complète à chaque fois.

Je recommande d'utiliser à la place Data.Sequence, qui est une implémentation de stockage séquentiel basée sur l'arbre des doigts optimisée. Il prend en charge l'insertion, la suppression et l'itération très rapides tout en étant une structure de données purement fonctionnelle.

Sinon, vous voudrez peut-être simplement utiliser des fermetures à glissière, mais les utiliser pour les arbres au lieu de pour les listes. Plus d'informations sur les fermetures à glissière peuvent être trouvées sur le Haskell Wiki. Les fermetures à glissière s'adapteraient très bien dans cette situation, car elles offrent la fonctionnalité exacte que vous recherchez: si vous visitez un arbre avec une fermeture à glissière, vous accédez aux "parents" de la partie de l'arbre que vous visitez, mais l'arbre lui-même n'a pas à contenir les références parentes.