performance - Applicative 部分可以比 Monad 部分更好地优化的 monad 示例

Question

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

我想看看这方面的一些好例子。它可以是一些非常简单的解析器或一些不同的 monad，这并不重要。重要的是 Applicative这种单子(monad)的接口(interface)符合其return和 ap ，但使用 Applicative产生更高效的代码。

更新:澄清一下，在这里我对不能是单子(monad)的应用程序不感兴趣。问题是关于两者兼而有之的事情。

Answer 1

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

{-# 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]

我从头顶上写了上面的例子，所以它可能不是应用和单子(monad)折叠的最佳实现，但是运行上面的代码给了我:

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