[Haskell-cafe] Musings on lists

[MigMit]

xs ++ ys is just a thunk, but only the first time you "request" it. Afterwards it is a real list. More correctly, due to the lazy nature of Haskell, it's actually part list, part "thunk". Basically, if you do [1,2,3] ++ [4,5,6], and then "request" some elements from it, it's going to be like this:

thunk (++) {arguments: 1:2:3:[] and 4:5:6:[]}
|
| Requesting first element
v
1 : thunk (++) {arguments: 2:3:[] and 4:5:6:[]}
|
| Requesting second element
v
1 : 2 : thunk (++) {arguments: 3:[] and 4:5:6:[]}
|
| Requesting first element again
v
1 : 2 : thunk (++) {arguments: 3:[] and 4:5:6:[]} -- no change
|
| Requesting fifth element
v
1 : 2 : 3 : 4 : 5: 6 : [] -- at this point those "4:5:6:[]" are exactly the same as "4:5:6:[]" from the second argument.

> On 13 Jul 2023, at 00:06, 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.