# 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 `10`

After struggling a while trying to understand why the above `head'`

function will work on infinite lists like this one:

head' [1..]

1

but its `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 `foldr`

and `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..]

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.

## Conclusion

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.