How is this function equivalent to getting the last item in a list?

Question

After completing the first problem ("Find the last element of a list") in the 99 questions exercises, I wanted to see how my solution compared with others and I found this solution.

myLast' = foldr1 (const id)

This documentation seems to show that foldr1 takes two arguments, the first being a function and the second being a list. But this definition only appears to take a function as an argument. Is there an implicit definition of the arguments passed like this?

myLast' xs = foldr1 (const id) xs

I have looked up the definitions of foldr1, const, and id, but I'm having a hard time understanding how those three work together to return the last item in the list.

Answer 1

You're exactly right. In Haskell, a function that takes two arguments can actually be treated as a function that takes one argument and returns another function that takes an argument; this is known as currying. Note that the function signature for foldr1 is:

(a -> a -> a) -> [a] -> a

While we often think of it as "a function that takes a function and a list as arguments and returns a value", it's really "a function that takes a function as an argument and returns a function that takes a list and returns a value".

Answer 2

As mipadi explains, the function is being curried. That explains how the list argument gets there, but perhaps doesn't explain how the actual fold works.

The const id bit is a little trixy. foldr1 is expecting to get something that has the type a -> a -> a. The definitions of these functions are

const :: x -> y -> x
const x y = x

id :: x -> x
id x = x

So, mangling that all together, we have

const id =
\ y -> id =
\ y -> \ x -> x =
\ y x -> x

In order words, const id does the same thing as flip const; it's a 2-argument function that throws the first argument away, and returns the second one. It's not terribly obvious that this is so; IMHO, flip const would be clearer.

foldr1 will call this function with the old value as the first argument, and the next list element as the second argument. This function always returns the next list element. The final output from foldr is the last output from the function, which will be the last element of the entire list.