Pourquoi les contre-listes sont-elles associées à la programmation fonctionnelle?

22

J'ai remarqué que la plupart des langages fonctionnels utilisent une liste à liaison unique (une liste "contre") comme types de liste les plus fondamentaux. Les exemples incluent Common Lisp, Haskell et F #. Ceci est différent des langages traditionnels, où les types de liste natifs sont des tableaux.

Pourquoi donc?

Pour Common Lisp (étant typé dynamiquement), j'ai l'idée que les inconvénients sont suffisamment généraux pour être également la base de listes, d'arbres, etc. Cela pourrait être une toute petite raison.

Pour les langages typés statiquement, cependant, je ne trouve pas de bon raisonnement, je peux même trouver des contre-arguments:

  • Le style fonctionnel encourage l'immuabilité, la facilité d'insertion de la liste chaînée est donc moins avantageuse,
  • Le style fonctionnel encourage l'immuabilité, ainsi que le partage de données; un tableau est plus facile à partager "partiellement" qu'une liste chaînée,
  • Vous pouvez aussi bien faire correspondre des motifs sur un tableau régulier, et encore mieux (vous pouvez facilement vous plier de droite à gauche par exemple),
  • En plus de cela, vous obtenez un accès aléatoire gratuit,
  • Et (un avantage pratique) si la langue est typée statiquement, vous pouvez utiliser une disposition de mémoire régulière et obtenir une augmentation de la vitesse du cache.

Alors pourquoi préférer les listes chaînées?

programming-languages functional-programming list linked-list Kos
la source
4
Venant des commentaires sur la réponse de @ sepp2k, je pense qu'il an array is easier to share "partially" than a linked listfaut clarifier ce que vous voulez dire. En raison de leur nature récursive, l'inverse est vrai si je comprends bien - vous pouvez partager partiellement une liste liée plus facilement en passant le long de n'importe quel nœud, tandis qu'un tableau aurait besoin de passer du temps à faire une nouvelle copie. Ou en termes de partage de données, deux listes liées peuvent pointer vers le même suffixe, ce qui n'est tout simplement pas possible avec les tableaux.
Izkata
Si un tableau se définit comme un décalage, une longueur, un tampon triple, vous pouvez partager un tableau en en créant un nouveau avec un décalage + 1, longueur 1, un tampon. Ou avoir un type spécial de tableau comme sous-tableau.
Dobes Vandermeer
@Izkata Lorsque nous parlons de tableaux, nous entendons rarement un tampon tel qu'un pointeur vers le début de la mémoire contiguë en C. Nous entendons généralement une sorte de structure qui stocke la longueur et un pointeur vers le début d'un tampon encapsulé. Dans un tel système, une opération de découpage peut renvoyer un sous-tableau, dont le pointeur de tampon pointe à mi-chemin dans le tampon (au premier élément du sous-tableau), et dont le nombre est tel que start + count vous donne le dernier élément. De telles opérations de découpage sont O (1) dans le temps et l'espace
Alexander - Reinstate Monica

Réponses:

22

Le facteur le plus important est que vous pouvez ajouter à une liste immuable liée individuellement en temps O (1), ce qui vous permet de créer de manière récursive des listes de n éléments en temps O (n) comme ceci:

// Build a list containing the numbers 1 to n:
foo(0) = []
foo(n) = cons(n, foo(n-1))

Si vous faisiez cela en utilisant des tableaux immuables, le temps d'exécution serait quadratique car chaque consopération aurait besoin de copier le tableau entier, ce qui conduirait à un temps d'exécution quadratique.

Le style fonctionnel encourage l'immuabilité, ainsi que le partage de données; un tableau est plus facile à partager "partiellement" qu'une liste chaînée

Je suppose qu'en partageant "partiellement", vous voulez dire que vous pouvez prendre un sous-tableau d'un tableau en temps O (1), alors qu'avec les listes liées, vous ne pouvez prendre la queue qu'en O (1) et tout le reste a besoin de O (n). C'est vrai.

Cependant, prendre la queue suffit dans de nombreux cas. Et vous devez tenir compte du fait que pouvoir créer des sous-réseaux à bas prix ne vous aide pas si vous n'avez aucun moyen de créer des tableaux à moindre coût. Et (sans optimisations intelligentes du compilateur), il n'y a aucun moyen de construire pas à pas un tableau pas à pas.

