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 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(   $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]

같이 보기

[편집]

각주

[편집]
  1. ↑ “Base”. Jane Street Capital. 2019년 2월 26일에 확인함. 
  2. ↑ array:fold-left
  3. ↑ fold-left
  4. ↑ array:fold-right
  5. ↑ fold-right
원본 주소 "https://ko.wikipedia.org/w/index.php?title=Fold_(고차_함수)&oldid=39228580"