Search code examples
haskelltypescomposition

Applying compose to fmap

For weeks I've been trying to figure out how the Haskell compiler applies the (.) to fmap.

What I mean is.

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

:t fmap
fmap :: Functor f => (a -> b) -> f a -> f b

:t (.) fmap
(.) fmap :: Functor f => (a -> a1 -> b) -> a -> f a1 -> f b

How did the compiler arrive at the type for (.) fmap?

I was actually going to ask this question here but while I was explaining what I've tried it all came together. So now I'm just going to post the answer too.

Solution

  • To get this I took fmap

    fmap :: Functor f => (a -> b) -> f a -> f b
fmap :: Functor f => (a -> b) -> (f a -> f b)

    if

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

    then

    (b -> c) of the start of the (.) function can be replaced with 

    ((a -> b) -> (f a -> f b))

    thus I have

    ((a1 -> b) -> (f a1 -> f b)) -> (a -> (a1 -> b)) -> a -> (f a1 -> f b)

    Since (.) has been applied to fmap, we can eliminate ((a1 -> b) -> (f a1 -> f b)) and we are left with

    (a -> (a1 -> b)) -> a -> (f a1 -> f b)

    Then to be extra clean we can eliminate extra parentheses.

    Glguy and Hamme from the IRC Beginner-haskell channel both reminded me (->) is right associative

    e.g. (a -> b -> c -> d) = (a -> (b -> (c -> d)))

    so we eliminate the redundant parentheses.

    (a -> a1 -> b) -> a -> f a1 -> f b

:t (.) fmap
(.) fmap :: Functor f => (a -> a1 -> b) -> a -> f a1 -> f b