La creazione di una struttura dati (non in elenco) tramite fromList crea effettivamente l'elenco?

Question

In sostanza io sono curioso di sapere se il codice come:

let myCollection = Data.SomeCollection.fromList [1, 2, foo] 

sta effettivamente facendo quello che sembra come in fase di esecuzione, e la creazione di una lista collegata come fase intermedia nella creazione di un SomeCollection -o se questo è solo un convenienza sintattica, e il compilatore si astiene dal fare una lista nel codice compilato?

Mi scuso se questa è una domanda stupida, ma ho intenzione di scoprirlo sin da quando ho appreso alcuni Haskell.

Answer 1

Risposta breve: Forse, in un certo senso, ma non proprio ...

Longer Risposta:

Quando si dice la lista si sta pensando in termini imperativi collegato. Haskell è pigro e funzionale, il che rende la domanda difficile da rispondere.

[a,b,c] è la mano corta per a:(b:(c:[])). Se valutiamo completamente questo aspetto (ad esempio, proviamo a stamparlo), ciò che finisce nella memoria appare e agisce molto come un elenco collegato in C, ma con molti più cervelli. Ma di solito non è quello che succede a un elenco in un'impostazione funzionale. Il modo in cui operano le funzioni basate su liste è facendo qualcosa con il capo della lista e inviando la coda della lista da qualche altra parte (forse nello stesso posto). Ciò significa che una lista sembra davvero x:xs dove xs è solo una funzione che creerà il resto della lista. (a thunk con terminologia GHC)

L'intero elenco non viene creato, quindi elaborato come si farebbe in una lingua imperativa. È in streaming tramite la funzione fromList un pezzo alla volta.

Almeno così funziona la maggior parte delle funzioni di fromList. Un generico fromList per una collezione potrebbe essere simile:

fromList :: [a] -> Collection a 
fromList = Data.List.foldl' insert empty 

Alcune collezioni possono trarre vantaggio di avere più di un elemento aggiunto alla volta. Quelle collezioni (e non ne conosco nessuna, ma so che esistono) costruiranno una lista più ampia di memoria.

Al di fuori di ottimizzazioni del compilatore, tuttavia, è generalmente il caso che

è equivalente computazionalmente (all'interno di un piccolo fattore costante) di:

empty `insert` 1 `insert` 2 `insert` foo 

Disclaimer: non lo faccio Conoscere gli interni di qualsiasi implementazione Haskell abbastanza bene da dire con assoluta certezza come valutano una lista costante nel codice, ma questo non è troppo lontano dalla realtà. Attendo l'illuminazione dai guru GHC se sono fuori dalla base.