La maggior parte delle lingue funzionali usa gli elenchi collegati come la loro struttura di dati immutabile primaria. Perché elenchi, e non ad es. alberi? Gli alberi possono anche riutilizzare percorsi e persino liste di modelli.
La maggior parte delle lingue funzionali usa gli elenchi collegati come la loro struttura di dati immutabile primaria. Perché elenchi, e non ad es. alberi? Gli alberi possono anche riutilizzare percorsi e persino liste di modelli.
Perché gli elenchi sono più semplici degli alberi. (Puoi vedere questo banalmente dal fatto che una lista è un albero degenerato, dove ogni nodo ha un solo figlio.)
La lista di contro è la struttura dati ricorsiva più semplice possibile di dimensioni arbitrarie.
Guy Steele ha sostenuto durante la progettazione del linguaggio di programmazione strongzza che per i calcoli paralleli massiccia del futuro, sia le nostre strutture dati che il nostro flusso di controllo dovrebbero essere a forma di albero con più diramazioni, non lineari come lo sono ora. Ma per il momento, la maggior parte delle nostre librerie principali della struttura dati sono state progettate con un'elaborazione sequenziale e iterativa (o ricorsione della coda, non ha molta importanza, sono la stessa cosa) in mente, non un'elaborazione parallela.
Nota che ad es. in Clojure, le cui strutture dati sono state progettate specificamente per il mondo parallelo, distribuito, "nuvoloso" di oggi, persino gli array (chiamati vettori in Clojure), probabilmente la struttura dati più "lineare" di tutti loro, in realtà sono implementati come alberi.
Quindi, in breve: una lista di contro è la struttura dati ricorsiva persistente più semplice possibile e non è stato necessario scegliere un "default" più complicato. Altri sono ovviamente disponibili come opzioni, ad es. Haskell ha array, code di priorità, mappe, heap, traci, tentativi e tutto ciò che potresti immaginare, ma l'impostazione predefinita è la semplice lista di controllo.
In realtà, quegli elenchi sono alberi! Hai nodi con due campi, car e cdr , che possono contenere più nodi o foglie. L'unica cosa che rende questi alberi in liste è la convenzione per interpretare il collegamento cdr come collegamento al nodo successivo in un elenco lineare e il collegamento car come valore del nodo corrente.
Detto questo, suppongo che la prevalenza delle liste collegate nella programmazione funzionale sia legata alla prevalenza della ricorsione rispetto all'iterazione. Quando il tuo solo costrutto ciclico a portata di mano è la ricorsione (di coda), vuoi strutture di dati che siano facili da usare con quello; e gli elenchi collegati sono perfetti per questo.
Leggi altre domande sui tag functional-programming