为什么我不能将这从Monad推广到Applicative？

Question

我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.我对么？如果是这样,为什么？

Answer 1

你无法通过免费Monad解除申请人,因为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是一个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,所以我们被卡住了.这基本上是我们总会陷入困境的地方.免费Monads模型Monads因此为了包裹它们我们需要以某种方式join或bind.