search

ekmett / free

free monads
http://hackage.haskell.org/package/free
Other
161 stars 65 forks source link

Why does hoistFree have such a strict type? #212

Open Wheatwizard opened 2 years ago

Wheatwizard commented 2 years ago

Currently the type for hoistFree is:

hoistFree :: Functor g => (forall a. f a -> g a) -> Free f b -> Free g b

However this type is more restrictive than it has to be. The type inferred by ghc is:

hoistFree :: Functor g => (f (Free f a) -> g (Free f a)) -> Free f a -> Free g a

This has a looser requirement on the function. Every function that is of type forall a. f a -> g a will be of type f (Free f a) -> g (Free f a). And thus this second type is more general. We can do stuff like hoistFree sort where sort only works for a which have an Ord instance.

The only benefit I can see to the existing type is that it is more category theoretic. The documentation calls the input function a natural transformation, and indeed the type requires it be a natural transformation. The looser type always preserves natural transformations but does not require the input to be a natural transformation.

What is the reason for the type of hoistFree?

RyanGlScott commented 2 years ago

Similar generalizations have been proposed in the past, such as in #131. However, it's not clear that changing the type signature as proposed would be a clear win. See https://github.com/ekmett/free/pull/131#issuecomment-207409319, which explains that hoistCofree's argument being a natural transformation makes hoistCofree a homomorphism. The same reasoning applies to hoistFree as well. If the argument's type were changed, then hoistFree would no longer be a homomorphism, which makes it more difficult to reason with.

The documentation for hoistFree and hoistCofree could be clarified to mention this more explicitly.

Wheatwizard commented 2 years ago

I think that documentation would definitely go a good way for this function. Would it maybe be a good idea to also include the two generalizations of hoistFree:

gen1 :: Functor g => (f (Free f a) -> g (Free f a)) -> Free f a -> Free g a
gen2 :: Functor f => (f (Free g a) -> g (Free g a)) -> Free f a -> Free g a

Both of these, at least for me, are much more useful to me from a practical standpoint than hoistFree is in its current state.