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

Question

很多人都在谈论 Applicative 不需要 需要自己的转换器 class，像这样：

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 应该是一个单子：

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

但是，虽然 MStream m 有一个 Monad 实例，但效率很低。（甚至不正确？） Applicative 实例实际上很有用！

现在请注意，通常的流作为恒等函子的特例出现：

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

但是Stream和f的组合不是MStream f！相反，Compose Stream f a 同构于 Stream (f a)。

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

编辑：

我想提供一个范畴论的观点。变换器是应用函子类别 C 上的 "nice" 内函子 t（即具有强度的松弛幺半群函子），以及来自 liftA 上恒等式的自然变换 liftA =30=] 到 t。更普遍的问题是现在存在哪些有用的变换器不是 "compose with g" 形式（其中 g 是一个应用程序）。我的主张是 MStream 是其中之一。

Answer 1

好问题！我相信这个问题有两个不同的部分：

将现有的应用程序或单子组合成更复杂的应用程序或单子。
从一些给定的起始集构造所有 applicatives/monads。

Ad 1.: Monad 转换器对于组合 monads 是必不可少的。 Monads don't compose directly. It seems that there needs to be an extra bit of information provided by monad transformers that tells how each monad can be composed with other monads (but it could be this information is already somehow present, see Is there a monad that doesn't have a corresponding monad transformer?).

另一方面，应用程序直接组合，参见Data.Functor.Compose. This is why don't need applicative transformers for composition. They're also closed under product (but not 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.: 是否可以从一些给定的原语集构建所有应用程序？ 显然不能。一个问题是构造总和数据类型：如果 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)

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

Are applicative transformers really superfluous?

haskell

stream

typeclass