Fold (고차 함수)
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
Fold는 리스트의 각 요소를 결합하여 단일 값을 생성하는 고차 함수이다. 리스트의 쉼표를 특정 연산자로 대체하는 것으로 이해할 수 있으며, 왼쪽 또는 오른쪽으로 결합하는 방식에 따라 두 가지 주요 유형이 있다. 왼쪽 폴드는 초기 값과 리스트의 첫 번째 요소를 함수에 적용하고, 그 결과를 다음 요소와 함께 반복하며, 오른쪽 폴드는 리스트의 마지막 요소와 초기값을 함수에 적용하고, 그 결과를 이전 요소와 함께 반복한다.
Fold는 다양한 프로그래밍 언어에서 지원되며, 함수형 언어에서는 핵심 기능으로 제공된다. 또한 C#, C++, Java, Python, Ruby, JavaScript 등 객체 지향 및 스크립트 언어에서도 폴드와 유사한 기능을 찾아볼 수 있다. 폴드는 데이터 구조의 구조적 구성 요소를 함수와 값으로 대체하는 구조적 변환으로 볼 수 있으며, 다양한 자료형에 적용될 수 있다. 엄격한 평가와 지연 평가 환경에서의 평가 순서에 따라 효율성이 달라질 수 있으며, 다형성을 가지므로 다른 함수를 표현하는 데 사용될 수 있다.
더 읽어볼만한 페이지
- 고차 함수 - 커링
커링은 다수의 인수를 취하는 함수를 단일 인수를 취하는 함수들의 연속으로 변환하는 기법으로, 함수형 프로그래밍에서 다인수 함수를 분해하여 적용하는 방식이며, 논리학과 컴퓨터 과학에서 널리 활용되는 중요한 개념이다. - 고차 함수 - Map (고차 함수)
Map 고차 함수는 함수형 프로그래밍에서 컬렉션의 각 요소에 함수를 적용해 새로운 컬렉션을 생성하는 기능으로, Lisp에서 처음 소개된 후 다양한 언어에서 구현되어 요소별 연산을 간결하게 표현하며, 구현 방식과 기능은 언어별로 차이가 있다. - 재귀 - 무한 루프
무한 루프는 컴퓨터 프로그램에서 루프가 종료되지 않고 무한히 반복되는 현상으로, 프로그램 오류나 의도적인 경우에 발생하며 시스템 응답 불능을 초래하거나 특정 상황에서 사용되기도 한다. - 재귀 - 점화식
점화식은 수열의 각 항을 이전 항들의 함수로 표현하는 방정식으로, 피보나치 수열, 로지스틱 맵, 이항 계수 등의 예시가 있으며, 선형대수학이나 Z변환 등을 이용하여 풀고 다양한 분야에 응용된다.
| Fold (고차 함수) | |
|---|---|
| 개요 | |
| 종류 | 고차 함수 |
| 정의 | 리스트의 원소들을 결합하는 함수 |
| 활용 | 리스트 축소 데이터 집계 |
| 특징 | 재귀적 또는 반복적 연산 수행 |
| 함수형 프로그래밍 | |
| 중요성 | 함수형 프로그래밍에서 중요한 역할 수행 |
| 불변성 | 데이터 불변성을 유지하며 안전한 연산 가능 |
| 연산 방식 | |
| 기본 원리 | 초기값과 리스트의 각 원소를 순차적으로 함수에 적용하여 결과 누적 |
| 예시 | 리스트의 모든 숫자 합 계산 문자열 연결 |
| 프로그래밍 언어별 구현 | |
| 공통 기능 | 대부분의 함수형 프로그래밍 언어에서 제공 |
| 사용 예시 | Haskell의 `foldl`, `foldr` Scala의 `foldLeft`, `foldRight` Python의 `functools.reduce` |
| 장점 | |
| 코드 간결성 | 복잡한 로직을 간결하게 표현 가능 |
| 재사용성 | 다양한 데이터 타입과 연산에 적용 가능 |
| 단점 | |
| 가독성 | 초기 학습 곡선이 높고, 복잡한 연산 시 가독성 저하 가능 |
| 성능 | 잘못 사용 시 성능 저하 유발 가능 |
| 기타 | |
| 관련 개념 | map filter |
| 주의사항 | 초기값 설정 및 연산 순서에 주의해야 함 |
2. 역사적 배경
폴드의 개념은 함수형 프로그래밍 언어의 발전과 함께 나타났다.
리스트 `[1, 2, 3, 4, 5]`를 덧셈 연산자로 폴드하면 15가 되는데, 이는 리스트의 모든 원소의 합이다.[1] 이를 쉼표를 '+' 연산으로 대체하는 것으로 생각하면, `1 + 2 + 3 + 4 + 5`가 된다.[1]
3. 리스트에 관하여
'+' 연산은 결합 법칙이 성립하므로, 괄호의 배치에 관계없이 결과는 동일하다. 그러나 결합 법칙이 성립하지 않는 이진 함수에서는 원소들이 결합되는 순서가 최종 결과에 영향을 줄 수 있다. 리스트에 대해 폴드를 수행하는 방법에는 오른쪽 폴드와 왼쪽 폴드 두 가지가 있다.
이는 Haskell (프로그래밍 언어) 또는 프롤로그에서 이진 연산자가 오른쪽 결합 또는 왼쪽 결합을 하는 것에 해당한다. 오른쪽 폴드의 경우 합은 `1 + (2 + (3 + (4 + 5)))`와 같이, 왼쪽 폴드의 경우 `(((1 + 2) + 3) + 4) + 5`와 같이 괄호로 묶인다.
초기값을 사용하면 편리하다. 오른쪽 폴드는 리스트의 끝에, 왼쪽 폴드는 리스트의 첫 번째 원소와 처음에 결합되는 초기값을 갖는다. 덧셈의 경우 덧셈 항등원인 0을 초기값으로 선택하면, 오른쪽 폴드는 `1 + (2 + (3 + (4 + (5 + 0))))`, 왼쪽 폴드는 `((((0 + 1) + 2) + 3) + 4) + 5`가 된다. 곱셈의 항등원은 1이며, 이를 초기값으로 사용하면 `1 * 1 * 2 * 3 * 4 * 5 = 120 = 5!`가 된다.
3. 1. 선형 폴드
선형 폴드는 리스트의 각 요소를 순차적으로 처리하며, 연산을 왼쪽에서 오른쪽으로 (좌측 폴드, `foldl`) 또는 오른쪽에서 왼쪽으로 (우측 폴드, `foldr`) 수행한다.
예를 들어, 리스트 `[1, 2, 3, 4, 5]`를 덧셈 연산자로 폴드하면 15가 된다. 이는 리스트의 쉼표를 '+' 연산자로 대체하는 것과 유사하며, `1 + 2 + 3 + 4 + 5`가 된다.[1]
Haskell (프로그래밍 언어)에서 `foldl`과 `foldr` 함수는 다음과 같이 표현될 수 있다.
```haskell
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
```
```haskell
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
```
좌측 폴드는 꼬리 재귀 최적화가 가능하여 메모리 효율성이 높을 수 있지만, 무한 리스트에는 적용할 수 없다. 반면 우측 폴드는 게으른 계산을 이용하면 무한 리스트에도 적용 가능하지만, 꼬리 재귀 최적화가 어려워 메모리 효율성이 떨어질 수 있다.
게으른 계산을 사용하는 왼쪽 폴드의 경우, 새로운 초기 매개변수가 재귀 호출 전에 평가되지 않아 스택 오버플로를 유발할 수 있다. 이를 방지하기 위해 Haskell에서는 `foldl'` (작은따옴표, 'prime'으로 발음) 함수를 제공하여 재귀 호출 전에 초기 매개변수의 평가를 강제한다.
3. 2. 트리형 폴드
트리형 폴드는 리스트를 이진 트리 형태로 구성하여 연산을 수행한다. 각 노드에서 함수를 적용하여 부분 결과를 계산하고, 이를 상위 노드에서 다시 결합하는 방식으로 진행된다. 이항 연산 ''f''가 결합 법칙을 만족하면, 연산 방식의 세부 사항은 달라도 괄호 배치에 관계없이 같은 값을 가진다.[1]
함수가 마그마인 경우, 즉 타입이 대칭적이고(a → a → a), 결과 타입이 리스트 요소의 타입과 동일한 경우, 괄호를 임의의 방식으로 배치하여 중첩된 하위 표현식의 이진 트리를 만들 수 있다. 이는 ''f''가 비엄격적일 경우 효율성에 큰 영향을 줄 수 있다.[1]
선형 폴드는 노드 지향적이며 리스트의 각 노드에 대해 일관된 방식으로 작동하는 반면, 트리형 폴드는 전체 리스트 지향적이며 노드 ''그룹'' 전체에 대해 일관된 방식으로 작동한다.[1]
리스트는 유한 및 무한히 정의된 리스트 모두에 대해 트리 형태 방식으로 폴드될 수 있다. foldi 함수의 경우, ''무한히'' 정의된 리스트에서 실행이 중단되지 않도록 하려면 함수 f가 적어도 전부 또는 즉시 두 번째 인수의 값을 ''항상'' 요구해서는 안 된다.[1]
유한 목록의 경우, 합병 정렬은 트리 형태의 폴딩을 사용하여 정의할 수 있다.
3. 3. 비어 있지 않은 리스트를 위한 특별한 폴드
초기값이 필요 없는 경우, 비어 있지 않은 리스트에 대해 `foldl1`과 `foldr1`과 같은 함수를 사용할 수 있다. `foldl1`은 리스트의 첫 번째 요소를 초기값으로 사용하고, `foldr1`은 리스트의 마지막 요소를 초기값으로 사용한다.[1] 이러한 함수들은 초기값을 명시적으로 지정할 필요가 없어 편리하지만, 비어 있는 리스트에는 적용할 수 없다.
이러한 fold는 형식 대칭 이진 연산을 사용한다. 즉, 두 인수와 결과의 형식이 같아야 한다. Richard Bird는 2010년 저서에서[2] "비어 있지 않은 목록에 대한 일반적인 fold 함수" `foldrn`을 제안했는데, 이 함수는 추가 인수 함수를 적용하여 마지막 요소를 변환하여, fold 자체를 시작하기 전에 결과 형식의 값으로 변환한다. 따라서 일반적인 `foldr`과 같이 형식 비대칭 이진 연산을 사용하여 목록 요소 형식과 다른 형식의 결과를 생성할 수 있다.
```haskell
foldl1 f [x] = x
foldl1 f (x:y:xs) = foldl1 f (f x y : xs)
foldr1 f [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)
foldt1 f [x] = x
foldt1 f (x:y:xs) = foldt1 f (f x y : pairs f xs)
foldi1 f [x] = x
foldi1 f (x:xs) = f x (foldi1 f (pairs f xs))
4. 다양한 언어에서의 폴드
. initval,array
verb/ array,initvalverb/ arrayfoldl(op, itr; [init])foldr(op, itr; [init])foldl(op, itr)foldr(op, itr)Iterable.fold(initval, func)Iterable.foldRight(initval, func)Iterable.reduce(func)Iterable.reduceRight(func)fold_left(Closure, Initial, List, Result)fold_right(Closure, Initial, List, Result)foldl(func, initval, sequence)foldr(func, initval, sequence)Fold[func, initval, list]Fold[func, initval, Reverse[list]]Fold[func, list]Fold[func, Reverse[list]]NestWhileList[func,, initval, predicate]fold(@func, list, defaultVal)fold(@func, flip(list), defaultVal)fold(@func, list)fold(@func, flip(list))lreduce(func, list, initval)rreduce(func, list, initval)lreduce(func, list)rreduce(func, list)fold_left func initval list vector::fold_left func initval vectorfold_right func initval list vector::fold_right func initval vector{FoldL List Func InitVal}{FoldR List Func InitVal}fold( f, A )reduce block initval, listreduce block listarray_reduce(array, func, initval)array_reduce(array_reverse(array), func, initval)array_reduce(array, func)array_reduce(array_reverse(array), func)Reduce(func, list, initval)Reduce(func, list, initval, right=TRUE)Reduce(func, list)Reduce(func, list, right=TRUE)iterator.fold(initval, func)iterator.rev().fold(initval, func)aCollection inject: aValue into: aBlockaCollection reduce: aBlockarray.reduce(initval, func) reduce(sequence, initval, func)array.reverse().reduce(initval, func)iterable.fold(initval,[func])iterable.reduce[func]
