¿Por qué se enumeran la estructura de datos de elección en lenguajes funcionales?

45

La mayoría de los lenguajes funcionales utilizan listas vinculadas como su estructura de datos inmutable principal. ¿Por qué listas, y no, por ejemplo, árboles? Los árboles también pueden reutilizar rutas e incluso listas de modelos.

functional-programming Filip Haglund
fuente
Posible duplicado de ¿Por qué las listas de contras están asociadas con la programación funcional?
mosquito
10
@gnat: este no es un duplicado de esa pregunta. La respuesta correcta y aceptada a esa pregunta es esencialmente "porque una lista enlazada inmutable permite compartir colas entre listas actualizadas y originales", una respuesta que se señala como parte de los antecedentes de esta pregunta ...
Jules
99
Un punto de aclaración es que una "lista" (el concepto de programación abstracta) es distinta de una "lista vinculada" (una implementación particular de ese concepto), al igual que la especificación de un lenguaje de programación es distinta de su implementación. La pregunta "¿por qué los lenguajes funcionales usan listas (el concepto de programación abstracta) como su estructura de datos principal?" es sutil pero fundamentalmente muy diferente de la pregunta "¿por qué las implementaciones comunes de los lenguajes funcionales X, Y y Z usan listas vinculadas como su estructura de datos principal?"
RM
I Scala Vector (que se implementa como un árbol) se prefiere un poco a List stackoverflow.com/questions/6928327/… En la práctica, la mayoría de las personas todavía usan Listas (por lo que he visto).
Akavall
Hice algunos cursos de programación funcional en Scala y usé MUCHO con árboles. Es solo que la lista es más simple para ejemplos. Los árboles se usan para problemas de rendimiento. Puede crear árboles inmutables reutilizando parte de árboles más antiguos al igual que agrega elementos a listas inmutables.
Borjab

Respuestas:

56

Porque las listas son más simples que los árboles. (Puede ver esto trivialmente por el hecho de que una lista es un árbol degenerado, donde cada nodo tiene un solo hijo).

La lista de contras es la estructura de datos recursiva más simple posible de tamaño arbitrario.

Guy Steele argumentó durante el diseño del lenguaje de programación Fortress que para los cálculos masivamente paralelos del futuro, tanto nuestras estructuras de datos como nuestro flujo de control deben tener forma de árbol con múltiples ramas, no lineales como lo son ahora. Pero por el momento, la mayoría de nuestras bibliotecas de estructura de datos centrales se diseñaron con procesamiento secuencial e iterativo (o recursión de cola, en realidad no importa, son lo mismo) en mente, no procesamiento paralelo.

Tenga en cuenta que, por ejemplo, en Clojure, cuyas estructuras de datos se diseñaron específicamente para el mundo paralelo, distribuido y "nublado" de la actualidad, incluso las matrices (llamadas vectores en Clojure), probablemente la estructura de datos más "lineal" de todas, se implementan realmente como arboles

En resumen: una lista de contras es la estructura de datos recursiva persistente más simple posible, y no había necesidad de elegir un "valor predeterminado" más complicado. Por supuesto, otros están disponibles como opciones, por ejemplo, Haskell tiene matrices, colas de prioridad, mapas, montones, treaps, intentos y todo lo que puedas imaginar, pero el valor predeterminado es la simple lista de contras.

Jörg W Mittag
fuente
10
Sí, los vectores Clojure se implementan como árboles, pero vale la pena señalar que son intentos de mapeo de matriz hash , no sus binarios estándar data Tree a = Leaf a | Branch a (Tree a) (Tree a). Esto refuerza su argumento de "simplicidad".
wchargin
1
Los vectores persistentes de FWIW Clojure se implementan como (como @wchargin señala árboles algo complejos) para el acceso rápido (logarítmico con una base grande) y la actualización de elementos arbitrarios, no realmente para la operación paralela per se (la parte inmutable se encarga de eso para algunos la licenciatura). Otros lenguajes de FP hacen la misma elección (a veces con diferentes tipos de árboles) cuando quieren ambos (por ejemplo, Haskell's Sequenceo Scala's Vector), pero no usan árboles cuando solo necesitan leer, ya que pueden lograrlo en un tiempo constante y verdadero (por ejemplo, Haskell's Vectoro F # vía .Net's ImmutableArray)
badcook
1
Por ejemplo, hacer pmapping sobre un vector en Clojure aún accede a cada elemento secuencialmente; La estructura de árbol del vector generalmente está oculta para el usuario final.
badcook
5

En realidad, esas listas son árboles! Tiene nodos con dos campos cary cdrque pueden contener más nodos u hojas. Lo único que convierte esos árboles en listas es la convención para interpretar el cdrenlace como un enlace al siguiente nodo en una lista lineal, y el carenlace como el valor del nodo actual.

Dicho esto, supongo que la prevalencia de las listas vinculadas en la programación funcional está vinculada a la prevalencia de la recursividad sobre la iteración. Cuando su única construcción de bucle en cuestión es la recursión (cola), desea estructuras de datos que sean fáciles de usar con eso; y las listas vinculadas son perfectas para eso.

cmaster
fuente
55
Eso depende del idioma. Claro, puede implementar un árbol en Me gusta de LISP usando celdas cons, pero en Haskell, por ejemplo, necesitará una estructura completamente separada. Y también tenga en cuenta que la mayoría de los lenguajes funcionales tienen muchas más construcciones en bucle que la recursividad de cola. Las bibliotecas centrales de Haskell, por ejemplo, proporcionan pliegues (izquierda y derecha), escaneos, recorridos sobre árboles, iteraciones sobre claves y valores de mapas, y muchas otras estructuras más especializadas. Claro, se implementan con recursión detrás de escena, pero el usuario ni siquiera necesita pensar en eso para que funcione.
Jules
@Jules Sin embargo, la programación funcional fue desarrollada y altamente influenciada por lenguajes como LISP. Obviamente, es posible hacer que toda esta iteración de la lista sea más eficiente mediante el uso de matrices bajo el capó, o agregar azúcar sintáctico que oculta la naturaleza de una lista, pero la programación funcional pura puede funcionar, y lo hace sin ella. Además, Haskell es un lenguaje bastante reciente (32 años más joven que LISP), que agrega muchas otras ideas, azúcar sintáctica, etc. al estilo funcional puro. Creo que, a juzgar por la programación funcional Haskell juzgar es un poco como mezcladores juzgar por juzgar Thermomix ...
cmaster
2
@cmaster, mientras que Haskell es más joven, todavía tiene 27 años e influyó en muchos lenguajes (incluidos Python, Java y C #, por nombrar algunos influyentes). Juzgar la programación funcional de LISP es como juzgar la programación imperativa de ALGOL: ambos han recorrido un largo camino desde que se vuelven irreconocibles. OKAY. Lisp podría decirse que aún es relevante, pero no lo consideraría 'mainstream' y se pierde mucha información posterior, incluidos los tipos de ML.
Maciej Piechotka
1
No puede procesar la cola de los árboles unidos individualmente de forma recursiva o iterativa sin una pila explícita si desea tocar todo el árbol, por lo que no creo que la recursión de la cola tenga algo que ver con eso.
k_g
@MaciejPiechotka Ni Python, Java ni C # pueden verse como lenguajes funcionales, son imprescindibles y agregan algunas características inspiradas en la programación funcional. Una vez que tiene un estado cambiante, está firmemente dentro del dominio de la programación imperativa, no funcional. Sin embargo, estoy de acuerdo con usted en que LISP definitivamente no es convencional.
cmaster