CODEWITHSUNDEEP
haskell
DemianArdus
DemianArdus

Reputation: 827

Haskell expression type?

I'm learning some Haskell and I can't understand something. I have this expression:

flip foldr id

And I needed to find its type. After a long time trying to solve this, I gave up and looked up the correct answer, which is:

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

But I can't understand why, and I would like to! I guess that the [a] -> a1 -> a1 comes from the foldr expression, but I don't know how to proceed. Thank you, and sorry for my English!

Upvotes: 0

Views: 278

Answers (1)

alecbz
alecbz

Reputation: 6488

Examine the types of the individual functions involved:

λ :t id
id :: a -> a
λ :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
λ :t flip
flip :: (a -> b -> c) -> b -> a -> c

Then try thinking of applying the functions to each other to see how the types would match up.

To avoid name conflicts when thinking, we can rewrite flip's type as (a1 -> b1 -> c1) -> b1 -> a1 -> c1.

The first thing that happens is applying flip to foldr. Looking at the types of flip and foldr, we see that the type a1 -> b1 -> c1 in flip's type gets "matched up" with the type of foldr. This means a1 matches up with a -> b -> b, b1 matches up with b, and c1 matches up with [a] -> b.

So in the context of this, flip's type becomes ((a -> b -> b) -> b -> [a] -> b) -> b -> (a -> b -> b) -> [a] -> b (I just replaced each a1 with a -> b -> c, each b1 with b , and each c1 with [a] -> b), and the type of flip foldr is the same thing with the first parameter taken away: b -> (a -> b -> b) -> [a] -> b.

We can check our work so far with ghci:

λ :t flip foldr
flip foldr :: b -> (a -> b -> b) -> [a] -> b

Now we take this type and apply it to the type of id (which we'll write as a2 -> a2). This means b matches up with a2 -> a2, and the type of flip foldr becomes (a2 -> a2) -> (a -> (a2 -> a2) -> (a2 -> a2)) -> [a] -> (a2 -> a2), and the type of flip foldr id is the same thing with the first parameter taken away: (a -> (a2 -> a2) -> (a2 -> a2)) -> [a] -> a2 -> a2. This is the same as the answer you got if we just rewrite a2 as a1 and remove some parentheses.

Upvotes: 6

Related Questions