人気ブログランキング | 話題のタグを見る

Data.List モジュールの使い方(10) foldl, foldr の仲間

Data.List モジュールの foldl, foldr は畳み込み関数とよばれている。なんで畳み込みというのか Google で探してみたが、はっきりしたことは分からなかった。しかし、これらの関数はリストを屏風のように畳んでいってひとつの値にしてしまう。

畳み込みというといかにも数学用語臭くて引いてしまうが、実は、手続き型言語で1から10までの総和を計算するときは、畳み込みという用語こそ使わないが、同じようなことをしている。たとえば、Ruby で1から10までの数のリストの総和を計算するには次のようにする。

irb(main):001:0> begin
irb(main):002:1* total = 0
irb(main):003:1> for i in [1,2,3,4,5]
irb(main):004:2>   total += i
irb(main):005:2> end
irb(main):006:1> puts total
irb(main):007:1> end
15

このとき total という変数が総和を格納するための変数で、最初は0に初期化されている。次に、for ループの中でリストの要素がひとつずつ取り出され、変数 total に加算されていく。こうして、for ループが終了したときは変数 total の内容はリストの要素の総和になっている。この際、加算はつねに total とリストの要素との間で行われ途中経過はtotal に残される。このような変数の性質はCPUのアキュームレータの働きと同じだ。

このような計算は、Haskell では、foldl (+) 0 [1,2,3,4,5] で行うことができる。
Prelude> foldl (+) 0 [1,2,3,4,5]
15

total のような変数に値の代入をすることができない関数型言語の Haskell でどうしてこういうことができるかというとそれは式の展開で行っているからだ。上のfoldl (+) [1,2,3,4,5] を展開すると次のようになる。

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

上の式の意味は、まず 0 + 1 の演算を展開する。計算をするわけではないので途中経過を total に代入するわけではない。次にその式の展開に + 2 をする式を展開する。さらに3、4,5 と続けていくと全体の展開式ができる。あとはその式を計算していけば答えの15がでるという仕組みだ。したがって、途中経過を計算するアキュームレータを使う必要はない。また、上の展開式をみるとリストが、1,2,..,5 と演算(+)を適用しながら畳み込まれていく様子が分かる。foldl の l はこの畳み込みの結果が(+)演算子の左側に残っていくことを示している。

foldr はfoldl とは逆に演算が右に展開していって最後に初期値が演算子の右に適用される。

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

演算子が(+)の場合はfoldl と foldr の結果は同じだが、演算子が (-) の場合は結果が異なる。

foldl (-) 0 [1,2,3,4,5]
=((((0 - 1) - 2) - 3) - 4) - 5)
= -15

foldr (-) 0 [1,2,3,4,5]
= (1 - (2 - (3 - (4 - (5 - 0))))
= 3

foldl と foldr には初期値が必要だが、foldl1 は初期値にリストの最初の要素を使う。また、foldr1 の場合も同じように初期値にリストの最初の要素が使われる。したがって次の計算は[1,2,3,4,5] の総和になる。

Prelude> foldl1 (+) [1,2,3,4,5]
15

foldl, foldr の引数には数値計算だけではなくて、大小比較やリストへの要素の追加などの演算子もとることができる。

Prelude> foldl1 max [2,9,7,3]
9

Prelude> foldl (flip (:)) [] [1,2,3,4,5]
[5,4,3,2,1]

foldl, foldr, foldl1, foldr1 はPrelude の標準関数だ。
by tnomura9 | 2011-08-24 07:46 | Haskell | Comments(0)
<< 機械に教わる Data.List モジュール... >>