Примеры монады, аппликативная часть которой может быть лучше оптимизирована, чем монадная.

Другой пример - строгая левая складка. Вы можете написать аппликативный экземпляр, который позволит вам составлять складки так, чтобы полученная складка могла быть выполнена для данных за один проход и в постоянном пространстве. Однако экземпляру монады необходимо повторить итерацию с начала данных для каждой привязки и сохранить весь список в памяти.

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

Возможно, канонический пример - это векторы.

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)

Вы можете немного сэкономить, определив >>= более прямо, но как бы вы это ни сокращали, монадическое поведение создает бесполезные переходники для недиагональных вычислений. Лень может спасти нас от замедления из-за фактора армагеддона, но режим «застегивания» <*> обязательно будет по крайней мере немного дешевле, чем получение диагонали матрицы.

Как сказал свинарник, очевидным примером являются массивы; их экземпляр монады не только немного более проблематичен на концептуальном уровне с индексированными типами длинами и т. д., но также работает хуже в очень реальной реализации 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 мкс (640001 итераций)
обнаружено 3768 выбросов среди 639999 выборок (0,6%)
2924 (0,5%) высокая серьезность
оценка стоимости вызова часов ...
среднее значение 41,62906 нс (12 итераций)
обнаружил 1 выброс среди 12 образцов (8,3%)
1 (8,3%) очень серьезный

сравнительный анализ Монадический
среднее значение: 2,773062 мс, фунт 2,769786 мс, ub 2,779151 мс, ci 0,950
std dev: 22.14540 us, lb 13.55686 us, ub 36.88265 us, ci 0,950

сравнительный анализ Применимое значение: 1,269351 мс, lb 1,267654 мс, ub 1,271526 мс, ci 0,950
std dev: 9.799454 us , фунт 8,171284 us, ub 13,09267 us, ci 0,950

Обратите внимание, что разница в производительности не проявляется при компиляции с -O2; очевидно, что ap заменяется на <*>. Но >>= может выделять только нужный объем памяти после каждого вызова функции, а затем помещать результаты в нужное место, что, по-видимому, требует значительных временных затрат; тогда как <*> может просто предварительно вычислить длину результата как произведение длин functions и values, а затем записать в один фиксированный массив.