重畳関数

重畳関数とは、高階関数の一種である。関数型プログラミングでよく用いられる。

概要

関数名としてはfold, inject, reduceなどがよく用いられる。プログラミング言語により関数名の違いが大きい。畳み込みと呼ぶこともあるが、日本語では畳み込みは数学の違う計算を指すことがあるもよう。

初期値と、リストと、「引数を2つとる関数」を引数にとる。「引数を2つとる関数」は正確には「関数自身の戻り値と同じ型の引数と、リストの1要素を引数とする関数」である。

1. 初期値とリストの1番目の要素に関数を適用する。
2. 上記の戻り値とリストの2番目の要素に関数を適用する。
3. 上記の戻り値とリストの3番目の要素に関数を適用する。
4. これをリストの最後の要素まで繰り返し、最後に関数を適用した結果を戻り値として返す。

式で書くと以下のような感じである。

fold(ini, list, f): ini は初期値、list は a₁, a₂, ..., a_n からなるリスト、f は関数 であるとき、

r₁ = f(ini, a₁), r₂ = f(r₁, a₂), r₃ = f(r₂, a₃), ..., r_n = f(r_n-1, a_n)とするとfold(ini, list, f) = r_nである。

例

抽象的すぎてわかりづらい方のために簡単な例をあげると、「1からnまでの総和を求める関数」を重畳関数で表現することができる。

初期値を0、リストをnまでの自然数からなるリスト[1, 2, ..., n]、関数f(a, b) = a + b とすると、

r₁ = f(0, 1) = 0 + 1, r₂ = f(r₁, 2) = 0 + 1 + 2, r₃ = f(r₂, 3) = 0 + 1 + 2 + 3, ..., となり、fold(0, [1, 2, ..., n], f)が「1からnまでの総和」になることがわかる。

ちなみに初期値を1、f(a, b) = a × b とすると、n の階乗を求める関数に早変わりする。

具体例

さらにもう少し具体的に、上記の総和を求める例で n = 5 とすると、

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

ということであり、これを図示すると、下記のようになる。

初期値	リスト
0	[	1	,	2	,	3	,	4	,	5	]
0	+	1
		↓										0 + 1 = 1
		1	+	2
				↓								1 + 2 = 3
				3	+	3
						↓						3 + 3 = 6
						6	+	4
								↓				6 + 4 = 10
								10	+	5
										↓		10 + 5 = 15
										15	=	fold(0, [1, 2, 3, 4, 5], +)

このように、リストの要素が戻り値の中に畳み込まれていく(注入されていく)イメージからfold(あるいはinject)という関数名が用いられたり、複数の値からなるリストが要素数を「減らして」たった一つの値に集約されることからreduceという関数名が用いられると思われる。

逆順の重畳関数

リストの末尾から計算する重畳関数というものもある。fold_rightやreducerのように末尾にrightやrをつけて表現することが多い。また、これと区別するために先頭から計算する方をfoldlとかreduce_leftのような表現をすることもある。

上記具体例で言えば、

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

となる。足し算は交換法則や結合法則が成り立つのでfoldとfold_rightの結果は等しくなるが、関数の種類によっては答えが変わってくる。

関連項目

• 高階関数
• モノイド
• 関数型プログラミング / 関数型言語
• プログラミング関連用語の一覧
• 数学関連用語の一覧