CODEWITHSUNDEEP
functionhaskelltypescomposition
Gonzalo_Arcos
Gonzalo_Arcos

Reputation: 150

Inferring type of composed function Haskell

Im having trouble inferring the type of this function:

(foldr (.))

I know the types of:

(.) :: (b -> c) -> (a -> b) -> a -> c

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

But now i have no idea what to do.. Is there a method to always be able to infer the type in a systematic way? How would it apply to this case?

Upvotes: 0

Views: 99

Answers (1)

Sibi
Sibi

Reputation: 48644

I usually follow these steps:

Write their types:

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

Make all the type variable name distinct:

(.) :: (b -> c) -> (a -> b) -> a -> c
foldr :: (x -> y -> y) -> y -> [x] -> y

Now since you are applying (.) to the first argument of foldr, you can infer the following relation between the types:

foldr :: (   x ->       y ->         y  ) -> y -> [x] -> y
(.) ::   (b -> c) -> (a -> b) -> (a -> c)

From the above you can infer the following relationship:

x ~ (b -> c)
y ~ (a -> b)
y ~ (a -> c)

From the above y, you can infer that both b and c should be same.

The type of foldr (.) should be:

foldr (.) :: y -> [x] -> y

Now replace y and x with the new derived ones, you will get the required type:

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

Upvotes: 4

Related Questions