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

1 Answer 1

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.

7
  • And why it does not work for the left case? May 16, 2021 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, 2021 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, 2021 at 8: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, 2021 at 8:32
  • 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, 2021 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.