So kombinieren Sie Haskell-Muster effizient

Question

Angenommen, ich habe eine Reihe von Funktionen mit dem Typ Action -> Int -> Int (oder gleichwertig), wobei Action eine Summenart ist und jede Funktion nur mit nur einer der Varianten funktioniert.

data Action = Reset | Increment | Decrement 

tryReset :: Action -> Int -> Int 
tryReset a i = case a of 
    Reset -> 0 
    _ -> i 

tryIncrement :: Action -> Int -> Int 
tryIncrement a i = case a of 
    Increment -> i + 1 
    _ -> i 

tryDecrement :: Action -> Int -> Int 
tryDecrement a i = case a of 
    Decrement -> i - 1 
    _ -> i 

Gibt es eine Möglichkeit, die Funktionen zu definieren (z. B. wie composedTogether) in einem einzigen Fall Ausdruck zu führen (optimisedCase) anstelle der mehrfachen Fall Ausdrücke (multipleCase)?

composedTogether :: Action -> Int -> Int 
composedTogether a = tryReset a . tryIncrement a . tryDecrement a 

optimisedCase :: Action -> Int -> Int 
optimisedCase Reset i = 0 
optimisedCase Increment i = i + 1 
optimisedCase Decrement i = i - 1 

multipleCase :: Action -> Int -> Int 
multipleCase a i = case a of 
    Decrement -> i - 1 
    _ -> case a of 
    Increment -> i + 1 
    _ -> case a of 
     Reset -> 0 
     _ -> i 

Oder ist ghc bereits magisch und optimiert dies automatisch?

Answer 1

Unterschätzen Sie den GHC-Optimierer nicht. Dies ist das Ergebnis der ghc -ddump-simpl -O2 (GHC 7.10.1 hier)

composedTogether = 
    \ (a_aoc :: Action) (eta_B1 :: Int) -> 
    case a_aoc of _ [Occ=Dead] { 
     Reset -> Optimization.composedTogether1; 
     Increment -> 
     case eta_B1 of _ [Occ=Dead] { GHC.Types.I# x_ayY -> 
     GHC.Types.I# (GHC.Prim.+# x_ayY 1) 
     }; 
     Decrement -> 
     case eta_B1 of _ [Occ=Dead] { GHC.Types.I# x_ayN -> 
     GHC.Types.I# (GHC.Prim.-# x_ayN 1) 
     } 
    } 

Wie Sie sehen können, habe alles inlined.

Um das zu bekommen, musste ich auskommentieren Ihre optimisedCase. Ansonsten habe ich

composedTogether :: Action -> Int -> Int 
composedTogether = optimisedCase 

multipleCase :: Action -> Int -> Int 
multipleCase = optimisedCase 

seit der GHC entdeckt die entsprechenden Versionen.

Mein Rat ist: Vergessen Sie diese Mikrooptimierungen, schalten Sie -O2 ein, und lassen Sie den Compiler seine Arbeit machen.

Darüber hinaus überschätzen Sie nicht, was der Optimierer auch tun kann! :-P Wenn es darauf ankommt, überprüfe den generierten Core.

Answer 2

optimisedCase :: Action -> Int -> Int 
optimisedCase Reset i = 0 
optimisedCase Increment i = i + 1 
optimisedCase Decrement i = i - 1 

ist die bevorzugte Notation und viel sauberer (was dem Fall Syntax entspricht)

Answer 3

Nach ungefähr dies ein wenig zu denken. Ich denke, das ist möglich, wenn ich eine kirchenkodierte Version von Action verwende.

import Data.Monoid (Endo(..)) 

data Action' a = Action' 
    { onReset :: a 
    , onIncrement :: a 
    , onDecrement :: a 
    } 

instance Functor Action' where 
    fmap f a = Action' (f $ onReset a) (f $ onIncrement a) (f $ onDecrement a) 

tryReset' :: Action' (Endo Int) 
tryReset' = Action' (Endo $ const 0) mempty mempty 

tryIncrement' :: Action' (Endo Int) 
tryIncrement' = Action' mempty (Endo succ) mempty 

tryDecrement' :: Action' (Endo Int) 
tryDecrement' = Action' mempty mempty (Endo pred) 

composeAction' :: Monoid a => Action' a -> Action' a -> Action' a 
composeAction' x y = Action' 
    (onReset x `mappend` onReset y) 
    (onIncrement x `mappend` onIncrement y) 
    (onDecrement x `mappend` onDecrement y) 

composedTogether' :: Action' (Endo Int) 
composedTogether' = tryReset' 
    `composeAction'` tryIncrement' 
    `composeAction'` tryDecrement' 

action :: Action' a -> Action -> a 
action a Reset = onReset a 
action a Increment = onIncrement a 
action a Decrement = onDecrement a 

doComposedTogether' :: Action -> Int -> Int 
doComposedTogether' = action (appEndo <$> composedTogether') 

Meine nächste Frage ist: Ist das der beste Weg, dies zu tun? Gibt es bereits eine vorhandene Bibliothek, die das tut? Prismen?