Beispiele für eine Monade, deren Anwendungsteil besser optimiert werden kann als der Monad Teil

Question

In einer Diskussion hörte ich, dass die Schnittstelle von einigen Parsern anders implementiert ist, effizienter als ihre Monad Schnittstelle. Der Grund ist, dass wir mit Applicative alle "Effekte" im Voraus kennen, bevor die gesamte effektive Berechnung ausgeführt wird. Bei Monaden können Effekte während der Berechnung von Werten abhängen, so dass diese Optimierung nicht möglich ist.

Ich würde gerne einige gute Beispiele dafür sehen. Es kann ein sehr einfacher Parser oder eine andere Monade sein, das ist nicht wichtig. Die wichtige Sache ist, dass die Schnittstelle einer solchen Monade mit seinen return und ap übereinstimmt, aber die Verwendung der Applicative produziert effizienteren Code.

Update: Nur um zu klären, hier bin ich nicht in Anwendungen interessiert, die nicht Monaden sein können. Die Frage betrifft Dinge, die beides sind.

Answer 1

Ein anderes Beispiel ist eine strenge linke Falte. Sie können eine anwendbare Instanz schreiben, die es Ihnen ermöglicht, Faltungen zu erstellen, so dass die resultierende Faltung an den Daten in einem einzigen Durchgang und in einem konstanten Abstand durchgeführt werden kann. Die Monaden-Instanz muss jedoch für jede Bindung vom Anfang der Daten erneut durchlaufen und die gesamte Liste im Speicher behalten.

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

schrieb ich das oben von der Spitze von meinem Kopf, als ein Beispiel, damit es nicht die optimale Umsetzung für applicative und monadischen Falten sein könnte, aber die oben gibt mir läuft:

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

Vielleicht ist das kanonische Beispiel durch die Vektoren gegeben.

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 

Wir können sie mit ein wenig Aufwand anwendungsfähig machen, zuerst Singles definieren und dann in eine Klasse einwickeln.

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 

Jetzt können wir die Applicative Struktur

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 

Ich lasse die Functor Instanz entwickeln (die über fmapDefault aus der Traversable Instanz extrahiert werden sollen).

Nun gibt es eine Monad Instanz entsprechend dieser Applicative, aber was ist das? Diagonales Denken! Das ist gefragt! Ein Vektor kann als die Tabellierung einer Funktion aus einer endlichen Domäne gesehen werden, daher ist die Applicative nur eine Tabellierung der K- und S-Kombinatoren, und die Monad hat ein Reader ähnliches Verhalten.

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) 

Sie könnten ein wenig sparen >>= durch die Definition von mehr direkt, sondern wie du es schneiden, das monadischen Verhalten schafft nutzlos Thunks für off-diagonal Berechnungen. Faulheit könnte uns vor einer Verlangsamung durch einen Armageddon-Faktor bewahren, aber das Zipping-Verhalten des <*> wird zwangsläufig etwas billiger sein als die Diagonale einer Matrix.

Answer 3

Wie Schweinehalter sagte, sind Arrays das offensichtliche Beispiel; ihre Monade Instanz ist nicht nur ein bisschen problematischer auf der konzeptionellen Ebene mit Typ-indexierten Längen usw., sondern führt auch schlechter in der sehr realen weltlichen Data.Vector Umsetzung:

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/Bank-d0 def0.hs
$ Bank-d0
Erwärmung
Abschätzen Uhr Auflösung ...
meine ist 1,516271 uns (640.001 Iterationen)
gefunden 3768 Ausreißern unter 639999 Proben (0,6%)
2924 (0.5%) hohe schwere
Schätzung Kosten einer Uhr Anruf ...
meine ist 41,62906 ns (12 Wiederholungen)
1 Ausreißer unter den 12 Proben gefunden (8,3%)
1 (8,3%) hohe schwere

Benchmarking Monadic
Mittelwert: 2,773062 ms, lb 2,769786 ms, ub 2,779151 ms, ci 0,950
std dev: 22,14540 uns, lb 13,55686 uns, ub 36,88265 uns, ci 0,950

Benchmarking Applicative
bedeuten: 1. 269.351 ms, lb 1,267654 ms, ub 1,271526 ms, ci 0,950
std dev: 9,799454 uns, lb 8,171284 uns, ub 13,09267 uns, ci 0,950

Beachten Sie, dass es nicht mit der Performance-Unterschied kommt aus wenn Sie mit -O2 kompilieren; anscheinend ap wird dann durch <*> ersetzt. Aber >>= kann nur die richtige Menge an Speicher nach jedem Funktionsaufruf zuordnen und dann die Ergebnisse an Ort und Stelle setzen, was ziemlich zeitaufwendig erscheint; wohingegen <*> einfach die Ergebnislänge als das Produkt der Längen functions und values vorausberechnen und dann in ein festes Array schreiben kann.