foldl' と無限リストの foldr

Haskell のリスト操作関連の高階関数は map や filter のように直観的に理解しやすいものが多い。例えば、リストの要素を全て２倍にしたい時は、map (*2) [1,2,3,4,5] のようにできるし、リストから偶数だけを取り出したい時は、filter even [1..10] で取り出すことができる。

しかし、畳込みに関しては一体何を行う関数なのか掴み難い。リストの総和を得るのに foldr (+) 0 [1,2,3,4,5] でできると言われても、どうしてそうなるのか合点がいかない。

実は、畳み込み関数 folds には明快な機能があるのだ。それは再帰関数を記述するという役割だ。例えば、リストの要素の総和を計算する関数 sum の定義は次のようにできる。

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

上の再帰的定義で１行目は the base case だ。再帰的定義で式を展開するときにも最後には確定的な値が必要になる。the base case はそのような確定的な値を提供する。

２行目は the recursive case だ。等号の両側に同じ名前の関数 sum が存在するので、再帰的定義と呼ばれるが、左右の sum は引き数が違うので、こういう定義でも矛盾は起きない。リストを引き数とする再帰的定義では sum (x:xs) と sum xs の関係を記述してある。sum (x:xs) と sum xs の値がすでに分かっていると仮定して、sum (x:xs) = x + sum xs という関係が成り立っていると定義しているのだ。

sum (x:xs) を x + sum xs に変形するのを還元 reduction という。リスト (x:xs) がひとつ要素の少ない xs に置き換えられているからだ。この例では、sum (x:xs) は + 演算の右のほう右のほうへと還元される、そこでこれを右再帰型の再帰的定義と呼ぶことにする（正式にはこのような用語はなく、この記事でのみ使うことにする）。

右再帰型の再帰的定義では、還元が右へ右へと行われていくので、sum をリスト [1,2,3] に関数適用すると次のように展開される。

sum [1,2,3]
= 1 + sum [2,3]
= 1 + (2 + sum [3])
= 1 + (2 + (3 + sum []))
= 1 + (2 + (3 + 0))

上の展開式を見ると、sum が + 演算子の右へ右へと展開されて最後に the base case の０が適用されるのがわかる。このようなタイプの再帰的関数は、foldr で記述することができる。

Prelude> foldr (+) 0 [1,2,3]
6

どうしてそうなるのだろうか、foldr の定義は次のようになっている。

foldr f z [] = z
foldr f z (x:xs) = x `f` foldr f z xs

したがって、foldr (+) 0 [1,2,3] を展開すると次のようになる。

foldr (+) 0 [1,2,3]
= 1 + (foldr (+) 0 [2,3])
= 1 + (2 + (foldr (x) 0 [3]))
= 1 + (2 + (3 + (foldr (+) 0 [])))
= 1 + (2 + (3 + 0))

最後の行を見るとこれが sum [1,2,3] の展開と一致していることが分かる。foldr は sum のような右再帰型の再帰関数を一般的にした、再帰関数一般の機能を果たす関数だったのだ。したがって、同じようなタイプのプログラミングになる、product [1,2,3] も foldr (*) 1 [1,2,3] で計算できる。

Prelude> product [1,2,3]
6
Prelude> foldr (*) 1 [1,2,3]
6

それでは foldl にはどんな機能があるのだろうか。sum の the recursive case はパターン (x:xs) を使って定義されていた。これは、先頭の要素が x で残りのリストが xs となるようなリスト全般にマッチする。そこで、Haskell の仕様にはないが、(xs:x) というパターンを使った再帰的定義を考えてみる。次の sum' がその関数だ。

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

この定義では sum' の reduction は、+ 演算子の左へ左へと行われていく。 このようなタイプの再帰的定義を、左再帰型の再帰関数とこの記事では呼ぶことにする。ちなみに、sum' [1,2,3] を展開すると次のようになる。

sum' [1,2,3]
= sum' [1,2] + 3
= (sum' [1] + 2) + 3
= ((sum' [] + 1) + 2) + 3
= ((0 + 1) + 2) + 3

ところで foldl の定義は次のようになる。

foldl f z [] = z
foldl f x (x:xs) = foldl f (f z x) xs

そこで、foldl (+) 0 [1,2,3] を展開してみると次のようになる。

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

これは sum' [1,2,3] の展開と一致する。

したがって、何をやっているのか分からなかった folds についても、foldr は右再帰型の汎用の再帰関数、foldl は左再帰型の汎用の再帰関数ととらえることで、その役割をすっきりと理解することができる。また、再帰関数を folds として記述することで、無名再帰関数を書くことができる。

さて、本題はこれからだ。Data.List モジュールには foldl' 関数というのがあり、foldl を正格に実行すると説明されている。

Haskell は遅延評価が標準で、関数は thunk として実行待ちの状態でメモリへ展開され、その関数の値が必要になった時だけ thunk が評価されるという方式になっている。したがって、どのようにメモリへ展開されるのかは分からないが、foldl は計算前に式が展開された形でメモリに記憶され、foldl が必要とされた時にメモリの展開式を実際に計算するということになる。

foldl' の場合は遅延評価を行わず、式の展開の各ステップで z の値の計算が行われ、戻値が返される。thunk をメモリに展開したり、計算に多量のスタックを使用したりしないので、メモリ効率がよく、計算が速い。

foldl と foldl' の差は次の実行例の実行速度を体験すると体感することができる。

Prelude> :m +Data.List
Prelude Data.List> foldl (+) 0 [1..2000000]
2000001000000
Prelude Data.List> foldl' (+) 0 [1..2000000]
2000001000000

これは foldl (+) 0 [1,2,3] = ((0 + 1) + 2) + 3 の展開を thunk としてメモリにおかず、直接に括弧の深いところから順に計算してその値を利用していくと考えると納得がいく。foldl をその展開式で捉えることで foldl' の動作を理解することができる。

もう一つの本題は、無限リストを引き数に持つ foldr の使い方だ。たとえば、次の foldr はリストの要素を２倍にしたリストを返す。

Prelude Data.List> foldr (\x y -> (x * 2) : y) [] [1,2,3]
[2,4,6]

これは foldr が次のように展開されるのをみると納得できる。

foldr (\x y -> (x * 2) : y) [] [1,2,3]
= (1*2) : ((2 * 2) : ((3 * 2) : []))

この展開の様子をみると、foldr の引き数 [1,2,3] が無限リスト [1..] でも使えることが分かる。遅延評価されるので先頭部分のリストを take 関数で切り取ればいいのだ。

Prelude Data.List> take 5 $ foldr (\x y -> (x * 2) : y) [] [1..]
[2,4,6,8,10]

このように、foldr が右再帰関数、foldl が左再帰関数と考え、これらの関数をその展開式で捉えれば、foldl' や foldr の無限リストへの関数適用など、理解しづらい関数の使い方がつかみやすくなる。

Haskell のプログラミングが難しく感じるのは、標準の関数に抽象的なものが多いからだ。抽象的な関数は folds でもわかるようにイメージを作るのが難しい。しかし、一旦イメージができると、様々な用途に活用できてコンパクトなコードを書けるようになる。抽象的な関数のイメージさえ作ることが出来れば、こんなに簡単にプログラムを書ける言語はない。