[Haskell-cafe] Musings on lists

[Jeff Clites]

Lazy evaluation does make it more subtle to actually define things like algorithmic complexity. So regarding this:

> isn't xs ++ ys just a thunk that, as elements are "requested" from it, produces them first from xs and then, when those run out, defers entirely to ys from that point on? If so, then the elements of xs aren't "copied" any more than the elements of ys are; they are just produced from different places.

It helps to start with the definition of ++:

  (++) :: [a] -> [a] -> [a]
  (++) []     ys = ys
  (++) (x:xs) ys = x : xs ++ ys

But to be even more explicit, let's make our own list type so that the constructors have normal names:

  data List a = Cons a (List a) | Empty

and now this definition directly translates to:

  concat :: List a -> List a -> List a
  concat Empty ys = ys
  concat (Cons z zs) ys = Cons z (concat zs ys)

But let's be even more explicit and simplify (desugar) this definition further:

  concat :: List a -> List a -> List a
  concat xs ys =
    case xs of
      Empty -> ys
      Cons z zs -> 
        let temp = concat zs ys
        in Cons z temp

The point of all of this is to emphasize that when you evaluate `concat xs ys`, in the non-empty xs case you will allocate a new data structure, the Cons holding the head element of xs, and the `temp` thunk representing the tail of the result.

So that's the additional overhead--you have to allocate a new cell, because although the head is an existing element, the tail is not--it has to capture the parameters necessary for the recursive call, which is new information. If (and only if) you evaluate the tail, you will force evaluation of the `temp` thunk, which will allocate another cell if zs is not empty (via the recursive call). So if you traverse the entire list, you will allocate a new cell for each element of xs--once these run out, you will recurse into the Empty case, and return ys, and you won't allocate new cells for the elements of ys. But you only perform this allocation as you traverse the list (for the first time), so if you never actually traverse it then indeed you will only ever allocate one new cell in total. So you are right that saying that "xs ++ ys copies xs" is misleading--that "copy" only happens during subsequent traversal, and it would be better described as "allocates a new cell for each element of xs, as it traverses".

Also, in this notation, (:) becomes:

  prepend :: a -> List a -> List a
  prepend x xs = Cons x xs

Here, you allocate one new cell, but that's it--there is no recursive call, just a constructor application to existing values.

That was a bit long-winded but I hope it was clear.

Important note: This is different from (for example) the Java case, where List is an interface, and you can create an implementation with a custom iterator which just serves out elements from two existing lists without having to do any O(n) allocation. In the Haskell case, a list is a concrete data type, and it's expressed directly as a linked list of cells, and retrieving an element requires creation (at some point) of a cell holding that element (as well as the tail representing the rest of the list.)

Jeff

> On Jul 12, 2023, at 3:07 PM, Todd Wilson <twilson at csufresno.edu> wrote:
> 
> 
> Deaf Cafe,
> 
> I'm an educator using Haskell, and I've been telling my students certain stories about Haskell evaluation that I'm now starting to question, so I'm writing for some clarification. I've written before about similar things (e.g., "Basic list exercise" from Mar 16), so it seems my own education on this topic is not yet complete! My apologies if this is too trivial for the Cafe.
> 
> One story I tell students is that list concatenation, xs ++ ys, ends up "copying" the elements of xs but not the elements of ys, and in particular an expression like xs ++ [a], putting a new element at the end of a list, is particularly expensive, at least compared to x : xs, putting one at the beginning, which seems obvious, right?
> 
> But here is my question: isn't xs ++ ys just a thunk that, as elements are "requested" from it, produces them first from xs and then, when those run out, defers entirely to ys from that point on? If so, then the elements of xs aren't "copied" any more than the elements of ys are; they are just produced from different places. Even the expression xs ++ [a] isn't problematic in this light: just act like xs, but with one more "card up the sleeve" when you are done. Have I gotten that right?
> 
> Second, if the above is correct, then if there is a nesting, (xs ++ ys) ++ zs, and we want an element from it, there will be two steps before we can get that element from xs. And this will continue until xs is exhausted, at which point we get new elements in one step from ys, and finally in zero steps from zs. But ++ is associative, and so this list is also xs ++ (ys ++ zs), which requires less work getting the elements from xs. Is this kind of optimization something that is or can be done (automatically)?
> 
> Thanks for your indulgence,
> 
> Todd Wilson
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.