CODEWITHSUNDEEP
haskelltypestype-inferencefunction-compositionhindley-milner
Unsatisfied Zebra
Unsatisfied Zebra

Reputation: 143

Reasoning about types in Haskell

Chapter 16 of "Haskell Programming from First Principles" on page 995 has an exercise to manually work out how (fmap . fmap) typechecks. It suggests substituting the type of each fmap for the function types in the type of the composition operator:

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

T2 fmap :: Functor f => (m -> n) -> f m -> f n

T3 fmap :: Functor g => (x -> y) -> g x -> g y

By (attempting to) substitute T2 and T3 into T1, I arrived at the following:

T4: ((m -> n) -> f m -> f n) -> ((x -> y) -> g x -> g y) -> a -> c

Further, it suggests checking the type of (fmap . fmap) to see what the end type should look like.

T5: (fmap . fmap) :: (Functor f1, Functor f2) => (a -> b) -> f1 (f2 a) -> f1 (f2 b)

I'm having trouble understanding what I should be doing here. Could any knowledgeable haskellers help get me started, or maybe provide examples of similar exercises that show how to work out types by hand?

Upvotes: 2

Views: 137

Answers (1)

Will Ness
Will Ness

Reputation: 71119

We proceed step by careful step:

--- fmap . fmap  =  (.) fmap fmap
--- Functor f, g, ... => ..... 

(.)      :: (   b     ->      c    ) -> (a ->  b ) -> a ->     c
    fmap ::  (d -> e) -> f d -> f e
             --------    ----------
(.) fmap ::                             (a ->d->e) -> a -> f d -> f e
                                             ----          ----------
-- then,

(.) fmap      :: (   a     ->  d  ->  e ) -> a   -> f   d   -> f   e
         fmap ::  (b -> c) -> g b -> g c
                  --------    ---    ---
(.) fmap fmap ::                          (b->c) -> f (g b) -> f (g c)
                                          ------      -----      -----

It is important to consistently rename all the type variables on each separate use of a type, to avoid conflation.

We use the fact that the arrows associate on the right,

 A -> B -> C   ~   A -> (B -> C)

and the type inference rule is

   f   :: A -> B
     x :: C
   --------------
   f x ::      B    ,  A ~ C

(f :: A -> B) (x :: C) :: B under the equivalence / unification of types A ~ C and all that it entails.

Upvotes: 3

Related Questions