読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

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

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

1.木構造

数式は見慣れているため、簡単に理解できるように訓練されてはいるが、それでも、少し込み入ってくると、どのように計算したらよいか困るときがある。そのような時、木構造で描くとわかりやすくなる。3*4+5*6を木構造で表すと下図のようになる。
f:id:bitterharvest:20140819071624p:plain
木構造は、一般に、ノード(枝)とリーフ(葉)で構成されている。ノードは、ノードあるいはリーフに繋がっている。リーフは末端である。ここでは、数式を次のように表している。ノードは演算を表し、リーフは値となっている。ノードでの値は、その下にあるノードあるいはリーフの値をノードでの演算に従って計算したものである。上の図では、乗算のノードはその下にある二つのリーフの値を掛け合わせて、加算のノードは二つの乗算ノードでの計算結果を足し合わせて、値を得る。

次に、数式が与えられた時、数式を左から右の方に読んでいったときに、木構造がどのように作成されるかを示したのが、下の図である。
f:id:bitterharvest:20140819074932p:plain
最初は、Emptyのリーフが作られる。最初の値3が読み込まれると、Emptyが3のリーフに代わる。次に*を読み込むと、リーフ3が、新しい乗算ノードに代わり、その左側のリーフはリーフ3、その右側のリーフはEmptyのリーフとなる。値4が読み込まれると、Emptyが4のリーフに代わる。

さらに、+を読み込むと、新しい加算のノードが作られ、その左側のノードは先ほどの乗算のノードに、その右側にはEmptyのリーフが作れれる。このような操作を続けることで、数式を読み終わると最初に示した木構造の図が得られる。