30

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

我想看看这方面的一些好例子。它可以是一些非常简单的解析器或一些不同的 monad，这并不重要。重要的是Applicative这样一个 monad 的接口符合它的returnand ap，但使用Applicative产生更有效的代码。

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

4

3 回答 3

19

另一个例子是严格的左折叠。您可以编写一个应用程序实例，该实例允许您组合折叠，以便可以在单次传递和恒定空间中对数据执行结果折叠。但是，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
于 2013-09-03T14:28:55.877 回答
17

也许典型的例子是由向量给出的。

data Nat = Z | S Nat deriving (Show, Eq, Ord)

data Vec :: Nat -> * -> * where
  V0    ::                  Vec Z x
  (:>)  :: x -> Vec n x ->  Vec (S n) x

我们可以通过一些努力使它们具有应用性，首先定义单例，然后将它们包装在一个类中。

data Natty :: Nat -> * where
  Zy  :: Natty Z
  Sy  :: Natty n -> Natty (S n)

class NATTY (n :: Nat) where
  natty :: Natty n

instance NATTY Z where
  natty = Zy

instance NATTY n => NATTY (S n) where
  natty = Sy natty

现在我们可以开发Applicative结构

instance NATTY n => Applicative (Vec n) where
  pure   = vcopies natty
  (<*>)  = vapp

vcopies :: forall n x. Natty n -> x -> Vec n x
vcopies  Zy      x  =  V0
vcopies  (Sy n)  x  =  x :> vcopies n x   

vapp :: forall n s t. Vec n (s -> t) -> Vec n s -> Vec n t
vapp  V0         V0         = V0
vapp  (f :> fs)  (s :> ss)  = f s :> vapp fs ss

我省略了Functor实例（应该fmapDefault从Traversable实例中提取）。

现在，有一个Monad对应于 this 的实例Applicative，但它是什么？对角思维！这就是所需要的！向量可以看作是来自有限域的函数的列表，因此Applicative它只是 K 和 S 组合子的列表，并且Monad具有类似Reader的行为。

vtail :: forall n x. Vec (S n) x -> Vec n x
vtail (x :> xs) = xs

vjoin :: forall n x. Natty n -> Vec n (Vec n x) -> Vec n x
vjoin Zy     _                  = V0
vjoin (Sy n) ((x :> _) :> xxss) = x :> vjoin n (fmap vtail xxss)

instance NATTY n => Monad (Vec n) where
  return    = vcopies natty
  xs >>= f  = vjoin natty (fmap f xs)

您可以通过更直接的定义来节省一点>>=，但是无论您如何削减它，单子行为都会为非对角线计算创建无用的 thunk。懒惰可能会使我们免于因世界末日因素而放慢速度，但 zip 的压缩行为<*>肯定比采用矩阵的对角线至少要便宜一些。

于 2013-09-03T11:39:21.993 回答
14

正如 pigworker 所说，数组是一个明显的例子；他们的 monad 实例不仅在类型索引长度等概念级别上存在更多问题，而且在非常现实的Data.Vector实现中表现更差：

import Criterion.Main
import Data.Vector as V

import Control.Monad
import Control.Applicative

functions :: V.Vector (Int -> Int)
functions = V.fromList [(+1), (*2), (subtract 1), \x -> x*x]

values :: V.Vector Int
values = V.enumFromN 1 32

type NRuns = Int

apBencher :: (V.Vector (Int -> Int) -> V.Vector Int -> V.Vector Int)
           -> NRuns -> Int
apBencher ap' = run values
 where run arr 0 = V.sum arr 
       run arr n = run (functions `ap'` arr) $ n-1

main = defaultMain
        [ bench "Monadic"     $ nf (apBencher ap   ) 4
        , bench "Applicative" $ nf (apBencher (<*>)) 4 ]

$ ghc-7.6 -O1 -o -fllvm -o bin/bench-d0 def0.hs
$ bench-d0
预热
估计时钟分辨率...
平均值为 1.516271 us（640001 次迭代）
在 639999 个样本中发现 3768 个异常值（0.6%） 2924 (0.5%) 时钟调用的
  高严重估计成本... 平均值为 41.62906 ns（12 次迭代） 在 12 个样本中发现 1 个异常值 (8.3%)   1 (8.3%) 高严重 基准测试 Monadic 平均值：2.773062 ms，lb 2.769786 ms，ub 2.779151 ms，ci 0.950 标准开发：22.14540 us，lb 13.55686 us，ub 36.88265 us，ci 0.950 基准测试应用 平均值：1.269351 ms，lb 1.267654 ms，ub 1.271526 ms，ci 0.950











标准开发：9.799454 我们，磅 8.171284 我们，ub 13.09267 我们，ci 0.950

-O2请注意，使用;编译时不会出现性能差异。显然到那时ap就被取代了<*>。但是>>=只能在每次函数调用后分配适量的内存，然后把结果放到位，这样显得相当耗时；而<*>可以简单地将结果长度预先计算为functions和values长度的乘积，然后写入一个固定数组。

于 2013-09-03T12:20:50.623 回答