По сути, мне любопытно, нравится ли код:
let myCollection = Data.SomeCollection.fromList [1, 2, foo]
на самом деле делает то, что выглядит во время выполнения, и создает связанный список в качестве промежуточного шага при создании SomeCollection -or, если это просто синтаксическое удобство, и компилятор избегает создания списка в скомпилированном коде?
Извиняется, если это глупый вопрос, но я имел в виду узнать с тех пор, как изучил Haskell.
Короткий ответ: Возможно, в некотором роде, но не очень...
Более длинный ответ:
Когда вы говорите связанный список, вы думаете в императивных терминах. Haskell ленив и функциональен, что затрудняет ответ на этот вопрос.
[a,b,c] является короткой рукой для a:(b:(c:[])). Если мы полностью оценим это (например, попробуем распечатать его), то, что заканчивается в памяти, выглядит и действует очень похоже на связанный список на C, но с гораздо большим количеством мозгов. Но обычно это не то, что происходит со списком в функциональной настройке. Способ работы большинства списков основан на выполнении чего-либо с заголовком списка и отправке хвоста списка из другого места (возможно, в одно и то же место). Это означает, что список действительно выглядит как x:xs, где xs - это просто некоторая функция, которая создаст остальную часть списка. (thunk в терминологии GHC)
Весь список не создается, а затем обрабатывается так, как вы бы сделали на императивном языке. Он передается через функцию fromList по одной части за раз.
По крайней мере, так работают большинство функций fromList. Общий fromList для коллекции может выглядеть так:
fromList :: [a] -> Collection a
fromList = Data.List.foldl' insert empty
В некоторых сборниках можно использовать более одного добавленного элемента за раз. Эти коллекции (и я не знаю никого, но я знаю, что они существуют) создадут более обширный список в памяти.
Однако, помимо оптимизации компилятора, обычно бывает, что
fromList [1, 2, foo]
является вычислительно эквивалентным (в пределах крошечного постоянного множителя):
empty `insert` 1 `insert` 2 `insert` foo
Отказ от ответственности: Я не знаю внутренних компонентов каких-либо реализаций Haskell достаточно, чтобы сказать с абсолютной уверенностью, как они оценивают константу списка в коде, но это не слишком далеко от реальности. Я ожидаю просветления от гуру GHC, если я ухожу из базы.