monad的例子,其应用部分可以比Monad部分更好地优化

Question

在一个讨论中,我听说Applicative一些解析器的接口以不同的方式实现,比它们的Monad接口更有效.原因在于Applicative,在整个有效计算运行之前,我们事先知道所有"效果".对于monad,效果可能取决于计算过程中的值,因此无法进行此优化.

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

更新:只是为了澄清,在这里我对不能成为monad的应用程序不感兴趣.问题是关于两者的事情.

Answer 1

另一个例子是严格的左折.可以编写应用性实例,其允许使得所得折叠可以对数据在单次和恒定空间中进行您撰写折叠.但是,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]

我从头顶写了上面的例子,所以它可能不是应用程序和monadic折叠的最佳实现,但运行上面的代码让我:

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

Answer 2

也许规范的例子是由向量给出的.

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与此相对应的实例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)

您可以通过>>=更直接地定义来节省一些,但无论如何切割它,monadic行为会为非对角线计算创建无用的thunk.懒惰可能会使我们免于因为一个世界末日的因素而放慢速度,但是它的拉链行为<*>必然至少比采用矩阵的对角线便宜一些.

Answer 3

正如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斌/板凳-D0 def0.hs
$板凳-D0
热身
估计时钟分辨率...
均值为1.516271我们(640001次迭代)
发现其中639999个样本(0.6%),3768个离群
  2924(0.5%)的高重度
的时钟呼叫的估计成本...
的意思是41.62906纳秒(12次迭代)
中发现1个离群值之间12个样本(8.3%)
  1(8.3%)的高重度

基准单子
意味着:2.773062毫秒,磅2.769786 MS,UB 2.779151毫秒,CI 0.950
标准偏差:22.14540我们,磅13.55686我们,UB 36.88265我们,CI 0.950

标杆应用型
平均:1.269351毫秒,磅1.267654毫秒,UB 1.271526毫秒,CI 0.950
标准偏差:9.799454我们,磅8.171284我们,ub 13.09267 us,ci 0.950

请注意,编译时不会出现性能差异-O2; 显然ap被<*>当时所取代.但是>>=只能在每个函数调用之后分配适当的内存量,然后将结果放在适当的位置,这看起来非常耗时; 而<*>可以简单地预先计算结果的长度的乘积functions和values长度,然后写入到一个固定阵列.