畳込関数fold

リストに関する処理は、以下のようなパターンで処理することが多いです。

f []     = v
f (x:xs) = x ● f xs

上記は関数fにリストを与えた時、次のような処理を行います。

リストが空の場合：値vが返される
リストが空でない場合：先頭要素xと関数fを残りのリストxsに適用した結果に対して、何らかの演算●を適用したものが返される

このようなパターンを簡潔に記述するために畳み込み(fold)と呼ばれる関数を使うことが出来ます。₁

例として、合計を取るsum関数の通常版とfold版を示します。ソースコードはHaskellです。

sumの通常版

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

sumのfold版

sum = foldr (+) 0

foldは次の入力を受け取り、出力を返します。

入力：
- ２引数関数
- アキュムレータの初期値
- 畳み込み対象のリスト
出力：
- 最終的なアキュムレータ

ここで、アキュムレータとは畳み込みに用いる値であり、sumのfold版の例では0が初期値になります。畳み込み関数の大まかな処理は以下のようになります。後述する右畳み込み、左畳み込みの図と合わせて読むと理解しやすいと思います。

2引数関数を以下の２つの引数で呼び出す：
- アキュムレータの値
- リストの先頭（あるいは最後）の要素
その結果を新しいアキュムレータとする
リストの次の要素を先頭（あるいは最後）とする
新しいアキュムレータとリストを使って、1.を繰り返す

畳み込みは右からでも左からでも可能です。

左畳み込み foldl (fold_left)

左畳み込みでは、リストの左側の要素から畳み込みを行っていきます。 sumのfoldl版を図で表すと以下のようになります（厳密ではありませんが、このような具合になると考えてください）。

f:id:succzero:20131207233749p:plain

ここで、入力と出力は以下のようになります。

入力：
- ２引数関数: +演算子
- アキュムレータの初期値: 0
- 畳み込み対象のリスト: [1,2,3]
出力：
- 最終的なアキュムレータ: 6

実際にfoldl関数を呼び出すときのコードは以下のようになります。

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

ただし、

sum = foldl (+) 0

と定義しておき、

sum [1,2,3]

という形で呼び出したほうが使い勝手が良いでしょう。これは部分適用と呼ばれるもので、関数の引数を一部分だけ指定したものを定義しておき、残りについては後から指定できるようになるものです。これによって、関数が再利用しやすくなります。

foldlは以下のように定義することができます。この定義と上図を見比べると、リストが空になるまでの過程がfoldl f v (x:xs) = foldl f (f v x) xsで、リストが空であるときの処理がfoldl f v [] = vであることが直感的に見て取れると思います。

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v []     = v
foldl f v (x:xs) = foldl f (f v x) xs

ここで、最初に示したリスト処理のパターンを再掲します。

f []     = v
f (x:xs) = x ● f xs

ここでのfはsum関数のような具体的な関数名を想定しており、●演算子は+や-等の具体的な２引数関数になります。具体的に置き換えると、sumの通常版になります。

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

このパターンと、前述したfoldlの定義とを見比べると、foldはリスト処理パターンを抽象的に定義したものであることが見て取れます。

右畳み込み foldr (fold_right)

