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.
I found a really good answer that helped me understand how foldr works more deeply:
https://stackoverflow.com/a/63177677/1612432
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With