差分をプログラムする

Haskell で頻出する再帰的プログラムは、定義をすべきはずの当の関数が定義の左側にも右側にも現れるのでなんとなく納得できない感じがする。しかし、よく眺めてみると、定義の左側に現れた関数と右側に現れた関数は全く同じではない。右側の関数の引数は左側の関数の引数と比べて何らかの形で減少しているという違いがある。

例えばリストの要素の総和を計算するプログラムは、Haskell では次のようになる。

total [] = 0
total (x:xs) = x + total xs

実行例:
Main> total [1,2,3,4,5]
15

total のプログラムの再帰的定義の部分は、total (x:xs) = x + total xs で確かに定義を表す等号の両側に total という関数が現れているが、左側の total の引数は (x:xs) で右側の total の引数は xs と引数にするリストの長さが右側の total では要素一つ分減っている。

つまり、上の定義では total (x:xs) と total xs の間の差分が x ですよと total (x:xs) と total xs の差分を定義しているのだ。この場合 total という関数名は単なるタグなので、total というなまえが sum でも何でもかまわない。total が単なるタグで実体ではないと考えると定義の左と右に現れても一向構わない。

差分だけの定義でどうしてプログラムが作動してしまうのだろうと不思議に思うが、Haskell の動作の本質が置換による式の展開であると考えれば理解できる。例えばリスト [1,2,3,4,5] を total の引数にしたときどう展開されるかを見てみる。

total [1, 2, 3, 4, 5]
= 1 + total [2, 3, 4, 5]
= 1 + (2 + total [3, 4, 5])
= 1 + (2 + (3 + total [4, 5]))
= 1 + (2 + (3 + (4 + total [5])))
= 1 + (2 + (3 + (4 + (5 + total []))))
= 1 + (2 + (3 + (4 + (5 + 0))))
= 15

このように、再帰的定義が逐次適用され、式が展開されて答えが導き出されるのがわかる。再帰的定義のこの「差分を定義する」という仕組みが分かれば、定義の右と左に total が現れるという不審な定義の仕方でもプログラムが動作するのが納得できる。
[PR]
by tnomura9 | 2009-09-04 07:36 | Haskell | Comments(0)
<< 九九掛け算表 Haskell によるボウリン... >>