Fold (고차 함수)

함수형 프로그래밍에서 **fold**란 고차 함수의 계열 중 하나이다. reduce, accumulate, compress 혹은 inject 등 다양하게 알려져 있다. 재귀적인 자료 구조를 분석하고, 전달받은 결합된 명령들을 사용하여 재결합하며, 재귀적으로 수행된 그 결과들로 반환 값(return value)을 만들어낸다. 보통 fold는 함수를 자료 구조의 최상위 노드의 조합 함수의 형태로 표현되며, 특정 조건 하에서 사용할 수 있는 어떤 기본 값(default values)을 가질 수 있다. 그리고 계통적인 방식으로 그 함수를 사용하여 자료 구조의 위계 상의 요소들을 조합하는 과정을 진행한다.
# 언어별 비교
{| class="wikitable" |- ! scope="col" | 언어 ! scope="col" | Left fold ! scope="col" | Right fold ! scope="col" | Left fold (초기값 없음) ! scope="col" | Right fold (초기값 없음) ! scope="col" | 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*`access-date = February 26, 2019 |- | 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*, *█*)
*enum*.reduce(*initval*, *█*)` | `*enum*.reverse_each.inject(*initval*, *█*)
*enum*.reverse_each.reduce(*initval*, *█*)` | `*enum*.inject(*█*)
*enum*.reduce(*█*)` | `*enum*.reverse_each.inject(*█*)
*enum*.reverse_each.reduce(*█*)` | |- | 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 R6RS | `(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 | sxhl|2=xquery| array:fold-left( $array as array(*), $zero as item()*, $f as function( item()*, item()* } as item()* ) as item()* *array*:fold-left fn:fold-left( $seq as item()*, $zero as item()*, $f as function( item()*, item() ) as item()* ) as item()*fold-left | sxhl|2=xquery| array:fold-right( $array as array(*), $zero as item()*, $f as function( item()*, item()* } as item()* ) as item()* *array*:fold-right fn:fold-right( $seq as item()*, $zero as item()*, $f as function( item(), item()* ) as item()* ) as item()*fold-right | | | |- | Xtend | `*iterable*.fold(*initval*,[*func*])` | | `*iterable*.reduce[*func*]` | | |}