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
 
 .''}
 {for {treeNode''.}'' ''do}''
 {for '' ''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
 }
 }
 Xtend
 ''iterable''.fold(''initval'',''func'')
 ''iterable''.reduce''func''
* 준동형
* Map (고차 함수)
* 재귀 (컴퓨터 과학)
분류:고차 함수
분류:재귀