5

Reading about folds on this wonderful book I have a question regarding foldr1 and the head' implementation proposed there, the code in question is:

head' = foldr1 (\x _ -> x)

this code works on infinite list, whereas foldl1 don't. A good visual explanation about why is this answer.

I do not quite understand though why does it work, considering that foldr1 is using the last element as accumulator. For example:

foldr1 (\x _ -> x) [1..]

This works because (I Think) lazy evaluation, even though foldr is starting from the last element of the list (which is infinite), I'm assuming because the function is not making use of any intermediate result, just return the first element.

So, is the compiler smart enough to know that, because inside of the lambda function only x is being used, just returns the first element of the list? even though it should start from the end?

On the contrary, doing

scanr1 (\x _ -> x) [1..]

Will print all elements of the infinite list without ending, which I suppose it's what the foldr is doing, just the compiler is smart enough to not evaluate it and return the head.

Thanks in advance.

Update

I found a really good answer that helped me understand how foldr works more deeply:

https://stackoverflow.com/a/63177677/1612432

Alejandro Alcalde
  • 5,990
  • 6
  • 39
  • 79

1 Answers1

6

foldr1 is using the last element as an initial accumulator value, but the combining function (\x _ -> x) is lazy in its second argument.

So provided the list is non-empty (let alone infinite), the "accumulator" value is never needed, thus never demanded.

foldr does not mean it should start from the right, just that the operations are grouped / associated / parenthesized on the right. If the combining function is strict in its 2nd argument that will entail indeed starting the calculations from the right, but if not -- then not.

So no, this is not about compiler being smart, this is about Haskell's lazy semantics that demand this. foldr is defined so that

foldr g z [x1,x2,...,xn]  =  g x1 (foldr g z [x2,...,xn])

and

foldr1 g xs  =  foldr g (last xs) (init xs)

and that's that.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • And why it does not work for the left case? – Alejandro Alcalde May 16 '21 at 18:51
  • 1
    ``foldl g a [x,y,...,z] = foldl g (a`g`x) [y,...,z] = (...((a`g`x)`g`y)...`g`z)`` so before `g` gets to work the whole list must be traversed. even if `g` is lazy, if the list is infinite it won't help. – Will Ness May 16 '21 at 18:56
  • 1
    I don't think that's a bug, no. Consider two cases: `foldr1 (||) [True]` and `foldr1 (||) (True : undefined : undefined)`. Both of these give the same result, but for completely different reasons. In the first case, we see there's nothing left to combine, so we return the value. In the second case, we see there's more left to combine, so we apply the combining function. There's no way to be any lazier, because we have to distinguish these cases. – dfeuer May 17 '21 at 08:31
  • @dfeuer thank you, I see it now. `foldr1` needs to know whether the head is the last element to return it without going through the function. which could change it: `foldr1 (\a b -> 42) (1 : undefined)` would give wrong result under my reading. – Will Ness May 17 '21 at 08:32
  • @dfeuer so in the end the equivalence is not `foldr1 g xs === foldr g (last xs) xs` -- it is `foldr1 g xs === foldr g (last xs) (init xs)` and it does hold: `foldr (||) undefined (init $ True : undefined)` diverges as well. so `foldr1` is definitely less lazy than `foldr`, and should only be freely used with infinite lists (or in any case those with length >= 2 guaranteed). thanks again! :) – Will Ness May 17 '21 at 08:42
  • 3
    _`foldr` does not mean it should *start* from the right, just that the operations are grouped / associated / parenthesized on the right_. I like this explicitness. – Enlico May 17 '21 at 09:51
  • @Enlico trying to write the ugliest clearest text as possible. :) leaving the matters of style to the cobbler and the tailor (and possibly English profs). few rules help: 1. describe a thing more than once, from more than one angle. 2. repeat important stuff. 3. use same words as cues of similarity (relates to 1.). 4. show how it is used, not describe. 5. pronouns are enemies of clarity, name stuff explicitly. (there should be more...) --- in English style they teach you to never repeat same word, and always replace second reference with pronoun instead of repeating the name, etc. – Will Ness May 17 '21 at 10:01