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'))</code>
| (reduce func list)
| <code>(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}.} {for {treeNode.} do} {for {{treeNode.reverse}.} 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.8ECMAScript 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 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 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 array:fold-left

fold-left array:fold-right

fold-right Xtend iterable.fold(initval,[func]) iterable.reduce[func]

 같이 보기 
 준동형
 Map (고차 함수)
 재귀 (컴퓨터 과학)

 각주 

분류:고차 함수
분류:재귀