畳み込み

Haskell のリスト操作関数のうちとりわけ有用なのが、map、filter、fold(r/l) だ。このうち、map や filter は直感的にわかりやすいのですぐに使えるようになる。map はリストの要素それぞれに関数を作用させた結果のリストを作成するし、filter は述語の条件に合う要素だけのリストを作成する。

Hugs> map (^2) [1..10]
[1,4,9,16,25,36,49,64,81,100]
Hugs> filter even [1..10]
[2,4,6,8,10]

しかし、fold (畳み込み)については、直感的な理解が難しい。リストの総和や階乗を同じ関数で計算できる便利なものだが、どうしてそうなるのかをイメージできないからだ。

Hugs> foldr (+) 0 [1..10]
55
Hugs> foldr (*) 1 [1..10]
3628800

だが、foldr については、リストの (:) 演算子を引数の演算子で置き換えるというイメージで理解することができる。Haskell ではリストは [1, 2, 3, 4, 5] のように表記するが、これは (:) (cons 演算子)を使った、次のような定義のシンタックスシュガーだ。

1 : ( 2 : ( 3 : ( 4 : ( 5 : [] ))))

foldr の動作は上の (:) 演算子を、foldr の引数で置き換え、[] (空リスト)を引数の初期条件(base case) で置き換えてやればいい。たとえば、foldr (+) 0 [1..5] は次のようになる。
foldr (+) 0 [1..5] == 1 + ( 2 + ( 3 + ( 4 + ( 5 + 0 )))) == 15

foldr の引数の演算子が (+) で初期条件が 1 の場合は、

foldr (*) 1 [1..5] == 1 * ( 2 * ( 3 * ( 4 * ( 5 * 1 )))) == 120

となる。これは、次のように再帰的な定義で記述された関数の動作と同じになる。

fact 0 = 1
fact n = n * fact (n-1)

fact 5 == 5 * fact 4
== 5 * ( 4 * fact 3)
== 5 * ( 4 * ( 3 * fact 2))
== 5 * ( 4 * ( 3 * ( 2 * fact 1)))
== 5 * ( 4 * ( 3 * ( 2 * (1 * fact0))))
== 5 * ( 4 * ( 3 * ( 2 * (1 * 1))))
== 120

つまり、foldr は初期条件までを含んで、関数の再帰的定義を一行で表現したものと考えられる。そう考えると、リストの総和や階乗以外の foldr の使い方が見える。例えば max という関数は二つの引数をとり、大きい方を返すが、

Hugs> max 1 2
2

これを foldr の引数にしてやると、リストの中の最大値を見つけてくれる。

Hugs> foldr max 0 [25, 2, 49, 9]
49

この動作は次のように理解できる。

foldr max 0 [25, 2, 49, 9]
== max 25 ( max 2 ( max 49 (max 9 0)))
== max 25 ( max 2 ( max 49 9 ))
== max 25 ( max 2 49 )
== max 25 49
== 49

また、foldr は次のように文字列にも適用できる。

Hugs> foldr (\x y -> x ++ "\n" ++ y) [] ["hello", "world"]
"hello\nworld\n"

foldr が初期値の指定を含めた再帰関数を定義している事が分かれば、コンパクトな記述をするための強力な道具になる。


今日の Haskell
Hugs> takeWhile (<5) [1, 3, 2, 5, 3]
[1,3,2]
Hugs> dropWhile (<5) [1, 3, 2, 5, 3]
[5,3]

後の方に条件に合致する要素があっても、最初に条件を満たさない要素があったところで処理が中断されるところが filter とは異なっている。
[PR]
by tnomura9 | 2010-11-28 09:22 | Haskell | Comments(0)
<< Haskell で虫食い算を解く 行列をプリントする >>