免费monad和免费操作

Question

来形容免费单子的一种方式是说,这是一个最初在endofunctors的类别(某些类别的幺C),其对象是endofunctors从C到C,箭头是它们之间的自然变换.如果我们C要Hask的是endofunctor所谓Functor在Haskell,这是由函子* -> *,其中*代表的对象Hask

通过initiality,从endofunctor任何地图t到幺m在End(Hask)诱导从地图Free t到m.

所述否则,从算符任何天然转化t到单子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

Answer 1

Haskell翻译似乎错了.一个很大的提示是你的free实现不会在任何地方使用monadic bind(或join).你可以找到free的foldFree,定义如下:

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一举消除一层.