I came across this problem while looking at free monads, but have brought it down to a much smaller example.
In Haskell we have the following type:
fmap :: Functor f => (a -> b) -> f a -> f b
Suppose also we have the following function:
foo :: Num a => p -> a
foo = \_ -> 1
Then
fmap foo :: (Functor f, Num b) => f a -> f b
-- and
fmap (fmap foo)
:: (Functor f1, Functor f2, Num b) => f1 (f2 a) -> f1 (f2 b)
Then one would expect we can apply fmap (fmap foo) only to something of type (Functor f1, Functor f2) => f1 (f2 a), but
fmap (fmap foo) foo :: (Functor f, Num b, Num (f a)) => p -> f b
What? Why does this type check, and why does it have the given type?
If someone were able to explain what's going on here, that would be very much appreciated. I'm sorry for the vague title, but I don't understand enough what's happening here to make it more specific. I'm happy to update it to something more searchable after a response clears it up.
foo is a function, so using fmap on it (as the second argument) selects the Functor instance for functions, where fmap = (.). So you are asking why fmap foo . foo has the given type, which is a straightforward unification problem:
foo :: Num x => p -> x
fmap foo :: (Functor f, Num b) => f a -> f b
Thus we have x = f a and the resulting type signature is (Num (f a), Functor f, Num b) => p -> f b.