6

描述 Free monad 的一种方法是说它是（某种类别的）内函子类别中的初始C幺半群，其对象是从C到的内函子C，箭头是它们之间的自然转换。如果我们认为C是Hask，则内函子就是haskell中所说Functor的，它是函子* -> *，*代表的对象Hask

初始时，从 endofunctort到 monoidm的任何映射都会End(Hask)引发从Free t到的映射m。

换句话说，任何从 Functort到 Monadm的自然转换都会引发从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
4

2 回答 2

7

Haskell 的翻译似乎是错误的。一个重要提示是您的free实现不会在任何地方使用单子绑定（或连接）。您可以找到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

于 2016-01-03T11:44:45.503 回答
3

我不了解类别理论部分，但 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 (m a)成您想要的m a，您需要对其进行应用f（以“将其t转换为”），然后利用Monadm的事实：m

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

这个类型检查，可能是你想要的:)

于 2016-01-03T11:47:45.133 回答