¿Por qué las listas de contras están asociadas con la programación funcional?

22

He notado que la mayoría de los lenguajes funcionales emplean una lista enlazada individualmente (una lista de "contras") como sus tipos de lista más fundamentales. Los ejemplos incluyen Common Lisp, Haskell y F #. Esto es diferente a los idiomas principales, donde los tipos de listas nativas son matrices.

¿Porqué es eso?

Para Common Lisp (que se escribe dinámicamente) tengo la idea de que las desventajas son lo suficientemente generales como para ser también la base de listas, árboles, etc. Esto podría ser una pequeña razón.

Sin embargo, para los idiomas tipados estáticamente, no puedo encontrar un buen razonamiento, incluso puedo encontrar contraargumentos:

  • El estilo funcional fomenta la inmutabilidad, por lo que la facilidad de inserción de la lista vinculada es menos ventajosa,
  • El estilo funcional fomenta la inmutabilidad, también el intercambio de datos; una matriz es más fácil de compartir "parcialmente" que una lista vinculada,
  • También podría hacer una coincidencia de patrones en una matriz regular, e incluso mejor (podría doblar fácilmente de derecha a izquierda, por ejemplo),
  • Además de eso, obtienes acceso aleatorio gratis,
  • Y (una ventaja práctica) si el idioma se escribe estáticamente, puede emplear un diseño de memoria regular y obtener un aumento de velocidad de la memoria caché.

Entonces, ¿por qué preferir las listas vinculadas?

programming-languages functional-programming list linked-list Kos
fuente
44
A partir de los comentarios sobre la respuesta de @ sepp2k, creo que es an array is easier to share "partially" than a linked listnecesario aclarar lo que quieres decir. Debido a su naturaleza recursiva, lo contrario es cierto según lo entiendo: puede compartir parcialmente una lista vinculada más fácilmente pasando cualquier nodo en ella, mientras que una matriz necesitaría pasar tiempo haciendo una nueva copia. O en términos de intercambio de datos, dos listas vinculadas pueden apuntar al mismo sufijo, lo que simplemente no es posible con las matrices.
Izkata
Si una matriz se define a sí misma como un desplazamiento, longitud, triple buffer, entonces podría compartir una matriz haciendo una nueva con offset + 1, length-1, buffer. O tenga un tipo especial de matriz como la submatriz.
Dobes Vandermeer
@Izkata Cuando hablamos de matrices, rara vez nos referimos a un búfer, como un puntero al comienzo de la memoria contigua en C. Por lo general, nos referimos a algún tipo de estructura que almacena la longitud y un puntero al comienzo de un búfer envuelto. Bajo dicho sistema, una operación de segmentación puede devolver una submatriz, cuyo puntero del búfer apunta a la mitad del búfer (en el primer elemento de la submatriz), y cuyo recuento es tal que el inicio + recuento le proporciona el último elemento. Tales operaciones de corte son O (1) en el tiempo y el espacio
Alexander - Restablecer Mónica

Respuestas:

22

El factor más importante es que puede anteponer una lista inmutable enlazada individualmente en tiempo O (1), lo que le permite construir recursivamente listas de elementos n en tiempo O (n) de esta manera:

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

Si hiciera esto usando matrices inmutables, el tiempo de ejecución sería cuadrático porque cada consoperación necesitaría copiar toda la matriz, lo que llevaría a un tiempo de ejecución cuadrático.

El estilo funcional fomenta la inmutabilidad, también el intercambio de datos; una matriz es más fácil de compartir "parcialmente" que una lista vinculada

Supongo que al compartir "parcialmente" quiere decir que puede tomar una submatriz de una matriz en el tiempo O (1), mientras que con las listas vinculadas solo puede tomar la cola en el tiempo O (1) y todo lo demás necesita O (n). Eso es verdad.

Sin embargo, tomar la cola es suficiente en muchos casos. Y debe tener en cuenta que ser capaz de crear subarrays a bajo costo no le ayuda si no tiene forma de crearlos a bajo costo. Y (sin optimizaciones inteligentes del compilador) no hay forma de construir una matriz de forma económica paso a paso.

