Couldy you help me understand the type of an implementation of foldr in Haskell?

Question

In the book titled "Programming in Haskell", on page 77, there is an implementation of foldr, in order to explain the function. It looks like this:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

Why isn't the type more like this:

foldr :: (a -> a -> b) -> a -> [a] -> b

The first argument, which is a function (a -> b -> b), will always be applied to the head of the list, and the recursively processed tail.

But what would be an example, where the head and the recursively processed tail end up having different types?

I surely don't understand something here. Could you break down the process of writing the type for this implementation of foldr?

`foldr (:) []` is a simple example. Here you construct a list, so here `b ~ [a]`. — Willem Van Onsem, Dec 16 '20 at 09:43
Note that the second parameter is the result of recursing on the tail of the list, hence that will be a `b` as well. — Willem Van Onsem, Dec 16 '20 at 09:43
"*But what would be an example, where the head and the recursively processed tail end up having different types?*". If the head and recursively processed tail would always have the same type, the signature would boil down to `foldr :: (a -> a -> a) -> a -> [a] -> a`, since in that case the "fold function" can not *return* something different than `a`, and the output type of foldr should thus be `a` as well. — Willem Van Onsem, Dec 16 '20 at 09:47
The existing answers on [this question](https://stackoverflow.com/questions/1757740/how-does-foldr-work/1763323#1763323) may be helpful as well. — CH., Dec 16 '20 at 10:01

CH. · Answer 1 · 2020-12-16T09:59:43.943

Note that at each point the tail the function is passed is the result of the recursive call foldr. Since foldr returns type b, it makes sense for the function to be of type a -> b -> b: its first argument is the head and its second is the result of the recursive foldr call.

Also, the base case is of type b, because the foldr call on [] simply returns the base case.

Manually expanding what foldr evaluates to on a concrete example (from Willem's comments on the question) might help.

For example,

  foldr (:) [] [1,2,3]
= (:) 1 (foldr (:) [] [2,3])
= (:) 1 ((:) 2 (foldr (:) [] [3]))
= (:) 1 ((:) 2 ((:) 3 (foldr (:) [] [])))
= (:) 1 ((:) 2 ((:) 3 [])) -- base case used here
= (:) 1 ((:) 2 [3])
= (:) 1 [2,3]
= [1,2,3]

Here, the function applied to the head and tail is of type Int -> [Int] -> [Int], meaning a = Int and b = [Int].

Side note: It is indeed true that foldr (:) [] = id.

You're right—I messed up as I had a more complex function that I edited into `(++)` for simplicity, without adjusting accordingly. I'll replace this immediately with a better example! — CH., Dec 16 '20 at 09:54

score 0 · Accepted Answer · edited Dec 16 '20 at 18:38

You can think of b as a state of the computation while of a as an input data. You traverse through the list backwards and react on the sequential inputs (of type a). To describe this computation you need 3 things:

A way to update the state (of type b) on new input (a). Therefore you need a function that takes an input, previous state and produces a new state: a -> b -> b
Some initial state (ofc, b)
The sequence of inputs/events – in this case a list of as.

It may be more clear to rewrite the type of foldr in a way that show the purpose of each type:

foldr :: (input -> state -> state) -> state -> [input] -> state
foldr update initialState inputs = case inputs of
  []  -- no inputs, so we leave it as it was
    -> initialState
  (input : rest) ->
    let -- update state on all of the other inputs
        prevState = foldr update initialState rest
        -- update state on the current input
        newState = update input prevState
    in newState

It is easier to see this flow on foldl tho. Then in foldr the order of the traversal is just reversed.

Couldy you help me understand the type of an implementation of foldr in Haskell?

2 Answers2