haskellfunctional-programming

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)

Solution

  • 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.