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
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()* fn:fold-left( $seq as item()*, $zero as item()*, $f as function( item()*, item() ) as item()* ) as item()*	array:fold-right( $array as array(*), $zero as item()*, $f as function( item()*, item()* } as item()* ) as item()* fn:fold-right( $seq as item()*, $zero as item()*, $f as function( item(), item()* ) as item()* ) as item()*
Xtend	iterable.fold(initval,[func])		iterable.reduce[func]

같이 보기

• 준동형
• Map (고차 함수)
• 재귀 (컴퓨터 과학)