[Haskell-cafe] Musings on lists

[Jeff Clites]

Yes, the allocation still happens. In the "single-pass" case, all of the newly-allocated data structures don't have to persist in memory simultaneously (that is, some become available for GC while other are still being created), but they still happen.

Consider:

  xs = 1 : (2 : (3: [] ) )
  ys = 4 : (5 : (6: [] ) )
  zs = xs ++ ys

xs is a data structure with two field--a head and a tail. The head of xs contains 1 and the tail contains the list [2, 3].

On the other hand, the head of zs also contains 1, but the tail contains [2, 3, 4, 5, 6]. It doesn't matter that the tail may be initially represented as a thunk, the important part is that since xs and zs contain different tails, they have to be different physical data structures. So zs has to have been a new allocation.

Continuing with the tails of xs and zs:

(tail xs) has a head containing 2, and a tail containing [3].
(tail zs) has a head containing 2, and a tail containing [3, 4, 5, 6].

So again, these have to be two physically different data structures.

((tail (tail xs)) has a head containing 3 and a tail containing [].
((tail (tail zs)) has a head containing 3 and a tail containing [4, 5, 6].

So again, these have to be two physically different data structures.

But now:

(tail ((tail (tail zs))) has a head containing 4, and a tail containing [5, 6].
ys has a head containing 4 and a tail containing [5, 6].

Those are the same, so they can be physically the same data structure.

So zs will require 3 additional allocations, one for each element of xs.

Jef 

> On Jul 12, 2023, at 9:18 PM, Todd Wilson <twilson at csufresno.edu> wrote:
> 
> Thanks to those who have contributed answers to my questions. I can see how, in a context like
> let zs = xs ++ ysin .... with a persistent reference to the concatenation, the spine (not the elements) of xs would have to be copied, because zs might need to be traversed multiple times. But what about something like
> f (xs ++ ys)
> for a function f that makes a single pass through its argument list (like length or sum)?
> 
> --Todd