リストの総和も式の展開で計算

Hugsでは標準の状態で sum という関数が備わっている。リストの総和を計算する関数だ。

Hugs> sum [1,2,3,4,5]
15

sum を使えば平均値も簡単に計算できる。

Hugs> sum [1,2,3,4,5] / 5
3.0

sum のプログラムは引数のパターンを使って。概略次のようになっている。引数のパターン (x:xs) はリストの先頭の要素を x で表し、残りのリストを xs で表している。

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

プログラムの意味を考えてみよう。1行目の式では、空白のリストの要素の総和は0であると言っている。当然のことだ。2行目の式はリストの総和は、リストの先頭の要素の値と、残りのリストの総和との和であると言っている。残りのリストの総和の値はわからないけれど、分かっていることにして、先頭の値と残りの要素の総和との和を計算している。この sum xs が分かっていないけど分かっていることにするというところがミソだ。

上のプログラムは、Hugs で実際に動かしてみることができる。sum は標準であるので、関数名を mysum にした。

Hugs> mysum [1,2,3,4,5] where mysum [] = 0; mysum (x:xs) = x + mysum xs
15

関数 sum の説明が長くなってしまったが、言いたかったのはこの sum もやはり式の展開(置き換え)で動作が説明できるということだ。それは、次のような式の展開の結果を見てみれば分かる。

sum [1,2,3,4,5]
= 1 + sum [2,3,4,5]
= 1 + 2 + sum [3,4,5]
= 1 + 2 + 3 + sum [4,5]
= 1 + 2 + 3 + 4 + sum [5]
= 1 + 2 + 3 + 4 + 5 + sum []
= 1 + 2 + 3 + 4 + 5 + 0
= 15

このように、関数の定義を繰り返し適用して式を展開していくだけで求める結果が得られることがわかる。手続き型の言語のループの考え方を Haskell にそのまま持ってきてもプログラムは作れない。しかし、Haskell のプログラムの動作は全て式の展開なのだということをつかんでしまうと、再帰型の関数の定義の意味がつかめて、プログラムの発想が楽になる。

Haskell のプログラムの動作は全て式の展開で説明できるという単純性は、Haskell の大きな魅力のひとつだ。
[PR]
by tnomura9 | 2010-10-09 13:34 | Haskell | Comments(0)
<< foldr と foldl Haskellでは再帰的定義も... >>