Fold (고차 함수)

함수형 프로그래밍에서 fold란 고차 함수의 계열 중 하나이다. reduce, accumulate, compress 혹은 inject 등 다양하게 알려져 있다. 재귀적인 자료 구조를 분석하고, 전달받은 결합된 명령들을 사용하여 재결합하며, 재귀적으로 수행된 그 결과들로 반환 값(return value)을 만들어낸다. 보통 fold는 함수를 자료 구조의 최상위 노드의 조합 함수의 형태로 표현되며, 특정 조건 하에서 사용할 수 있는 어떤 기본 값(default values)을 가질 수 있다. 그리고 계통적인 방식으로 그 함수를 사용하여 자료 구조의 위계 상의 요소들을 조합하는 과정을 진행한다.

언어	Left fold	Right fold	Left fold (초기값 없음)	Right fold (초기값 없음)	Unfold
APL	`func⍨/⌽initval,vector`	`func/vector,initval`	`func⍨/⌽vector`	`func/vector`
C# 3.0	`ienum.Aggregate(initval, func)`	`ienum.Reverse().Aggregate(initval, func)`	`ienum.Aggregate(func)`	`ienum.Reverse().Aggregate(func)`
C++	`std::accumulate(begin, end, initval, func)`	`std::accumulate(rbegin, rend, initval, func)`
C++17	`(initval op ... op pack)`	`(pack op ... op initval)`	`(... op pack)`	`(pack op ...)`
CFML	`obj.reduce(func,initial)`		`obj.reduce(func)`
Clojure	`(reduce func initval list)`	`(reduce func initval (reverse list'))`	`(reduce func list)`	`(reduce func" (reverse list))`
Common Lisp	`(reduce func list :initial-value initval)`	`(reduce func list :from-end t :initial-value initval)`	`(reduce func list)`	`(reduce func list :from-end t)`
Curl	`{{TreeNode.default treeNode ...} .to-Iterator}`	`{{TreeNode.default treeNode ...} .reverse}.to-Iterator}`	`{for {treeNode.to-Iterator} do}`	`{for {{treeNode.reverse}.to-Iterator} do}`
D	`reduce!func(initval, list)`	`reduce!func(initval, list.reverse)`	`reduce!func(list)`	`reduce!func(list.reverse)`
Elixir	`List.foldl(list, acc, fun)`	`List.foldr(list, acc, fun)`
Elm	`List.foldl(Fun, Accumulator, List)`	`List.foldr(Fun, Accumulator, List)`
Erlang	`lists:foldl(Fun, Accumulator, List)`	`lists:foldr(Fun, Accumulator, List)`
F#	`Seq/List.fold func initval list`	`List.foldBack func list initval`	`Seq/List.reduce func list`	`List.reduceBack func list`	`Seq.unfold func initval`
Gosu	`Iterable.fold(f(agg, e))Iterable.reduce(init, f(agg, e)) Iterable.partition(f(e))`
Groovy	`list.inject(initval, func)`	`list.reverse().inject(initval, func)`	`list.inject(func)`	`list.reverse().inject(func)`
Haskell	`foldl func initval list`	`foldr func initval list`	`foldl1 func list`	`foldr1 func list`	`unfoldr func initval`
Haxe	`Lambda.fold(iterable, func, initval)`
J	`verb~/\|. initval,array`	`verb/ array,initval`	`verb~/\|. array`	`verb/ array`
Java 8+	`stream.reduce(initval, func)`		`stream.reduce(func)`
JavaScript 1.8 ECMAScript 5	`array.reduce(func, initval)`		`array.reduce(func)`
Julia	`foldl(op, itr; [init])`	`foldr(op, itr; [init])`	`foldl(op, itr)`	`foldr(op, itr)`
Kotlin	`Iterable.fold(initval, func)`	`Iterable.foldRight(initval, func)`	`Iterable.reduce(func)`	`Iterable``.reduceRight(func)`
LFE	`(lists:foldl func accum list)`	`(lists:foldr func accum list)`
Logtalk	`fold_left(Closure, Initial, List, Result)`	`fold_right(Closure, Initial, List, Result)`
Maple	`foldl(func, initval, sequence)`	`foldr(func, initval, sequence)`
Mathematica	`Fold[func, initval, list]`	`Fold[func, initval, Reverse[list]]`	`Fold[func, list]`	`Fold[func, Reverse[list]]`	`NestWhileList[func,, initval, predicate]`
MATLAB	`fold(@func, list, defaultVal)`	`fold(@func, flip(list), defaultVal)`	`fold(@func, list)`	`fold(@func, flip(list))`
Maxima	`lreduce(func, list, initval)`	`rreduce(func, list, initval)`	`lreduce(func, list)`	`rreduce(func, list)`
Mythryl	`fold_left func initval list vector::fold_left func initval vector`	`fold_right func initval list vector::fold_right func initval vector`
OCaml	`List.fold_left func initval list Array.fold_left func initval array`	`List.fold_right func list initval Array.fold_right func array initval`			`Base.Sequence.unfold ~init ~f`^[1]
Oz	`{FoldL List Func InitVal}`	`{FoldR List Func InitVal}`
PARI/GP	`fold( f, A )`
Perl	`reduce block initval, list`		`reduce block list`
PHP	`array_reduce(array, func, initval)`	`array_reduce(array_reverse(array), func, initval)`	`array_reduce(array, func)`	`array_reduce(array_reverse(array), func)`
Python 2.x	`reduce(func, list, initval)`	`reduce(lambda x,y: func(y,x), reversed(list), initval)`	`reduce(func, list)`	`reduce(lambda x,y: func(y,x), reversed(list))`
Python 3.x	`functools.reduce(func, list, initval)`	`functools.reduce(lambda x,y: func(y,x), reversed(list), initval)`	`functools.reduce(func, list)`	`functools.reduce(lambda x,y: func(y,x), reversed(list))`
R	`Reduce(func, list, initval)`	`Reduce(func, list, initval, right=TRUE)`	`Reduce(func, list)`	`Reduce(func, list, right=TRUE)`
Ruby	`enum.inject(initval, &block) enum.reduce(initval, &block)`	`enum.reverse_each.inject(initval, &block) enum.reverse_each.reduce(initval, &block)`	`enum.inject(&block) enum.reduce(&block)`	`enum.reverse_each.inject(&block) enum.reverse_each.reduce(&block)`
Rust	`iterator.fold(initval, func)`	`iterator.rev().fold(initval, func)`
Scala	`list.foldLeft(initval)(func)` `(initval /: list)(func)`	`list.foldRight(initval)(func)` `(list :\ initval)(func)`	`list.reduceLeft(func)`	`list.reduceRight(func)`
Scheme R⁶RS	`(fold-left func initval list) (vector-fold func initval vector)`	`(fold-right func initval list) (vector-fold-right func initval vector)`	`(reduce-left func defaultval list)`	`(reduce-right func defaultval list)`	`(unfold p f g seed [tail-gen])` `unfold-right p f g seed [tail]` `(vector-unfold f length initial-seed ···)` `(vector-unfold-right f length initial-seed ···)`
스몰토크	`aCollection inject: aValue into: aBlock`		`aCollection reduce: aBlock`
Standard ML	`foldl func initval list Array.foldl func initval array`	`foldr func initval list Array.foldr func initval array`
Swift	`array.reduce(initval, func) reduce(sequence, initval, func)`	`array.reverse().reduce(initval, func)`
XPath 3.1	array:fold-left( $array as array(), $zero as item(), $f as function( item(), item() } as item()* ) as item()* ^[2] fn:fold-left( $seq as item(), $zero as item(), $f as function( item(), item() ) as item() ) as item()* ^[3]	array:fold-right( $array as array(), $zero as item(), $f as function( item(), item() } as item()* ) as item()* ^[4] fn:fold-right( $seq as item(), $zero as item(), $f as function( item(), item()* ) as item()* ) as item()* ^[5]
Xtend	`iterable.fold(initval,[func])`		`iterable.reduce[func]`

Fold (고차 함수)

언어별 비교

같이 보기

각주

Wikiwand - on