Por que as listas são a estrutura de dados escolhida em linguagens funcionais?

Porque as listas são mais simples que as árvores. (Você pode ver isso trivialmente pelo fato de que uma lista é uma árvore degenerada, onde cada nó tem apenas um único filho.)

A lista de cons é a estrutura de dados recursiva mais simples possível de tamanho arbitrário.

Guy Steele argumentou durante o projeto da linguagem de programação Fortress que para as computações massivamente paralelas do futuro, nossas estruturas de dados e nosso fluxo de controle devem ser em forma de árvore com múltiplos ramos, não lineares como são agora. Mas, por enquanto, a maioria das nossas principais bibliotecas de estrutura de dados foi projetada com processamento seqüencial e iterativo (ou recursão final, não importa realmente, elas são a mesma coisa) em mente, não em processamento paralelo.

Observe que, por exemplo em Clojure, cujas estruturas de dados foram projetadas especificamente para o mundo paralelo, distribuído, "nublado" de hoje, até arrays (chamados vetores em Clojure), provavelmente a estrutura de dados mais "linear" de todos eles, são realmente implementados como árvores.

Portanto, em resumo: uma lista de cons é a estrutura de dados recursiva persistente mais simples possível, e não havia necessidade de escolher um "padrão" mais complicado. Outros, claro, estão disponíveis como opções, e. Haskell tem matrizes, filas de prioridade, mapas, heaps, treaps, tentativas e tudo o que você poderia imaginar, mas o padrão é a lista de cons simples.

Na verdade, essas listas são árvores! Você tem nós com dois campos, car e cdr , que podem conter mais nós ou folhas. A única coisa que torna essas árvores em listas é a convenção para interpretar o link cdr como um link para o próximo nó em uma lista linear e o link car como o valor do nó atual.

Dito isso, acho que a prevalência de listas vinculadas na programação funcional está vinculada à prevalência da recursão sobre a iteração. Quando seu único constructo de looping é a recursão (tail-), você quer estruturas de dados fáceis de usar com isso; e as listas vinculadas são perfeitas para isso.