Erstellt das Erstellen einer (nicht listen) Datenstruktur über fromList tatsächlich die Liste?

Question

Im Wesentlichen bin ich neugierig, wenn Code wie:

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

tatsächlich tut, was es sieht wie zur Laufzeit, und eine verknüpfte Liste als Zwischenschritt zu schaffen in einem SomeCollection Schaffung -oder wenn dies nur ein syntaktische Bequemlichkeit, und der Compiler vermeidet es, eine Liste im kompilierten Code zu machen?

Entschuldigung, wenn das eine dumme Frage ist, aber ich habe seit dem Lernen etwas von Haskell herausfinden wollen.

Answer 1

Kurze Antwort: Vielleicht, in einer Art und Weise, aber nicht wirklich ...

Längere Antwort:

Wenn Sie Liste verknüpft sagen Sie unbedingt Begriffe denken. Haskell ist faul und funktional, wodurch die Frage schwer zu beantworten ist.

[a,b,c] ist kurze Hand für a:(b:(c:[])). Wenn wir dies vollständig auswerten (zum Beispiel versuchen, es auszudrucken), sieht das aus, was im Gedächtnis endet, und es verhält sich ähnlich wie eine verkettete Liste in C, aber mit viel mehr Gehirnen. Aber das passiert normalerweise nicht mit einer Liste in einer funktionalen Umgebung. Die meisten Listen-basierten Funktionen funktionieren, indem Sie etwas mit dem Kopf der Liste tun und den Rest der Liste an anderer Stelle (vielleicht an den gleichen Ort) senden. Das bedeutet, dass eine Liste wirklich wie x:xs aussieht, wobei xs nur eine Funktion ist, die den Rest der Liste erstellt. (a thunk in GHC-Terminologie)

Die gesamte Liste wird nicht erstellt und dann wie in einer imperativen Sprache ausgeführt. Es ist geströmt durch die fromList Funktion Stück für Stück.

Zumindest so funktioniert die meisten fromList Funktionen. Ein generische fromList für eine Sammlung könnte wie folgt aussehen:

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

Einige Sammlungen Vorteil, dass mehr als ein Element hinzugefügt zu einem Zeitpunkt erfolgen können. Diese Sammlungen (und ich kenne keine, aber ich weiß, dass sie existieren) werden eine umfangreichere Liste im Speicher aufbauen.

Außerhalb der Compiler-Optimierungen, jedoch ist es in der Regel der Fall, dass

rechnerisch entspricht (in einem kleinen konstanten Faktor) von:

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

Haftungsausschluss: mir nicht kenne die Interna jeder Haskell-Implementierung gut genug, um mit absoluter Sicherheit zu sagen, wie sie eine Listenkonstante im Code auswerten, aber dies ist nicht allzu weit von der Realität entfernt. Ich erwarte Erleuchtung von den GHC Gurus, wenn ich weit von der Basis entfernt bin.