Search code examples
haskelltypescomposition

How do I derive the type for this function:

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?

Solution

  • 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.