performance - leibniz - Ejemplos de una mónada cuya parte Aplicable se puede optimizar mejor que la parte Monad

functor

Question

En una discusión escuché que la interfaz de aplicación de algunos analizadores se implementa de manera diferente, de manera más eficiente que su interfaz Monad . La razón es que con Applicative conocemos todos los "efectos" por adelantado, antes de que se ejecute todo el cómputo efectivo. Con las mónadas, los efectos pueden depender de los valores durante el cálculo, por lo que esta optimización no es posible.

Me gustaría ver algunos buenos ejemplos de esto. Puede ser un analizador muy simple o una mónada diferente, eso no es importante. Lo importante es que la interfaz de aplicación de dicha mónada cumple con su return y ap , pero el uso de Applicative produce un código más eficiente.

Actualización: solo para aclarar, aquí no estoy interesado en los aplicativos que no pueden ser mónadas. La pregunta es sobre cosas que son ambas cosas.

Answer 1

Otro ejemplo es un doblez izquierdo estricto. Puede escribir una instancia aplicativa que le permita componer pliegues para que el pliegue resultante se pueda realizar sobre los datos en un solo paso y espacio constante. Sin embargo, la instancia de mónada necesita volver a iterarse desde el comienzo de los datos para cada enlace y mantener toda la lista en la memoria.

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

Escribí lo anterior arriba de mi cabeza como ejemplo, por lo que podría no ser la implementación óptima para los pliegues aplicativos y monádicos, pero ejecutar lo anterior me da:

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

Tal vez el ejemplo canónico está dado por los vectores.

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

Podemos hacer que sean aplicativos con un poco de esfuerzo, primero definiendo singletons y luego envolviéndolos en una clase.

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

Ahora podemos desarrollar la estructura 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

Omito la instancia de Functor (que debe extraerse a través de fmapDefault desde la instancia de Traversable ).

Ahora, hay una instancia de Monad correspondiente a este Applicative , pero ¿qué es? Pensamiento diagonal! ¡Eso es lo que se requiere! Un vector puede verse como la tabulación de una función de un dominio finito, por lo tanto, el Applicative es solo una tabulación de los combinadores K y S, y la Monad tiene un comportamiento tipo 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)

Puede guardar un poco definiendo >>= más directamente, pero de cualquier forma que lo corte, el comportamiento monádico crea thunk inútiles para cálculos fuera de diagonal. La pereza puede salvarnos de la desaceleración por un factor de armagedón, pero el comportamiento de compresión del <*> será, al menos, un poco más barato que tomar la diagonal de una matriz.

Answer 3

Como dijo un cerdo, las matrices son el ejemplo obvio; su instancia de mónada no es solo un poco más problemática en el nivel conceptual con longitudes indexadas por tipo, etc., sino que también se desempeña peor en la implementación de Data.Vector es muy real:

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
calentando
estimando la resolución del reloj ...
la media es 1.516271 us (640001 iteraciones)
encontró 3768 valores atípicos entre 639999 muestras (0,6%)
2924 (0.5%) alto severo
estimar el costo de una llamada de reloj ...
la media es 41.62906 ns (12 iteraciones)
encontró 1 valores atípicos entre 12 muestras (8.3%)
1 (8.3%) alto severo

benchmarking Monadic
media: 2.773062 ms, lb 2.769786 ms, ub 2.779151 ms, ci 0.950
std dev: 22.14540 us, lb 13.55686 us, ub 36.88265 us, ci 0.950

benchmarking Aplicativo
media: 1.269351 ms, lb 1.267654 ms, ub 1.271526 ms, ci 0.950
std dev: 9.799454 us, lb 8.171284 us, ub 13.09267 us, ci 0.950

Tenga en cuenta que no sale con la diferencia de rendimiento cuando compila con -O2 ; aparentemente ap es reemplazado por <*> entonces. Pero >>= solo puede asignar la cantidad correcta de memoria después de cada llamada de función y luego colocar los resultados en su lugar, lo que parece bastante costoso en el tiempo; mientras que <*> simplemente puede precomputar la longitud del resultado como el producto de las functions y values longitudes, y luego escribir en una matriz fija.