sepp2k
fuente
Eso no es cierto en absoluto. Puede adjuntar a matrices en O (1) amortizado.
DeadMG
10
@DeadMG Sí, pero no a matrices inmutables .
sepp2k
"compartir parcialmente": creo que ambas listas de contras pueden apuntar a la misma lista de sufijos (no sé por qué querrías esto), y que puedes pasar un punto medio en lugar del comienzo de la lista a otra función sin tener que copiar (Lo he hecho muchas veces)
Izkata
@Izkata El OP estaba hablando de compartir parcialmente matrices, no listas. Además, nunca escuché lo que estás describiendo como compartir parcial . Eso es solo compartir.
sepp2k
1
@Izkata El OP utiliza el término "matriz" exactamente tres veces. Una vez para decir que los idiomas FP utilizan listas vinculadas donde otros idiomas usan matrices. Una vez para decir que las matrices son mejores para compartir parcialmente que las listas vinculadas y una vez para decir que las matrices pueden coincidir con el patrón de la misma manera (como listas vinculadas). En todos los casos, está contrastando matrices y listas vinculadas (para señalar que las matrices serían más útiles como estructura de datos primaria que las listas vinculadas, lo que lleva a su pregunta por qué se prefieren las listas vinculadas en FP), por lo que no veo cómo podría estar usando los términos indistintamente.
sepp2k
4

Creo que todo se reduce a que las listas se implementan con bastante facilidad en el código funcional.

Esquema:

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

Haskell

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

Las matrices son más difíciles y no tan bonitas de implementar. Si quieres que sean extremadamente rápidos, entonces deberán escribirse a bajo nivel.

Además, la recursividad funciona mucho mejor en listas que en matrices. Considere la cantidad de veces que ha consumido / generado recursivamente una lista frente a una matriz indexada.

Pubby
fuente
No diría que es correcto llamar a su versión de esquema una implementación de listas vinculadas. No podrá usarlo para almacenar nada más que funciones. Además, las matrices son más difíciles (en realidad imposibles) de implementar en cualquier lenguaje que no tenga soporte incorporado para ellas (o fragmentos de memoria), mientras que las listas vinculadas solo requieren algo como estructuras, clases, registros o tipos de datos algebraicos para implementar. Eso no es específico de los lenguajes de programación funcionales.
sepp2k
@ sepp2k ¿Qué quiere decir "almacenar cualquier cosa menos funciones" ?
Pubby
1
Lo que quise decir es que las listas definidas de esa manera no pueden almacenar nada que no sea una función. Sin embargo, eso no es realmente cierto. No sé, por qué he pensado eso. Lo siento por eso.
sepp2k
2

Una lista enlazada individualmente es la estructura de datos persistente más simple .

Las estructuras de datos persistentes son esenciales para una programación puramente funcional y funcional.

ziggystar
fuente
1
esto parece simplemente repetir el punto hecho y explicado en la respuesta superior que se publicó hace más de 4 años
mosquito
3
@gnat: La respuesta principal no menciona las estructuras de datos persistentes, o que las listas enlazadas individualmente son la estructura de datos persistente más simple, o que son esenciales para una programación funcional puramente funcional. No puedo encontrar ninguna superposición con la respuesta principal en absoluto.
Michael Shaw
2

Puede usar los nodos Cons fácilmente solo si tiene un lenguaje de recolección de basura.

Los nodos Contras coinciden mucho con el estilo de programación funcional de llamadas recursivas y valores inmutables. Por lo tanto, encaja bien en el modelo de programador mental.

Y no olvides razones históricas. ¿Por qué todavía se llaman Nodos Cons y peor aún usan car y cdr como accesores? La gente lo aprende de los libros de texto y cursos y luego lo usa.

Tiene razón, en el mundo real, las matrices son mucho más fáciles de usar, consumen solo la mitad del espacio de memoria y tienen mucho rendimiento debido a errores de nivel de caché. No hay razón para usarlos con idiomas imperativos.

Lothar
fuente
1

Las listas vinculadas son importantes por la siguiente razón:

Una vez que tome un número como 3, y lo convierta en secuencia sucesora como succ(succ(succ(zero))), y luego use la sustitución con {succ=List node with some memory space}, y {zero = end of list}, terminará con una lista vinculada (de longitud 3).

La parte importante real es números, sustitución y espacio de memoria y cero.

tp1
fuente