Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

foldr1 and infinite list on Haskell

Tags:

haskell

fold

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

like image 404
Alejandro Alcalde Avatar asked May 16 '21 16:05

Alejandro Alcalde


1 Answers

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.

like image 63
Will Ness Avatar answered Oct 11 '22 20:10

Will Ness