bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskellで数式をビジュアルに(2)

2.プログラムで表現

数式を木構造に変換するプログラムをHaskellで実現する。数式が木構造に変換される様子をもう一度、図で示すと次のようになる。
f:id:bitterharvest:20140819074932p:plain
複雑すぎて、Javaで実現しようとは思わない。直感的にHaskellでも苦労するかなと想像したが、取り越し苦労であった。数式から木構造への変換の様子をまとめると次のようになる。
①値が来たときは、木構造の右隅にあるEmptyを値で変える。
②加算が来たときは、加算のノードを作成し、これまでのTreeをその左側のノードに、右側にはEmptyのリーフをつける。
③乗算が来たときは、木構造の右隅にある値のところに、乗算のノードを作成し、これまでの値をその左側のノードに、右側にはEmptyのリーフをつける。

まず、型の定義から始める。ノードでの演算Opと、木構造Treeを代数的データ型(dataでの定義)を用いて次のように定義する。

data Op = Plus | Mult deriving (Eq, Ord, Show)
data Tree =  Empty | Leaf Int | Node Op Tree Tree deriving (Eq, Show)

OpではPlus,Multはそれぞれ加算と乗算である。Treeは再帰で定義した。Emptyは特別なリーフで何も入っていない。通常のリーフはLeaf Intで定義され、値は整数である。ノードはNode Op Tree Treeで定義され、Treeを再帰的に読んでいる。

つぎに、数式から木構造を作り出すプログラムは次の通りである。なお、ここでの数式に用いることができる値はプログラムの説明を簡単にするために1から9までの整数とした。また、数式は、スペースなしの値と演算だけで記述される文字列で与える。例えば、"3*4+5*6"である。

expr :: String -> Tree -> Tree
expr [] tree             = tree
expr (x:xs) tree
  | x >= '1' && x <= '9' = expr xs $ number x tree
  | x == '+'             = expr xs $ plus tree
  | x == '*'             = expr xs $ mult tree
  | otherwise            = tree

expr [] tree は式を全て読みつくしたら、生成された木構造treeを返す。
expr (x:xs) treeは処理途中の数式の先頭(すなわちもっとも左側にある文字)を取り出し、値、演算+,*に分けて処理を行う。これらの処理は再帰的で、それらの処理で返されてきた木構造を残りの文字列に対する木構造への変換に利用している。

次にこれらの処理について述べる。簡単なところから、加算が来た時のプログラムは次の通りである。

plus :: Tree -> Tree
plus tree = Node Plus tree Empty

変換への仕様に応えて、新しい加算のノードを作成し、これまでのTreeをその左側のノードに、右側にはEmptyのリーフをつけていることがわかる。

値が来たときは、次のようになる。

number :: Char -> Tree -> Tree
number x Empty = Leaf $ digitToInt x
number x (Node op t1 t2)
  | t2 == Empty = Node op t1 (Leaf $ digitToInt x)
  | otherwise   = Node op t1 $ number x t2

変換への仕様に応えて、木構造の右隅にあるEmptyを値で変えていることがわかる。なお、digitToIntは文字を数値に変える関数である。これを用いるときは、次のモジュールをロードしておくこと。

import Data.Char
import Data.List

乗算が来たときは、次のようになる。

mult :: Tree -> Tree
mult (Leaf t2) = Node Mult (Leaf t2) Empty 
mult (Node op t1 t2) = Node op t1 $ mult t2

変換への仕様に応えて、木構造の右隅にある値t2のところに、乗算のノードを作成し、これまでの値t2をその左側のノードに、右側にはEmptyのリーフをつけていることがわかる。

プログラムは、間違った数式も含めて確かめてみるとよい。例えば、次のようにする。

test1 = expr "3+4" Empty
test2 = expr "3*4" Empty
test3 = expr "2*3+4*5" Empty
test4 = expr "2+3*4*5+6*7" Empty
test5 = expr "3++4" Empty
test6 = expr "3+*5" Empty
test7 = expr "3+45" Empty

2.プログラム全体

プログラム全体は次のようになる。

import Data.Char
import Data.List

data Op = Plus | Mult deriving (Eq, Ord, Show)

data Tree =  Empty | Leaf Int | Node Op Tree Tree deriving (Eq, Show)

expr :: String -> Tree -> Tree
expr [] tree             = tree
expr (x:xs) tree
  | x >= '1' && x <= '9' = expr xs $ number x tree
  | x == '+'             = expr xs $ plus tree
  | x == '*'             = expr xs $ mult tree
  | otherwise            = tree


number :: Char -> Tree -> Tree
number x Empty = Leaf $ digitToInt x
number x (Node op t1 t2)
  | t2 == Empty = Node op t1 (Leaf $ digitToInt x)
  | otherwise   = Node op t1 $ number x t2

mult :: Tree -> Tree
mult (Leaf t2) = Node Mult (Leaf t2) Empty 
mult (Node op t1 t2) = Node op t1 $ mult t2

何ともあっさりと解決で、少し、調子抜けである。プログラムを簡単にしているのは、再帰的な処理と、パターン照合である。

3.課題1

数式から木構造への次の仕様が正しいことを示しなさい。
①値が来たときは、木構造の右隅にあるEmptyを値で変える。
②加算が来たときは、加算のノードを作成し、これまでのTreeをその左側のノードに、右側にはEmptyのリーフをつける。
③乗算が来たときは、木構造の右隅にある値のところに、乗算のノードを作成し、これまでの値をその左側のノードに、右側にはEmptyのリーフをつける。

4.課題2

数式にカッコを許した場合、仕様はどのようになるかを記述しなさい。

5.課題2

上記の仕様に基づき、プログラムを作成しなさい。