When returning a list pattern from a Haskell function how much of the original list is referenced?

This is a question regarding Haskell list pattern returns.

If I return a cons-based list pattern that matches one of the function inputs, does the function return a reference to the head of the original list, or does it return a new list with a new head that points to the tail of the original list?

My understanding is that if a function has an (x:xs) pattern in its inputs, the x will reference the head value, and xs will be a reference to the tail of the original list, so that if I return xs it will return a reference to the tail node, skipping the need to make a copy of the tail contents.

But, what happens if I return the whole pattern, or part of the pattern? Does the compiler recognize the input pattern and return a reference utilizing a node in the original list, or does it start a new list for the cons-based lead elements and just reuse the tail?

foobar (x:xs) = xs

vs

foobar (x:xs) = (x:xs)

vs

foobar (x:y:zs) = (y:zs)

  • I’m not sure if the compiler is doing this optimisation (or whether it is allowed to do that), but you can force it to not build a new list but use the original reference by using an as-pattern

    – 

Haskell-the-language doesn’t define any of this. It’s an implementation detail. The language is sufficiently high-level that the difference between both possibilities can’t directly be observed, except in that a different amount of memory is used.

Generally you should expect that a new list is created, and only the tail re-used. But it’s certainly something that the compiler can often optimise to re-use the whole thing.

If you want to be sure the original reference is reused, use an at-pattern instead:

foobar l@(x:xs) = l

If you want to be sure a new list is created… well I don’t know if there’s a completely infallible way. But I also don’t see why you would ever want this in the first place.

Leave a Comment