Definition of hoistfree

Question

I have some questions concerning the function hoistfree from the Haskell library Control.Monad.Free. Given a transformation f between two functors, hoistfree f produces a morphism between the corresponding free monads. Here is its definition.

hoistFree :: Functor g => (forall a. f a -> g a) -> Free f b -> Free g b
hoistFree _ (Pure a)  = Pure a
hoistFree f (Free as) = Free (hoistFree f <$> f as)

Question 1 How does Haskell know that <$> is the map associated to g and not to f, Free f or Free g?

Question 2 Why hoistfree has not been defined as

hoistFree :: Functor g => (forall a. f a -> g a) -> Free f b -> Free g b
hoistFree _ (Pure a)  = Pure a
hoistFree f (Free as) = Free (f (hoistFree f <$> as))

?

If f is a natural transformation, these two definitions coincide. The second definition however always satisfies the relation

hoistfree f = iter (wrap . f) . map return

which looks pretty natural. Furthermore, there are a few basic functions that can be expressed using iter_map f g = iter f . map g. For example,

(=<<) f = iter_map wrap f

Question 3 Is iter_map defined somewhere? It looks like a monadic mapreduce. I didn't see it in the base library. Is there some gain in fusioning iter and map? In a few other languages, this is the case, but I am not sure for Haskell.

Answer 1

Question 1

Because of type inference, which chooses <$> from g. Indeed, in

Free (hoistFree f <$> f as)

f as has type g <something>, hence the <$> is the one given by Functor g.

Question 2

I think that, in Haskell, f is always a natural transformation. Any polymorphic function f a -> g a must be natural in a, by parametricity / free theorem. Both definitions being equivalent, I'm not sure if any one is the "best". Maybe yours is. Or maybe the original one has better performance in practice. It looks a bit as the foldr vs foldl' argument on associative operators, where there's no clear winner.

Question 3 No idea.