haskell - Does the free monad always exist?

Question

We know from the category theory that not all endofunctors in Set admit a free monad. The canonical counterexample is the powerset functor.

But Haskell can turn any functor into a free monad.

data Free f a = Pure a | Free (f (Free f a))
instance Functor f => Monad (Free f) where
  return = Pure
  Pure a >>= f = f a
  Free m >>= f = Free ((>>= f) <$> m)

What makes this construction work for any Haskell functor but break down in Set?

question from:https://stackoverflow.com/questions/34565277/does-the-free-monad-always-exist

Answer 1

It's become clear that this answer is wrong. I'm leaving it here to preserve valuable discussion in the comments until someone formulates a correct answer.

---

Consider the power set in Set. If we have a function f : S -> T, we can form f' : PS S -> PS T by f' X = f [X]. Nice covariant functor (I think). We could also form f'' X = f^(-1) [X], a nice contravariant functor (I think).

Let's look at the "power set" in Haskell:

newtype PS t = PS (t -> Bool)

This is not a Functor, but only a Contravariant:

instance Contravariant PS where
  contramap f (PS g) = PS (g . f)

We recognize this because t is in negative position. Unlike Set, we cannot get at the "elements" of the characteristic functions that make up the power set, so the covariant functor isn't available.

I would conjecture, therefore, that the reason Haskell admits a free monad for every covariant functor is that it excludes those covariant functors that cause trouble for Set.