如何有效地组合 haskell 模式匹配

Question

假设我有一堆 Action -> Int -> Int 类型的函数（或等效函数），其中 Action 是求和类型，并且每个函数只对其中一个变体进行实际工作。

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

有没有一种方法可以将函数（例如 composedTogether）组合成单个 case 表达式（optimisedCase），而不是多个 case 表达式（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

或者 ghc 已经很神奇并且自动优化了这个？

Answer 1

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

是首选的表示法，更简洁（相当于 case 语法）

Answer 2

稍微想了一下。如果我使用 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')

我的下一个问题是：这是最好的方法吗？是否已经有一个现有的库可以做到这一点？棱镜？

Answer 3

不要低估 GHC 优化器。这是 ghc -ddump-simpl -O2（此处为 GHC 7.10.1）

的结果

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

如您所见，所有内容都已内联。

为此，我不得不 注释掉 你的 optimisedCase。否则，我得到了

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

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

因为 GHC 发现了等效版本。

我的建议是：忘记这些微优化，打开 -O2，让编译器完成它的工作。

话虽这么说，但也不要高估优化器的功能！ :-P 如果确实重要，请检查生成的核心。

如何有效地组合 haskell 模式匹配

How to combine haskell pattern matches efficiently

optimization

haskell

pattern-matching

ghc