Haskell の代数データ型で使われるデータ構築子は、実は関数と同様に扱えます。たとえば、四則演算の式を表す代数データ型を以下のように定義したとします。
data Expr = C Int | Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div Expr Expr deriving Show
"1 + 2" は "Add (C 1) (C 2)" と表現できます。この式を評価してみましょう。
Add (C 1) (C 2) → Add (C 1) (C 2)
当たり前ですが、そのものが返ってきます。
話は変わりますが、add という関数を素直に定義すると、こうなるでしょう。
add x y = x + y
式 "add 1 2" を評価するとこうなります。
add 1 2 → 3
すなわち、関数であれば簡略化されますが、データ構築子であれば簡略化されないところだけが違います。
全置表現(あるいは Lisp もどき)
Expr を実際に計算するプログラムを書きましょう。
data Expr = C Int | Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div Expr Expr deriving Show evaluate :: Expr -> Int evaluate (C x) = x evaluate (Add e1 e2) = evaluate e1 + evaluate e2 evaluate (Sub e1 e2) = evaluate e1 - evaluate e2 evaluate (Mul e1 e2) = evaluate e1 * evaluate e2 evaluate (Div e1 e2) = evaluate e1 `div` evaluate e2
(10 + 8 / 2 * 7 - 4) に相当する Expr を evaluate の引数に指定すると、こうなります。
evaluate (Sub (Add (C 10) (Mul (Div (C 8) (C 2)) (C 7))) (C 4)) → 34
二項演算子1
データ構築子は関数のように扱えるので、バッククートで囲むと二項演算子になります。
data Expr = C Int | Expr `Add` Expr | Expr `Sub` Expr | Expr `Mul` Expr | Expr `Div` Expr deriving Show evaluate :: Expr -> Int evaluate (C x) = x evaluate (e1 `Add` e2) = evaluate e1 + evaluate e2 evaluate (e1 `Sub` e2) = evaluate e1 - evaluate e2 evaluate (e1 `Mul` e2) = evaluate e1 * evaluate e2 evaluate (e1 `Div` e2) = evaluate e1 `div` evaluate e2
こうすると、二項演算子は関数適用より弱いので括弧が減って、Expr がずいぶん読みやすくなります。
evaluate ((C 10 `Add` ((C 8 `Div` C 2) `Mul` C 7)) `Sub` C 4) → 34
二項演算子2
Haskell なんですから、本当の二項演算子を使いましょう。data の中では二項演算子の名前は ":" から始める必要があるそうです。
data Expr = C Int | Expr :+ Expr | Expr :- Expr | Expr :* Expr | Expr :/ Expr deriving Show evaluate :: Expr -> Int evaluate (C x) = x evaluate (e1 :+ e2) = evaluate e1 + evaluate e2 evaluate (e1 :- e2) = evaluate e1 - evaluate e2 evaluate (e1 :* e2) = evaluate e1 * evaluate e2 evaluate (e1 :/ e2) = evaluate e1 `div` evaluate e2
記号になるだけで、ずいぶん直感的になりますね。
evaluate ((C 10 :+ ((C 8 :/ C 2) :* C 7)) :- C 4) → 34
優先順位
二項演算子には、優先順位が付けられるはずです。という訳で、これが最終的なプログラムです。
data Expr = C Int | Expr :+ Expr | Expr :- Expr | Expr :* Expr | Expr :/ Expr deriving Show evaluate :: Expr -> Int evaluate (C x) = x evaluate (e1 :+ e2) = evaluate e1 + evaluate e2 evaluate (e1 :- e2) = evaluate e1 - evaluate e2 evaluate (e1 :* e2) = evaluate e1 * evaluate e2 evaluate (e1 :/ e2) = evaluate e1 `div` evaluate e2 infixl 6 :* , :/ infixl 5 :+ , :-
以下の実行例を見れば、感動を押さえきれないでしょう。。。
evaluate (C 10 :+ C 8 :/ C 2 :* C 7 :- C 4) → 34
おまけ
あなたの言語で、これできますか？
