应用部分比 Monad 部分可以更好优化的 monad 示例

在一次讨论中我听说Applicative一些解析器的接口的实现方式不同，但比它们的更有效Monad界面。原因是与Applicative在运行整个有效计算之前，我们提前知道所有“效果”。对于 monad，效果可能取决于计算期间的值，因此这种优化是不可能的。

我希望看到一些很好的例子。它可以是一些非常简单的解析器或一些不同的单子，这并不重要。重要的是，Applicative这样一个 monad 的接口符合它的return and ap，但使用Applicative产生更高效的代码。

Update:只是为了澄清，在这里我对不能是 monad 的应用程序不感兴趣。问题是关于两者兼而有之的事情。

另一个例子是严格的左折叠。您可以编写一个应用实例，它允许您组合折叠，以便可以在单遍和恒定空间中对数据执行生成的折叠。然而，monad 实例需要从每个绑定的数据开头重新迭代，并将整个列表保留在内存中。

{-# LANGUAGE GADTs #-}

import Criterion.Main

import Data.Monoid
import Control.Applicative
import Control.Monad

import Prelude hiding (sum)

data Fold e r where
    Step :: !(a -> e -> a) -> !a -> !(a -> r) -> Fold e r
    Bind :: !(Fold e r) -> !(r -> Fold e s) -> Fold e s

data P a b = P !a !b

instance Functor (Fold e) where
    fmap f (Step step acc ret) = Step step acc (f . ret)
    fmap f (Bind fld g) = Bind fld (fmap f . g)

instance Applicative (Fold e) where
    pure a    = Step const a id
    Step fstep facc fret <*> Step xstep xacc xret = Step step acc ret where
        step (P fa xa) e = P (fstep fa e) (xstep xa e)
        acc = P facc xacc
        ret (P fa xa) = (fret fa) (xret xa)

    Bind fld g <*> fldx = Bind fld ((<*> fldx) . g)
    fldf <*> Bind fld g = Bind fld ((fldf <*>) . g)

instance Monad (Fold e) where
    return = pure
    (>>=) = Bind

fold :: Fold e r -> [e] -> r
fold (Step _ acc ret) [] = ret acc
fold (Step step acc ret) (x:xs) = fold (Step step (step acc x) ret) xs
fold (Bind fld g) lst = fold (g $ fold fld lst) lst

monoidalFold :: Monoid m => (e -> m) -> (m -> r) -> Fold e r
monoidalFold f g = Step (\a -> mappend a . f) mempty g

count :: Num n => Fold e n
count = monoidalFold (const (Sum 1)) getSum

sum :: Num n => Fold n n
sum = monoidalFold Sum getSum

avgA :: Fold Double Double
avgA = liftA2 (/) sum count

avgM :: Fold Double Double
avgM = liftM2 (/) sum count

main :: IO ()
main = defaultMain
    [ bench "Monadic"     $ nf (test avgM) 1000000
    , bench "Applicative" $ nf (test avgA) 1000000
    ] where test f n = fold f [1..n]

我从头到尾写了上面的内容作为示例，因此它可能不是应用折叠和单子折叠的最佳实现，但是运行上面的代码给了我：

benchmarking Monadic
mean: 119.3114 ms, lb 118.8383 ms, ub 120.2822 ms, ci 0.950
std dev: 3.339376 ms, lb 2.012613 ms, ub 6.215090 ms, ci 0.950

benchmarking Applicative
mean: 51.95634 ms, lb 51.81261 ms, ub 52.15113 ms, ci 0.950
std dev: 850.1623 us, lb 667.6838 us, ub 1.127035 ms, ci 0.950