¿Por qué las listas son la estructura de datos elegida en lenguajes funcionales?

Porque las listas son más simples que los árboles. (Esto se puede ver de manera trivial por el hecho de que una lista es un árbol degenerado, donde cada nodo tiene un solo elemento secundario).

La lista de contras es la estructura de datos recursivos 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 masivos paralelos del futuro, tanto nuestras estructuras de datos como nuestro flujo de control deberían 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 estructuras de datos centrales se diseñaron con un procesamiento secuencial e iterativo (o recursión de la cola, en realidad no importa, son lo mismo) en mente, no un procesamiento paralelo.

Tenga en cuenta que, por ejemplo, en Clojure, cuyas estructuras de datos se diseñaron específicamente para el mundo paralelo, distribuido, "nublado" de hoy, incluso matrices (llamadas vectores en Clojure), probablemente la estructura de datos más "lineal" de todas, son en realidad implementados como árboles.

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

¡De hecho, esas listas son árboles! Tiene nodos con dos campos, car y cdr , que pueden contener más nodos u hojas. Lo único que convierte esos árboles en listas, es la convención de interpretar el enlace cdr como un enlace al siguiente nodo en una lista lineal, y el enlace car como el valor de nodo actual.

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