畳み込み関数の比較 (fold / accumulate / inject / reduce)
つーか、fold の弱点として、言語によって引数の順番がまちまちで、
jijixi's diary - fold, map, for-each この中から一つ選ぶとしたらどれ？
正直憶えきれないってのがあるんだよな。誰か対応表とか作ってくれんもんか。
確かにいろいろとややこしいのでまとめてみました。
いくつかの言語について大雑把に表にすると次のような感じ。
| 言語 | 関数 |
|---|---|
| Haskell, OCaml, Scheme, Erlang | foldl* f init items |
| C++ | accumulate(begin, end, init, f) |
| Ruby*, JavaScript | items.inject(init, f) |
| Python, Perl* | reduce(f, items [, init]) |
| 言語 | 畳み込む二項演算 |
|---|---|
| Scheme(SRFI)*, Erlang | f(item, acc) |
| その他 | f(acc, item) |
解説
fold-leftはこういう演算
(((init + x1) + x2) + x3)
fold-rightはこういう演算
(x1 + (x2 + (x3 + init)))
自分の中ではわりとHaskellが基準です。中置記法で考えるのがわかりやすいと思います。
- [x1, x2, x3, ...] はリスト/配列
- 上の + は任意の二項演算(関数)に置き変えられる。
- その二項演算が結合則を満たすならば，単位元を初期値にした fold-left と fold-right の結果が一致する。
以下各言語での使い方と加減算の例を。
Haskell
foldl
- 型: (a -> b -> a) -> a -> [b] -> a
- foldl f init items
- f acc item
- 結果を左側に溜める
foldl (+) 0 [1, 2, 3] -- 0 + 1 + 2 + 3 = 6 foldl (-) 7 [1, 2, 3] -- 7 - 1 - 2 - 3 = 1
foldr
- 型: (a -> b -> b) -> b -> [a] -> b
- foldr f init items
- foldlと同じ
- f item acc
- foldlと逆で、右側に溜める
foldr (+) 0 [1, 2, 3] -- 1 + (2 + (3 + 0)) = 6 foldr (-) 7 [1, 2, 3] -- 1 - (2 - (3 - 7)) = -5
その他
foldl1, foldr1 はそれぞれの初期値無し版
- foldl1だとこんな感じ → (((x1 + x2) + x3) + x4)
- 空リストで例外発生
scanl/scanl1/scanr/scanr1 は畳み込み途中の値をリスト化する。
OCaml
fold_left
- 型: ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
- fold_left f init items
- f acc item
- Haskell の foldl と同じ
List.fold_left (+) 0 [1; 2; 3] (* 0 + 1 + 2 + 3 *) List.fold_left (-) 7 [1; 2; 3] (* 7 - 1 - 2 - 3 *)
fold_right
- 型: ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
- fold_right f items init
- items と init が fold_left と逆
- f item acc
- Haskellと同じく、右側に溜める
- (items,init) の順序 = (item,acc) の順序
List.fold_right (+) [1; 2; 3] 0 (* 1 + (2 + (3 + 0))) *) List.fold_right (-) [1; 2; 3] 7 (* 1 - (2 - (3 - 7))) *)
その他
fold_left2, fold_right2 は3項演算用。リストを二つ引数に取る。
Scheme(SRFI)
fold
- (fold f init items1 items2 ...)
- (f item acc)
- Haskell/OCamlやSICPにあるfold-leftとは挙動が違う
- f が結果を右側に貯める(cons的な引数の取り方をする)
- (x3 + (x2 + (x1 + init)))
- リストを複数渡せる → 全部appendしたような挙動
(fold + 0 '(1 2 3)) ; 3 + (2 + (1 + 0)) (fold - 7 '(1 2 3)) ; 3 - (2 - (1 - 7))
Gauche では組み込み．
fold-right
- (fold-right f init items1 items2 ...)
- (f item acc)
- Haskellと同じ
(fold-right + 0 '(1 2 3)) ; 1 + (2 + (3 + 0)) (fold-right - 7 '(1 2 3)) ; 1 - (2 - (3 - 7))
その他
- reduce
- リストが空ならデフォルト値、そうでなければ初期値無しfold。
- pair-fold
- cdrをfoldしていく。こんな感じ → [x3] ++ ([x2, x3] ++ ([x1, x2, x3] ++ init))
等がある。
Erlang
listsのfoldl/foldr
名前はHaskell中身はSRFI.
foldl
- foldl(F, Init, Items)
- F(Item, Acc)
- Schemeのfoldと同じ。
lists:foldl(fun(Item, Acc) -> Item+Acc end, 0, [1, 2, 3]). lists:foldl(fun(Item, Acc) -> Item-Acc end, 7, [1, 2, 3]).
foldr
lists:foldr(fun(Item, Acc) -> Item+Acc end, 0, [1, 2, 3]). lists:foldr(fun(Item, Acc) -> Item-Acc end, 7, [1, 2, 3]).
追記
+演算子を直接渡すにはfun erlang:'+'/2として
lists:foldl(fun erlang:'+'/2, 0, [1,2,3]).
以下、手続き型っぽい言語。
多分全部結果を左に溜めていくfold-leftの挙動をすると思う。
C++
- TYPE accumulate(iterator begin, iterator end, TYPE init);
- TYPE accumulate(iterator end, iterator end, TYPE init, BinaryFunction f);
- TYPE f(TYPE acc, TYPE item);
- 初期値省略不可
- BinaryFunction はデフォルトで加算
- 入力と出力で型が全て一致するような演算についてのみ畳みこめる
#include <numeric> #include <functional> int ary[] = {1, 2, 3}; std::accumulate(ary, ary+3, 0); // 足し算が使われる std::accumulate(ary, ary+3, 7, std::minus<int>());
Ruby
- items.inject(init = self.first) {|acc, item| ... }
- 初期値省略可能(foldl1的な動作になる。空配列の時 nil が返る)
- 引数の順序はC++に似てる。(コレクション、初期値、関数)
[1, 2, 3].inject(0) {|acc, item| acc + item } [1, 2, 3].inject(7) {|acc, item| acc - item } # 7 - 1 - 2 - 3 [1, 2, 3].inject {|acc, item| acc - item } # 1 - 2 - 3
JavaScript
Prototype.js
- items.inject(init, f [, context])
- Rubyに似ている
- prototype.js v1.6.0 から context が optional引数として追加されてた
- f.bind(context) される
- f(acc, item [, index])
- indexが使用可能
// requires prototype.js [1, 2, 3].inject(0, function(acc, item) { return acc + item }); [1, 2, 3].inject(7, function(acc, item) { return acc - item }); // 7 - 0*1 - 1*2 - 2*3 [1, 2, 3].inject(7, function(acc, item, idx) { return acc - idx*item });
Python
- reduce(f, items[, init])
- f(acc, item)
- 初期値省略可能(foldl1的な動作になる。空リストの時TypeError)
reduce(labmda acc, item: acc+item, [1, 2, 3], 0) reduce(labmda acc, item: acc-item, [1, 2, 3], 7) reduce(labmda acc, item: acc-item, [1, 2, 3])
Perl
- reduce BLOCK LIST
- ブロック内で $a が acc, $b が item
- 初期値はリストの先頭に置けばよい
use List::Util; List::Util::reduce {$a + $b} 0, (1, 2, 3); List::Util::reduce {$a - $b} 7, (1, 2, 3); List::Util::reduce {$a - $b} 1, 2, 3;