右畳み込みでは、リストの右側から畳み込みを行っていきます。ただし、リストは左側からしか読めないため、結果的に見ると右側から畳み込んでいるようにみえる、ということです。これはfoldrが末尾再帰ではなく通常の再帰になっているため、「概念的には」下図のように、まず上から下に向かって計算式`f x (foldr f v xs)を展開していき、リストが空になった時点で、下から上に向かって展開した式を計算していくため、右側から畳み込んでいるようにみえるのです。（実際は遅延評価されますが、このような具合になると考えてください）

f:id:succzero:20131207233937p:plain

以下のfoldrの定義と図を見比べると動きがわかると重います。

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v []       = v
foldr f v (x:xs) = f x (foldr f v xs)

末尾再帰

再帰関数は自分自身を呼び出すような関数ですが、中でも末尾再帰はその関数の最後のステップが自身の呼び出しになっているものを指します。 foldlはfoldl f (f v x) xsとなっており、(f v x)の部分を先に計算して結果をv2すると、最後に残るのはfoldl f v2 xs という自分自身の呼び出しになります。一方、foldrは、f x (foldr f v xs)となっており、(foldr f v xs)の部分を計算してv2とすると、最後に残るのはf x v2となり自分自身ではありません。この残りを覚えておくためにスタックを用いる必要があります。このように、関数を呼び出した後にスタックに覚えておかなければならないような計算がないことを末尾呼び出し（tail call）といい、そのような再帰呼び出しになっていることを末尾再帰といいます。

末尾再帰はスタックが不要になるだけでなく、コンパイラによってはループとしてコンパイルされるため高速になるというメリットもあります。

foldlとfoldrの違いと使い分け

foldlとfoldrは、畳み込みの方向と末尾再帰か否かという点が大きく異なります。スタックを消費しない末尾再帰であるfoldlのほうが良さそうに見えますが、リストから新しいリストを構成するような処理の場合、リストは左方向にしか伸ばせないためfoldrのほうが有利なことがあります。また、foldrでは無限リストを扱えるという特徴もあります。

参考のため、左畳み込みと右畳み込みの関数と型を載せておきます。

畳み込みの方向	関数名	型
右	foldr	(a -> b -> b) -> b -> [a] -> b
左	foldl	(a -> b -> a) -> a -> [b] -> a

リストから新しいリストを構成するケースではfoldrのほうが有利

右畳み込みのほうが有利になるケースとして、map関数を自作してみます。 map関数はリストと関数が与えられた時、その関数をリストの要素１つ１つに適用していき、その結果を新たなリストとして返すものです。まずfoldrを使って定義したmap関数です。

mapr f xs = foldr (\x acc -> (f x) : acc) [] xs

関数fとリストxsを受け取り、xsの先頭要素を２引数関数のxに束縛、初期アキュムレータである空リスト[]を２引数関数のaccに束縛し、fをxに適用した結果をaccに連結させていきます。２引数関数の中身は畳み込むときに計算されていき、そのおかげでリストの右側の要素から処理されていくのでした。このおかげで、結果となるリストは元のリストと順番が同じになります。なお、foldrの２引数関数は以下の順序で引数を取ります。 - 第一引数：リストの先頭要素 - 第二引数：アキュムレータ

次はfoldを使ったmap関数をみてみましょう。

mapl f xs = foldl (\acc x -> acc ++ [f x]) [] xs

foldlの２引数関数は以下の順序で引数を取ります。 - 第一引数：アキュムレータ - 第二引数：リストの先頭要素 foldrのときとは順番が逆になっているのがわかると思います。

ここで++という演算子が現れています。コンス(:)演算子が要素とリストを結合するのに対し、++はリストとリストを結合するものです。このため、左側に空リストがきても結合ができます。使い方のイメージは以下のようになります。

[] ++ [1]
=> [1]
(([] ++ [1]) ++ [2])
=> [1, 2]
((([] ++ [1]) ++ [2]) ++ [3])
=> [1, 2, 3]

ただし、コンスに比べ、リスト同士の結合はパフォーマンスが悪いため、このようなケースではスタックの消費が許されるならfoldrを使ったほうがよいかもしれません。なお、リストの要素の順番を反転させるような場合はfoldlの方が有利です。

rev :: [a] -> [a]
rev = foldl (\acc x -> x : acc) []

rev [1,2,3]
=> [3,2,1]

無限リストをfoldrで扱う(foldlでは扱えない)

Haskellではリストは遅延評価されるため、foldrであれば無限リストを扱うことができます。

foldr (\x acc -> x * 2 : acc) [] [1..]
=> [2,4,6,8,10,12,14,16,18,20...

[1..] というのは[1,2,3,..と続く無限のリストを表します。上記ではこの無限のリストに対して、それぞれの要素を２倍にしたリストを返すということを行っています。

しかし、すべての２引数関数で無限リストが使えるわけではありません。どのような演算なら無限リストが扱えるようになるのでしょうか？

ここで先ほど言ったfoldlとfoldrの計算順序の話は忘れてください（笑）。Haskellは遅延評価を特徴とする言語です。すごく大雑把に言うと外側から評価していきます。参考文献にあるfoldl, foldrの簡潔な表現をみていきます。

foldl (●) v [x0,x1,...,xn] = (...((v ● x0) ● x1) ...) ● xn
foldr (●) v [x0,x1,...,xn] = x0 ● (x1 ● (... (xn ● v)...))

リストの要素が無限にある場合、外側から見ていくとfoldlは内側の(v ● x0)に到達できないことが分かります。一方、foldrは外側にあるx0の部分は計算できそうです。その結果をv0とすると、v0 ● (x1 ● (...と続くので、次はx1を計算してv1とします。このように計算していくと、v0 ● (v1 ● (v2 ● ... と計算が行えるので、●の中身によってはうまく結果を取り出せそうです。 ●が&&であった場合を考えます。&&の定義は以下のようになっています。

True  && x = x
False && _ = False

特に左側がFalseの場合、右側を無視しているところに注目です。ここで、さきほどのv0がFalseであった場合、残りの(x1 ● (x2 ● ... は無視されるため無限リストが対象であっても結果が得られるというわけです。また、先ほど示したfoldr (\x acc -> x * 2 : acc) [] [1..]という式は、●の中身が(\x acc -> x * 2 : acc)となっています。この演算なら、無限リスト内のすべての要素が評価し終わるまで計算できないということは無いため、随時計算していくことができます。 ●を(\x acc -> x * 2 : acc)とすると、