ニコニコ大百科モバイル

7/2(月)よりスマホまたはPCでアクセスした場合、各デバイス向けのサイトへ自動で転送致します


重畳関数


ヨミ: ジュウジョウカンスウ
掲示板をミル!
3カキコ!

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


概要


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

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

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

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

fold(ini, list, f): ini は初期値、list は a1, a2, ..., an からなるリスト、f は関数 であるとき、

r1 = f(ini, a1), r2 = f(r1, a2), r3 = f(r2, a3), ..., rn = f(rn-1, an)とするとfold(ini, list, f) = rnである。



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

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

r1 = f(0, 1) = 0 + 1, r2 = f(r1, 2) = 0 + 1 + 2, r3 = f(r2, 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の結果は等しくなるが、関数の種類によっては答えが変わってくる。


関連項目



最終更新日: 17/06/18 08:53
タグ検索 パソコン版を見る


[0]TOP
ニコニコ動画モバイル
運営元:ドワンゴ