CODEWITHSUNDEEP
haskell
user2975699
user2975699

Reputation: 595

Types of standard prelude function when composed

I have to find out the type of these functions

(.)(:) :: (a -> b) -> a -> [b] -> [b]
(:(.)) type error
((.):) ::
((:):) :: 
(.)(.) ::

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

I don't know what to do to find the type of ((.):). These are old exam question and i am trying to learn how to find types when functions are composed. I have only been able to solve the first one.

Upvotes: 0

Views: 72

Answers (2)

mornfall
mornfall

Reputation: 428

You just use the same unification algorithm that the compiler uses (mostly). First you should rewrite the expression into a prefix form, working the ((.):) example that'd be:

\p -> (:) (.) p

which eta-reduces to

(:) (.)

now

(:) :: a -> [a] -> [a]
(.) :: (y -> z) -> (x -> y) -> x -> z

hence you need to unify (y -> z) -> (x -> y) -> x -> z with a which gives us a more specific type for (:) in the context of (:) (.):

((y -> z) -> (x -> y) -> x -> z) -> [(y -> z) -> (x -> y) -> x -> z)] -> [(y -> z) -> (x -> y) -> x -> z)]

as this is plain function application, the rule is

f   :: a -> b
x   :: a
f x :: b

now that the type of (.) and the first parameter of the specialised (:) (intermediate) type are the same, you just cancel them out to get the resulting type for (:) (.):

[(y -> z) -> (x -> y) -> x -> z)] -> [(y -> z) -> (x -> y) -> x -> z)]

Upvotes: 1

user1804599
user1804599

Reputation:

(.) has type (b -> c) -> (a -> b) -> a -> c and (:) has type a -> [a] -> [a].

(x:) is the same as \xs -> x : xs. In your case, x is (.) and thus has the type of (.).

From this we can conclude that ((.):) has type [(b -> c) -> (a -> b) -> a -> c] -> [(b -> c) -> (a -> b) -> a -> c].

GHCi verifies this:

Prelude> :t ((.):)
((.):)
  :: [(b -> c) -> (a -> b) -> a -> c]
     -> [(b -> c) -> (a -> b) -> a -> c]

Upvotes: 1

Related Questions