自由单子和自由操作

Question

自由Monad的一种描述方法是说它是一个初始的单子（initial monoid），在某个范畴C的自函子（endofunctors）范畴中，对象是从C到C的自函子，箭头是它们之间的自然变换。如果我们取C为Hask，那么自函子就是Haskell中被称为Functor的东西，它们是从* -> *到Hask的functor，其中*表示Hask的对象。

通过初始性，从自函子t到End(Hask)中的单子m的任何映射都会诱导出从Free t到m的映射。

换句话说，从一个Functor t到一个Monad m的任何自然变换都会诱导出从Free t到m的自然变换。

我本来希望能够编写一个函数...

free :: (Functor t, Monad m) => (∀ a. t a → m a) → (∀ a. Free t a → m a)
free f (Pure  a) = return a
free f (Free (tfta :: t (Free t a))) =
    f (fmap (free f) tfta) 

但这种方法无法统一，而以下方法可以实现。

free :: (Functor t, Monad m) => (t (m a) → m a) → (Free t a → m a)
free f (Pure  a) = return a
free f (Free (tfta :: t (Free t a))) =
    f (fmap (free f) tfta)

或者带签名的泛化

free :: (Functor t, Monad m) => (∀ a. t a → a) → (∀ a. Free t a → m a)

我在范畴论或者Haskell翻译中犯了错误吗？

非常希望能够听到您的建议。

PS: 含有启用代码

{-# LANGUAGE RankNTypes, UnicodeSyntax #-}
import Control.Monad.Free

- nicolas

Answer 1

哈斯克尔翻译似乎有误。一个很大的提示是，您的free实现没有在任何地方使用单调绑定（或加入）。您可以在foldFree中找到free，其定义如下：

free :: Monad m => (forall x. t x -> m x) -> (forall a. Free t a -> m a)
free f (Pure a)  = return a
free f (Free fs) = f fs >>= free f

重点在于 f 专门化为 t (Free t a) -> m (Free t a)，从而一举消除一个 Free 层。

- András Kovács

Answer 2

我不了解范畴论部分，但是Haskell部分在原始实现和原始类型签名中明显未经过良好的类型检查。

给定：

free :: (Functor t, Monad m) => (∀ a. t a → m a) → (∀ a. Free t a → m a)

当您对 Free tfta 进行模式匹配时，您会得到

tfta :: t (Free t a)
f :: forall a. t a -> m a 
free :: (forall a. t a -> m a) -> forall a. Free t a -> m a

因此

free f :: forall a. Free t a -> m a

导致

fmap (free f) :: forall a. t (Free t a) -> t (m a) 

因此，为了将t（ma）折叠成所需的ma，您需要在其上应用f（将t“转换为m”），然后利用m是一个Monad的事实：

f . fmap (free f) :: forall a. t (Free t a) -> m (m a)
join . f . fmap (free f) :: forall a. t (Free t a) -> m a

这意味着您可以通过更改free的第二个分支来修复原始定义：

{-# LANGUAGE RankNTypes, UnicodeSyntax #-}

import Control.Monad.Free
import Control.Monad

free :: (Functor t, Monad m) => (∀ a. t a → m a) → (∀ a. Free t a → m a)
free f (Pure  a) = return a
free f (Free tfta) = join . f . fmap (free f) $ tfta

这个经过类型检查，很可能也许可能是你想要的东西 ：）

- Cactus

---

确实，这是使用连接而不是绑定的另一个不错的选择。我希望我能将这两个答案标记为正确。 - nicolas

请注意，这里的free是指Free递归原理中的free：free f = fold (join . f) return，其中fold :: Functor f => (f b -> b) -> (a -> b) -> Free f a -> b。相比之下，使用>>=的foldFree库不需要Functor约束，因为Haskell中的Free数据类型对于所有的f :: * -> *参数都是有效的，我们可以直接在该结构上进行计算（尽管具有非函子f的Free f a并不是很有用）。 - András Kovács