Does creating a (non-list) data structure via fromList actually create the list?

Question

Essentially I'm curious if code like:

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

is actually doing what it looks like at runtime, and creating a linked list as an intermediate step in creating a SomeCollection—or if this is just a syntactic convenience, and the compiler eschews making a list in the compiled code?

Apologies if this is a stupid question, but I've been meaning to find out ever since learning some Haskell.

Answer 1

Short answer: Maybe, in a way, but not really...

Longer Answer:

When you say linked list you are thinking in imperative terms. Haskell is lazy and functional which makes the question hard to answer.

[a,b,c] is short hand for a:(b:(c:[])). If we fully evaluate this (for example try to print it out) what ends up in memory looks and acts a lot like a linked list in C, but with a lot more brains. But that is not usually what happens to a list in a functional setting. The way most list based functions operate is by doing something with the head of the list and sending the tail of the list off somewhere else (perhaps to the same place). That means a list really looks like x:xs where xs is just some function that will create the rest of the list. (a thunk in GHC terminology)

The whole list is not created, then processed as you would do in an imperative language. It is streamed through the fromList function one piece at a time.

At least that is the way most fromList functions work. A generic fromList for a collection might look like:

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

Some collections can take advantage of having more then one element added at a time. Those collections (and I don't know of any, but I know they exist) will build up a more extensive in memory list.

Outside of compiler optimizations, however, it is generally the case that

fromList [1, 2, foo]

is computationally equivalent (within a tiny constant factor) of:

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

Disclaimer: I do not know the internals of any Haskell implementations well enough to say with absolute certainty how they evaluate a list constant in code, but this is not too far from reality. I await enlightenment from the GHC gurus if I am way off base.