Understanding why foldr works on infinite list on Haskell
I started learning Haskell this year, and I started reading a well known book, learnyouahaskell.com. But while reading through the High order functions chapter I came across a snipped of code that could not fully understand.
Implement head function using foldr1
head' :: [a] -> a head' = foldr1 (\x _ -> x)
For those who don't know,
foldr1 is just a short hand of
foldr that already take the last element as accumulator or starting point for the
fold. So, this snipped
foldr1 (\_ acc -> acc) [1..10] would return
After struggling a while trying to understand why the above
head' function will work on infinite lists like this one:
foldl equivalent won't, it will run for ever:
head' = foldl1 (\_ x -> x)
I decided to ask on stack overflow and that actually helped me understand why it was working, but I wanted to go a little bit deeper and continued to search. After reading through all the answers in this question that mentioned infinite list, I found the one that enlightened me. I will try to explain what I understood in order to help others with the same question, but also to exercise my understanding and why not, for my future me.
NOTE: I'm not a Haskell expert, so if I say something wrong, feel free to correct me in the comments below.
How foldr works from the inside
foldr implementation can be seen here:
foldr k z = go where go  = z go (y:ys) = y `k` go ys
A common misunderstanding with
foldl, which I also had, is that one may think the former start from the end of the list, and the latter from the begining. What really happens is that
foldl is left associative, and
foldr right associative, and both of them start from the left most side of the list.
With this knowledge, and the implementation of
foldr, we can finally understand what is going under the hood in our
head' function. Lets write our lambda function as a regular function to make it easier:
myL x _ = x
Simple enough, a function that takes two arguments and just returns the first one. Now, lets see how this piece of code would evaluate:
foldr1 myL [1..]
As we are providing a non-empty list, the pattern match would go to the second pattern, evaluating to
1 `myL` go ys
Since Haskell is lazy, and our
myL function already have all it needs (the first element of the list) there is no need to evaluate the second side of the statement, namely
go ys, so we have short-circuited
foldr and it returns with the correct result, the head of the infinite list.
This may be a simple thing to understand, but it wasn't entirely clear to me why it was working until I dived enough into the code to finally understand it correctly. Hope it was helpful for you also!
Feel free to comment if you feel something can be improved.