CODEWITHSUNDEEP
haskelloptimizationpattern-matchingghc
Louis Pan
Louis Pan

Reputation: 115

How to combine haskell pattern matches efficiently

Say I have a bunch of functions with the type Action -> Int -> Int (or equivalent), where Action is a sum type, and each function only does real work with only one of the variants.

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

Is there a way to compose the functions (eg. like composedTogether) to result in a single case expression (optimisedCase), instead of the multiple case expressions (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

Or is ghc already magical and optimises this automatically?

Upvotes: 2

Views: 209

Answers (3)

chi
chi

Reputation: 116139

Don't underestimate the GHC optimiser. This is the result of ghc -ddump-simpl -O2 (GHC 7.10.1 here)

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)
        }
    }

As you can see, everything got inlined.

To get that, I had to comment out your optimisedCase. Otherwise, I got

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

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

since the GHC spotted the equivalent versions.

My advice is: forget about these micro optimizations, turn on -O2, and let the compiler do its job.

That being said, don't overestimate what the optimiser can do, too! :-P When it does matter, check the generated Core.

Upvotes: 4

Louis Pan
Louis Pan

Reputation: 115

After thinking about this a bit. I think this is possible if I use a church-encoded version of Action.

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')

My next question is: Is this the best way of doing this? Is there already an existing library that does this? Prisms?

Upvotes: 0

karakfa
karakfa

Reputation: 67507

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

is the preferred notation and much cleaner (which is equivalent to the case syntax)

Upvotes: 0

Related Questions