Создает ли структуру данных (без списка) через список из списка?

Question

По существу мне любопытно, если такой код:

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

на самом деле делает то, что он выглядит как во время выполнения, а также создание связанного списка в качестве промежуточного шага в создании SomeCollection -или, если это просто синтаксическое удобство, а компилятор избегает создания списка в скомпилированном коде?

Извинения, если это глупый вопрос, но я имел в виду выяснить с тех пор, как изучил Хаскелл.

Answer 1

Короткий ответ: Может быть, в некотором смысле, но на самом деле не ...

Longer Ответ:

Когда вы говорите, связанный список, который вы соберетесь в императивных условиях. Haskell ленив и функциональен, что затрудняет ответ на этот вопрос.

[a,b,c] - короткая рука для a:(b:(c:[])). Если мы полностью оценим это (например, попробуем распечатать его), то, что заканчивается в памяти, выглядит и действует очень похоже на связанный список на C, но с гораздо большим количеством мозгов. Но обычно это не то, что происходит со списком в функциональной настройке. Способ работы большинства списков основан на выполнении чего-либо с заголовком списка и отправке хвоста списка из другого места (возможно, в одно и то же место). Это означает, что список действительно выглядит как x:xs, где xs - это просто функция, которая создаст остальную часть списка. (a thunk в терминологии GHC)

Весь список не создан, а затем обрабатывается так, как вы бы сделали на императивном языке. Это поток через fromList функция одна часть за раз.

По крайней мере, это самый способ работы fromList. Общий fromList для коллекции может выглядеть следующим образом:

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

Некоторые коллекции могут воспользоваться имеющие более одного элемента добавляется в то время. Эти коллекции (и я не знаю никого, но я знаю, что они существуют) создадут более обширный список в памяти.

Вне оптимизации компилятора, однако, как правило, бывает, что

вычислительно эквивалент (в пределах крошечного постоянного множителя) от:

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

Отказ от ответственности: я не хорошо знакомы с внутренностями любых реализаций Haskell, чтобы с абсолютной уверенностью сказать, как они оценивают константу списка в коде, но это не слишком далеко от реальности. Я жду просветления от гуру GHC, если я ухожу от базы.