4

我hoistFree从免费包推广到hoistFreeM，类似于如何推广fmap到Data.Traversable.mapM。

import Control.Monad
import Control.Monad.Free
import Data.Traversable as T

hoistFreeM :: (Traversable g, Monad m) =>
              (forall a. f a -> m (g a)) -> Free f b -> m (Free g b)
hoistFreeM f = go
  where go (Pure x)  = return $ Pure x
        go (Free xs) = liftM Free $ T.mapM go =<< f xs

但是，我认为没有一种方法可以进一步推广它以与任何 一起工作Applicative，类似于如何推广Data.Traversable.mapM到Data.Traversable.traverse. 我对么？如果是这样，为什么？

4

1 回答 1

7

您不能通过 Free Monad 提升 Applicative，因为 Monad 结构需要选择（通过(>>=)或join），而 Applicative 无法提供。但是，也许不出所料，您可以通过免费应用程序提升应用程序

-- also from the `free` package
data Ap f a where
  Pure :: a -> Ap f a
  Ap :: f a -> Ap f (a -> b) -> Ap f b

hoistAp :: (forall a. f a -> g a) -> Ap f b -> Ap g b
hoistAp _ (Pure a) = Pure a
hoistAp f (Ap x y) = Ap (f x) (hoistAp f y)

hoistApA :: Applicative v => (forall a. f a -> v (g a)) -> Ap f b -> v (Ap g b)
hoistApA _ (Pure a) = pure (Pure a)
hoistApA f (Ap x y) = Ap <$> f x <*> hoistApA f y

-- just what you'd expect, really

更明确地说，让我们尝试泛化hoistFreeM到hoistFreeA. 开始很容易

hoistFreeA :: (Traversable f, Applicative v) =>
              (forall a. f a -> v (g a)) -> Free f b -> v (Free g b)
hoistFreeA _ (Pure a) = pure (Pure a)

hoistFreeM我们可以尝试从这里类推继续。mapM变成traverse了，我们可以达到

hoistFreeA f (Free xs) = ?f $ traverse (hoistFreeA f) xs

我一直在用?f它作为临时类型的洞来试图弄清楚如何前进。如果我们可以使我们可以完成这个定义

?f :: v (f (Free g b)) -> v (Free g b)

换句话说，我们需要将该f层转换为一个g层，同时生活在我们的层之下v。v由于v是 a ，因此很容易进入底层Functor，但我们必须转换f a为的唯一方法g a是我们的​​参数函数forall a . f a -> v (g a)。

我们可以尝试将它f与Free包装器一起应用以折叠我们的g层。

hoistFreeA f (Free xs) = ?f . fmap (fmap Free . f) $ traverse (hoistFreeA f) xs

但现在我们必须解决

?f :: v (v (Free g b)) -> v (Free g b)

就是join，所以我们被卡住了。从根本上说，这是我们总是会陷入困境的地方。Free Monads 对 Monads 建模，因此为了包装它们，我们需要以某种方式join或bind.

于 2013-10-27T00:55:35.277 回答