How do I derive the type for this function:

  • A+
Category:Languages

I'm trying to get better at playing "type tetris". I have the functions:

(=<<) :: Monad m => (a -> m b) -> m a -> m b zip :: [a] -> [b] -> [(a, b)] 

And GHCi tells me:

(zip =<<) :: ([b] -> [a]) -> [b] -> [(a, b)] 

I'm having a hard time figuring out how to arrive at that final signature from the first two. My intuition (for lack of a better word) is saying that the first argument of =<< namely a -> mb is somehow reconciled against the signature of zip, and then it should all fall out from that. But I can't understand how to make that leap. Can it be broken down in to a series of easy to follow steps?

 


It helps to do two things before everything else:

  1. put explicit parentheses so that x->y->z becomes x->(y->z)
  2. rename type variables so that there are no clashes

Wit this in mind let's rewrite the types

(=<<) :: Monad m => (a -> m b) -> (m a -> m b) zip :: [x] -> ([y] -> [(x, y)]) 

Now match the types. The first argument to =<< is zip, so (a -> m b) is the same as [x] -> ([y] -> [(x, y)]).

a          ->        m b [x]        ->        ([y] -> [(x, y)]) 

So a is [x] and m b is ([y] -> [(x, y)]). Rewriting -> in prefix notation, we get -> [y] [(x, y)], which is the same as (-> [y]) [(x, y)].

m             b (-> [y])      [(x, y)] 

So m is (-> [y]) (which is a monad indeed) and b is [(x, y)].

So now we know what is a, what is b and what is m. Let's rewrite (m a -> m b) in these terms:

(m            a)          ->          (m            b) ((-> [y])     [x])        ->          ((-> [y])     [(x, y)]) 

Rewriting in the infix style again, we get

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

which is, up to variable names, is the same answer GHC is giving you.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: