爲什麼我無法將此從Monad推廣到Applicative？

Question

我將hoistFree從free包概括爲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結構要求選擇（通過(>>=)或join），並且Applicative無法提供該選項，因此無法通過Free Monad提升應用程序。但是，也許並不奇怪，你可以通過一個免費應用型

-- 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是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。