haskell - 应用型变压器真的是多余的吗？

Question

有很多谈论Applicative不需要自己的转换器类，如下所示:

class AppTrans t where
    liftA :: Applicative f => f a -> t f a

但是我可以定义似乎不是应用程序组合的应用程序转换器!例如副作用流:

data MStream f a = MStream (f (a, MStream f a))

提升只是在每一步执行副作用:

instance AppTrans MStream where
    liftA action = MStream $ (,) <$> action <*> pure (liftA action)

如果 f是一个应用程序，然后 MStream f也是:

instance Functor f => Functor (MStream f) where
    fmap fun (MStream stream) = MStream $ (\(a, as) -> (fun a, fmap fun as)) <$> stream

instance Applicative f => Applicative (MStream f) where
    pure = liftA . pure
    MStream fstream <*> MStream astream = MStream
        $ (\(f, fs) (a, as) -> (f a, fs <*> as)) <$> fstream <*> astream

我知道出于任何实际目的，f应该是一个单子(monad):

joinS :: Monad m => MStream m a -> m [a]
joinS (MStream stream) = do
    (a, as) <- stream
    aslist <- joinS as
    return $ a : aslist

但是虽然有 Monad MStream m 的实例，效率低下。 (甚至不正确？) Applicative实例实际上很有用!

现在请注意，通常的流作为恒等仿函数的特殊情况出现:

import Data.Functor.Identity
type Stream a = MStream Identity a

但是Stream的组成|和 f不是 MStream f !相反，Compose Stream f a与 Stream (f a) 同构.

我想知道MStream是任意两个应用程序的组合。

编辑:

我想提供一个范畴论的观点。变压器是一个“不错的”内仿函数 t在类别 C应用仿函数(即具有强度的松散单曲面仿函数)以及自然变换 liftA来自 C 上的身份至t .现在更普遍的问题是存在哪些有用的转换器不是“与 g 组合”(其中 g 是一个应用程序)形式。我的主张是 MStream是其中之一。

Answer 1

好问题!我相信这个问题有两个不同的部分:

作曲 将现有的应用程序或 monad 转化为更复杂的应用程序。

构建所有 来自某些给定起始集的应用程序/单子(monad)。

广告 1: Monad 转换器对于组合 monad 是必不可少的。 单子(monad) don't compose directly .似乎需要由 monad 转换器提供额外的信息，告诉每个 monad 如何与其他 monad 组合(但可能这些信息已经以某种方式存在，请参阅 Is there a monad that doesn't have a corresponding monad transformer? )。

另一方面，应用程序直接组成 ，见 Data.Functor.Compose .这就是为什么不需要应用转换器来组合。他们也在 product 下关闭(但不是 coproduct )。

例如，拥有 infinite streams data Stream a = Cons a (Stream a)和另一个应用程序g , 两个 Stream (g a)和 g (Stream a)是应用程序。

但即使 Stream也是一个单子(monad)(join 采用二维流的对角线)，它与另一个单子(monad)的组合 m不会，也不会Stream (m a)也不是 m (Stream a)将永远是一个单子(monad)。

此外，正如我们所见，它们都与您的 MStream g 不同。 (非常接近 ListT done right )，因此:

广告 2:所有的应用程序都可以从一组给定的原语中构造出来吗？ 显然不是。一个问题是构造 sum 数据类型:如果 f和 g是应用程序，Either (f a) (g a)不会，因为我们不知道如何作曲Right h <*> Left x .

另一个构造原语采用固定点，如您的 MStream例子。在这里，我们可能会尝试通过定义类似的东西来概括构造

newtype Fix1 f a = Fix1 { unFix1 :: f (Fix1 f) a }

instance (Functor (f (Fix1 f))) => Functor (Fix1 f) where
    fmap f (Fix1 a) = Fix1 (fmap f a)

instance (Applicative (f (Fix1 f))) => Applicative (Fix1 f) where
    pure k = Fix1 (pure k)
    (Fix1 f) <*> (Fix1 x) = Fix1 (f <*> x)

(这需要不太好的 UndecidableInstances )然后

data MStream' f g a = MStream (f (a, g a))

type MStream f = Fix1 (MStream' f)