How can the type of a composite Traversal be worked out?

Question

I'm following a blog post on lens' traversals. In it, there is a composition of

traverse.posts

and it ends up with type

(Traversable t, Applicative f) => 
   ([Post] -> f [Post]) -> t User -> f (t User)

I understand that it is function composition., but I'm a bit confused on how it ends up with that type.

Can anyone help me to walk through this?

Answer 1

We have the following types for the functions:

traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)
posts :: Functor f => ([Post] -> f [Post]) -> User -> f User

Let's line up the types for traverse and posts (in that order) so we can see what's going on (I'll omit the type-class constraints for this), and let's add the implied parentheses around the results of the functions (a -> b -> c is a shortcut for a -> (b -> c))

                        (a    ->   f b   ) -> (t a -> f (t b))
([Post] -> f [Post]) -> (User ->   f User)

From this we can see that a ~ User, b ~ User (~ here means 'is identified with', or 'is equal to'), so let's specialize traverse and write down the types of the functions again:

                        (User ->   f User) -> (t User -> f (t User))
([Post] -> f [Post]) -> (User ->   f User)

From this we can see that the composition will have the type (omitting the constraints for now, again)

([Post] -> f [Post]) ->                       (t User -> f (t User))

Or without the optional parentheses

([Post] -> f [Post]) -> t User -> f (t User)

Now what about the constraints? Well the use of posts gives us the Functor f constraint, and traverse gives us Applicative f and Traversable t, but because Applicative is a sub-class of Functor (it's defined as class Functor f => Applicative f where -- ...), we don't have to specify the Functor f constraint, it's already there.

So we are left with:

traverse . posts :: (Applicative f, Traversable t) => 
                    ([Post] -> f [Post]) -> t User -> f (t User)