프로그래밍에서 맵과 리듀스
정의
맵
함수 $f : X \to Y$ 의 집합을 $F$ 라 하자. 다음과 같이 정의되는 고차 함수 $\text{map}$ 를 맵이라 한다. $$ \text{map} : F \times 2^{X} \to 2^{Y} \\ \text{map} \left( f , \left\{ x_{1} , \cdots , x_{n} \right\} \right) := \left\{ f \left( x_{1} \right) , \cdots, f \left( x_{n} \right) \right\} $$
폴드
함수 $g : X \to X$ 의 집합을 $G$ 라 하자. 다음과 같이 정의되는 고차 함수 $\text{fold}$ 를 폴드라 한다.
$$ \text{fold} : G \times 2^{X} \to X \\ \text{fold} \left( g , A \right) := g \left( x , \text{fold} \left( g , A \setminus \left\{ x \right\} \right) \right) \qquad , x \in A $$
설명
정의에 나온 수식은 그냥 수학하는 사람들이 이해하기 쉬우라고 적어놓은 것이니 너무 기겁하지 않길 바란다. 쉽게 말해 맵은 받은 배열의 원소 각각에 받은 함수를 다 취해주는 함수고, 폴드는 배열의 원소를 하나씩 빼서pop 주어진 함수를 계속해서 취해주는 함수다.
폴드의 수식이 어렵다면 위키백과의 설명을 참고해보자. 만만찮게 어려워서 수식이 쉬워보이는 효과가 있을 것이다.
함수형 프로그래밍에서 fold란 고차 함수의 계열 중 하나이다. reduce, accumulate, compress 혹은 inject 등 다양하게 알려져 있다. 재귀적인 자료 구조를 분석하고, 전달받은 결합된 명령들을 사용하여 재결합하며, 재귀적으로 수행된 그 결과들로 반환 값(return value)을 만들어낸다. 보통 fold는 함수를 자료 구조의 최상위 노드의 조합 함수의 형태로 표현되며, 특정 조건 하에서 사용할 수 있는 어떤 기본 값(default values)을 가질 수 있다. 그리고 계통적인 방식으로 그 함수를 사용하여 자료 구조의 위계 상의 요소들을 조합하는 과정을 진행한다.
맵과 폴드는 둘 다 함수를 인자로 받는 고차 함수고, 특히 폴드는 재귀함수다. 이 포스트의 제목이 그러하듯, 폴드는 보통 리듀스reduce로 불린다.
맵과 리듀스는 함수형 프로그래밍을 받아들임으로써 얻을 수 있는 이점 중 하나로 꼽히며, 하둡hadoop이나 분산 컴퓨팅 같은 곳에서 접할 수 있다. 성능이 떨어지지만 수가 많은 슬레이브slave 노드들 각각에서 데이터를 처리하고(Map) 그걸 마스터master 노드에서 수합해 요약하는(Reduce) 이미지를 떠올리면 된다.
예시
맵: 브로드캐스팅
프로그래밍 언어 중 하나인 줄리아에서는 맵을 일상적으로 사용하며, 맵을 네이티브하게 사용할 수 있는 문법을 브로드캐스팅broadcasting이라 부른다.
julia> A = [1,-2,3,-4]
4-element Vector{Int64}:
1
-2
3
-4
julia> f(x) = x^2
f (generic function with 1 method)
가령 위와 같은 배열 A와 함수 f()가 있다면, map()은 다음과 같이 배열의 각 원소마다 f를 취해준다.
julia> map(f, A)
4-element Vector{Int64}:
1
4
9
16
한편 같은 원리, 같은 결과지만 다음과 같이 f 뒤에 점 .을 찍어서 A의 원소에 포인트와이즈pointwise하게 f을 취하겠다고 할 수도 있다. 이것이 브로드캐스팅이다.
julia> f.(A)
4-element Vector{Int64}:
1
4
9
16
폴드: 리듀스
다른 말이 필요 없다. 직접 보면 한 번에 이해된다.
julia> reduce(+, A)
-2
$$ \text{reduce} (+,A) = -4 + (3 + ((-2) + 1)) = -2 $$
julia> reduce(max, A)
3
$$ \text{reduce} (\max,A) = \max(-4 , \max(3 , \max (-2 , 1))) = 3 $$