あどけない話

Haskell のデータ構築子

Haskell

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

おまけ

あなたの言語で、これできますか？

Permalink | コメント(4) | トラックバック(1) | 16:35