自由单子总是存在吗？

Question

我们从类别理论中知道,并非Set中的所有endofunctors都承认一个免费的monad.规范的反例是powerset仿函数.

但是Haskell可以将任何仿函数变成一个免费的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)

是什么让这个构造适用于任何Haskell仿函数但在Set中分解？

Answer 1

很明显这个答案是错误的。我将其留在这里是为了在评论中保留有价值的讨论，直到有人提出正确的答案。

考虑 中设置的幂Set。如果我们有一个函数f : S -> T，我们可以f' : PS S -> PS T通过 来形成f' X = f [X]。很好的协变函子（我认为）。我们还可以组成f'' X = f^(-1) [X]，一个很好的逆变函子（我认为）。

让我们看看Haskell中的“幂集”：

newtype PS t = PS (t -> Bool)

这不是一个，Functor而只是一个Contravariant：

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

我们认识到这一点是因为t处于消极位置。与 不同的是Set，我们无法获得构成幂集的特征函数的“元素”，因此协变函子不可用。

因此，我推测 Haskell 承认每个协变函子都有一个自由单子的原因是它排除了那些给 带来麻烦的协变函子Set。