Pourquoi les listes sont-elles la structure de données de choix dans les langages fonctionnels?

La plupart des langages fonctionnels utilisent des listes chaînées comme structure de données immuable principale. Pourquoi des listes, et pas par exemple des arbres? Les arbres peuvent également réutiliser des chemins et même des listes de modèles.

functional-programming Filip Haglund
la source

Duplication possible de Pourquoi les listes négatives sont-elles associées à la programmation fonctionnelle?

moucher le

@gnat - c'est pas un double de cette question. La réponse correcte et acceptée à cette question est essentiellement "parce qu'une liste chaînée immuable permet le partage des queues entre les listes mise à jour et originale", une réponse qui est soulignée dans le contexte de cette question ...

Jules

Un point de clarification est qu'une "liste" (le concept de programmation abstraite) est distincte d'une "liste chaînée" (une implémentation particulière de ce concept), tout comme la spécification d'un langage de programmation est distincte de son implémentation. La question "Pourquoi les langages fonctionnels utilisent-ils des listes (le concept de programmation abstraite) comme structure de données principale?" est subtilement mais fondamentalement très différente de la question "pourquoi les implémentations courantes des langages fonctionnels X, Y et Z utilisent-elles des listes chaînées comme structure de données principale?"

RM le

I scala Vector (qui est implémenté sous la forme d'un arbre) est légèrement préférable à la liste stackoverflow.com/questions/6928327/… Dans la pratique, la plupart des gens utilisent encore les listes (d'après ce que j'ai vu).

Akavall

J'ai suivi des cours de programmation fonctionnelle à Scala et utilisé BEAUCOUP d'arbres. C'est juste que la liste est plus simple pour des exemples. Les arbres sont utilisés pour des problèmes de performances. Vous pouvez créer des arborescences innommables en réutilisant une partie d'anciennes arborescences tout en ajoutant des éléments à des listes inaltérables.

Borjab

Réponses:

Parce que les listes sont plus simples que les arbres. (Vous pouvez le voir de manière triviale par le fait qu’une liste est un arbre dégénéré, chaque nœud n’ayant qu’un seul enfant.)

La liste des inconvénients est la structure de données récursive la plus simple possible de taille arbitraire.

Lors de la conception du langage de programmation Fortress, Guy Steele a expliqué que, pour les calculs extrêmement parallèles du futur, nos structures de données et notre flux de contrôle devraient être en forme d'arborescence à multiples branches, et non linéaires à l'heure actuelle. Mais pour le moment, la plupart de nos principales bibliothèques de structures de données ont été conçues avec un traitement séquentiel et itératif (ou une récursion finale, peu importe, elles sont identiques), pas un traitement parallèle.

Notez que, par exemple, dans Clojure, dont les structures de données ont été spécialement conçues pour le monde parallèle, "nuageux" et distribué, même des tableaux (appelés "vecteur dans Clojure), probablement la structure de données la plus" linéaire "de tous, sont en réalité mis en oeuvre des arbres.

En résumé, une liste est la structure de données récursive persistante la plus simple possible et il n’était pas nécessaire de choisir un "défaut" plus compliqué. D'autres sont bien sûr disponibles en option, par exemple Haskell a des tableaux, des files d'attente prioritaires, des cartes, des tas, des balises, des tentatives et tout ce que vous pouvez imaginer, mais la valeur par défaut est la simple liste des inconvénients.

Jörg W Mittag
la source

Oui, les vecteurs Clojure sont implémentés en tant qu'arbres, mais il convient de noter qu'il s'agit d'essais mappés sur des tableaux de hachage , et non de vos fichiers binaires standard data Tree a = Leaf a | Branch a (Tree a) (Tree a). Cela renforce votre argument "simplicité".

wchargin

Les vecteurs persistants de FWIW Clojure sont implémentés sous forme d'arborescence (comme l'indique @wchargin un peu complexe) pour un accès rapide (logarithmique avec une base importante) et la mise à jour d'éléments arbitraires, et non pour un fonctionnement parallèle en tant que tel (la partie immuable s'en occupe degré). Les autres langages de PF font le même choix (parfois avec différents types d’arbres) quand ils veulent les deux (par exemple ceux de Haskell Sequenceou de Scala Vector), mais n’utilisez pas les arbres quand ils ont seulement besoin de les lire car ils peuvent y parvenir en temps réel (par exemple Haskell's Vectorou F # via .Net ImmutableArray)

badcook

Par exemple, un pmapping sur un vecteur dans Clojure accède toujours à chaque élément de manière séquentielle; la structure arborescente du vecteur est généralement masquée pour l'utilisateur final.

Badcook

En fait, ces listes sont des arbres! Vous avez des noeuds avec deux champs, caret cdr, qui peuvent contenir plus de tels noeuds ou feuilles. La seule chose qui transforme ces arbres en listes est la convention selon laquelle le lien est interprétécdr comme un lien vers le nœud suivant dans une liste linéaire et le carlien comme la valeur du nœud actuel.

Cela dit, je suppose que la prévalence des listes chaînées dans la programmation fonctionnelle est liée à la prévalence de la récursion sur l'itération. Lorsque votre seule construction en boucle est la récursion, vous voulez des structures de données faciles à utiliser avec cela; et les listes chaînées sont parfaites pour cela.

cmaster
la source

cela dépend de la langue. Bien sûr, vous pouvez implémenter une arborescence dans LISP-like en utilisant des cellules contra, mais dans Haskell, par exemple, vous aurez besoin d’une structure entièrement distincte. Notez également que la plupart des langages fonctionnels ont beaucoup plus de constructions en boucle que la récursion de la queue. Les bibliothèques de base de Haskell, par exemple, fournissent des plis (à gauche et à droite), des analyses, des parcours sur des arbres, des itérations sur des clés et des valeurs de cartes, ainsi que de nombreuses autres structures plus spécialisées. Bien sûr, ils sont implémentés avec une récursivité en arrière-plan, mais l'utilisateur n'a même pas besoin d'y penser pour le faire fonctionner.

Jules

@Jules Néanmoins, la programmation fonctionnelle a été développée et fortement influencée par des langages tels que LISP. Évidemment, il est possible de rendre toute cette liste-itération plus efficace en utilisant des tableaux sous le capot, ou d’ajouter du sucre syntaxique qui cache la nature d’une liste, mais la programmation fonctionnelle pure peut faire et ne pas en faire. En outre, Haskell est une langue assez récente (32 ans de moins que LISP), qui ajoute de nombreuses autres idées, du sucre syntaxique, etc. au style purement fonctionnel. Je pense, à en juger la programmation fonctionnelle en jugeant Haskell est un peu comme juger des mélangeurs en jugeant thermomix ...

cmaster

@cmaster bien qu'Haskell soit plus jeune, il a encore 27 ans et a influencé de nombreuses langues (notamment Python, Java et C #, pour ne nommer que peu d'influence). Juger la programmation fonctionnelle par LISP équivaut à juger la programmation impérative par ALGOL - les deux ont parcouru un long chemin depuis pour devenir méconnaissables. D'ACCORD. Lisp est sans doute toujours d'actualité, mais je ne le considérerais pas comme un courant dominant et passe à côté de beaucoup d'informations plus tardives, notamment de types ML.

Maciej Piechotka

Vous ne pouvez pas traiter les arbres liés individuellement de manière récursive ou itérative sans une pile explicite si vous souhaitez toucher à tout l’arbre. Je ne pense donc pas que la récursion de la queue y soit pour quelque chose.

k_g

@MaciejPiechotka Ni Python, Java, ni C # ne peuvent être considérés comme des langages fonctionnels, ils sont impératifs et ajoutent quelques fonctionnalités inspirées par la programmation fonctionnelle. Une fois que vous avez changé d'état, vous êtes fermement dans le domaine de la programmation impérative, non fonctionnelle. Je suis d'accord avec vous, cependant, que LISP n'est certainement pas un courant dominant.

cmaster