Perché le liste di controllo sono associate alla programmazione funzionale?

Il fattore più importante è che puoi anteporre un elenco single linkabile immutabile in O (1) time, che ti consente di creare ricorsivamente gli elenchi di elementi n in O (n) in questo modo:

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

Se lo facevi usando matrici immutabili, il tempo di esecuzione sarebbe quadratico perché ogni operazione cons avrebbe bisogno di copiare l'intero array, portando a un tempo di esecuzione quadratico.

Functional style encourages immutability, so also data sharing; an array is easier to share "partially" than a linked list

Suppongo che "parzialmente" la condivisione significhi che puoi prendere un sottoarray da un array in O (1) tempo, mentre con gli elenchi collegati puoi solo prendere la coda in tempo O (1) e tutto il resto ha bisogno di O ( n). È vero.

Tuttavia, prendere la coda è sufficiente in molti casi. E devi tener conto del fatto che essere in grado di creare sottotasti a basso costo non ti aiuta se non hai modo di creare array a basso costo. E (senza intelligenti ottimizzazioni del compilatore) non c'è modo di costruire passo per passo un array in modo economico.

Penso che si tratti di elenchi che sono piuttosto facili da implementare nel codice funzionale.

Schema:

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

Haskell:

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

Gli array sono più difficili e non altrettanto belli da implementare. Se vuoi che siano estremamente veloci, dovranno essere scritti a basso livello.

Inoltre, la ricorsione funziona molto meglio sugli elenchi rispetto agli array. Considera il numero di volte in cui hai ricorsivamente consumato / generato un elenco rispetto a un array indicizzato.

Un elenco a link singolo è la struttura dei dati persistente più semplice

Le strutture di dati persistenti sono essenziali per una programmazione performante, puramente funzionale.

Puoi usare facilmente i nodi Cons solo se hai una lingua raccolta dati inutili.

I nodi cons corrispondono molto allo stile di programmazione funzionale delle chiamate ricorsive e dei valori immutabili. Quindi si adatta bene al modello di programmatore mentale.

E non dimenticare le ragioni storiche. Perché si chiamano ancora Nodi Contro e peggio ancora usano auto e cdr come accessor? Le persone lo imparano dai libri di testo e dai corsi e poi lo usano.

Hai ragione, nel mondo reale gli array sono molto più facili da usare, consumano solo metà dello spazio di memoria e sono molto più performanti a causa di errori di livello della cache. Non c'è motivo di usarli con le lingue imperative.

Gli elenchi collegati sono importanti per il seguente motivo:

Una volta che prendi un numero come 3 e lo converti in successore come succ(succ(succ(zero))) , e poi usi la sostituzione con {succ=List node with some memory space} , e {zero = end of list} , finirai con un elenco collegato (di lunghezza 3).

La parte più importante è costituita da numeri, sostituzione, spazio di memoria e zero.