sepp2k
la source
Ce n'est pas vrai du tout. Vous pouvez ajouter des tableaux en O amorti (1).
DeadMG
10
@DeadMG Oui, mais pas aux tableaux immuables .
sepp2k
"partage partiel" - je pense que les deux listes de contre peuvent pointer vers la même liste de suffixes (je ne sais pas pourquoi vous voulez cela), et que vous pouvez passer un point médian au lieu du début de la liste à une autre fonction sans avoir à copier (je l'ai fait plusieurs fois)
Izkata
@Izkata L'OP parlait cependant de partager partiellement des tableaux, pas de listes. De plus, je n'ai jamais entendu ce que vous décrivez comme un partage partiel . C'est juste du partage.
sepp2k
1
@Izkata L'OP utilise le terme "tableau" exactement trois fois. Une fois pour dire que les langages FP utilisent des listes chaînées où d'autres langages utilisent des tableaux. Une fois pour dire que les tableaux sont meilleurs pour le partage partiel que les listes liées et une fois pour dire que les tableaux peuvent également être mis en correspondance avec des modèles (comme les listes liées). Dans tous les cas, il contraste des tableaux et des listes liées (pour faire valoir que les tableaux seraient plus utiles en tant que structure de données principale que les listes liées, ce qui conduit à sa question de savoir pourquoi les listes liées sont préférées dans FP), donc je ne vois pas comment il pourrait utiliser les termes de manière interchangeable.
sepp2k
4

Je pense que cela revient à des listes qui sont assez facilement implémentées dans du code fonctionnel.

Schème:

(define (cons x y)(lambda (m) (m x y)))

Haskell:

data  [a]  =  [] | a : [a]

Les tableaux sont plus difficiles et pas aussi jolis à mettre en œuvre. Si vous voulez qu'ils soient extrêmement rapides, ils devront être écrits en bas niveau.

De plus, la récursivité fonctionne beaucoup mieux sur les listes que sur les tableaux. Considérez le nombre de fois où vous avez consommé / généré récursivement une liste vs indexé un tableau.

Pubby
la source
Je ne dirais pas qu'il est exact d'appeler la version de votre schéma une implémentation de listes chaînées. Vous ne pourrez pas l'utiliser pour stocker autre chose que des fonctions. De plus, les tableaux sont plus difficiles (en fait, impossibles) à implémenter dans n'importe quel langage qui ne les prend pas en charge (ou morceaux de mémoire), tandis que les listes liées nécessitent seulement quelque chose comme des structures, des classes, des enregistrements ou des types de données algébriques à implémenter. Ce n'est pas spécifique aux langages de programmation fonctionnels.
sepp2k
@ sepp2k Que voulez-vous dire par "stocker autre chose que des fonctions" ?
Pubby
1
Ce que je voulais dire, c'est que les listes définies de cette façon ne peuvent pas stocker tout ce qui n'est pas une fonction. Ce n'est pas vraiment vrai cependant. Je ne sais pas pourquoi j'ai pensé ça. Désolé pour ça.
sepp2k
2

Une liste à liaison unique est la structure de données persistante la plus simple .

Les structures de données persistantes sont essentielles pour une programmation performante et purement fonctionnelle.

ziggystar
la source
1
cela semble simplement répéter le point soulevé et expliqué dans la réponse la plus haute qui a été publiée il y a plus de 4 ans
gnat
3
@gnat: La première réponse ne mentionne pas les structures de données persistantes, ou que les listes liées individuellement sont la structure de données persistante la plus simple, ou qu'elles sont essentielles pour une programmation performante purement fonctionnelle. Je ne trouve aucun chevauchement avec la réponse du haut.
Michael Shaw
2

Vous pouvez utiliser facilement les nœuds Cons uniquement si vous disposez d'une langue récupérée.

Les nœuds correspondent beaucoup au style de programmation fonctionnel des appels récursifs et des valeurs immuables. Il s'intègre donc bien dans le modèle du programmeur mental.

Et n'oubliez pas les raisons historiques. Pourquoi sont-ils encore appelés Cons Nodes et pire encore utilisent-ils la voiture et le cdr comme accessoires? Les gens l'apprennent à partir de manuels et de cours, puis l'utilisent.

Vous avez raison, dans le monde réel, les tableaux sont beaucoup plus faciles à utiliser, ne consomment que la moitié de l'espace mémoire et sont beaucoup plus performants en raison des échecs de niveau de cache. Il n'y a aucune raison de les utiliser avec des langages impératifs.

Lothar
la source
1

Les listes liées sont importantes pour la raison suivante:

Une fois que vous avez pris un nombre comme 3, que vous l'avez converti en séquence successive comme succ(succ(succ(zero))), puis que vous y avez utilisé la substitution avec {succ=List node with some memory space}, et {zero = end of list}, vous vous retrouverez avec une liste chaînée (de longueur 3).

La partie importante réelle est les nombres, la substitution et l'espace mémoire et zéro.

tp1
la source