haskell - 自由单子(monad)总是存在吗？

Question

从范畴论中我们知道，并非Set中的所有内仿函数都承认自由单子(monad)。典型的反例是幂集仿函数。

但是 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

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

<小时/>

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

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

newtype PS t = PS (t -> Bool)

这不是一个仿函数，而只是一个逆变:

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

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

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