Map (고차 함수)

1. 개요

Map (고차 함수)는 주어진 함수를 입력 자료 구조의 각 요소에 적용하여 새로운 자료 구조를 생성하는 고차 함수이다. 기본적으로 입력 자료 구조와 동일한 크기 및 형태의 새로운 자료 구조를 반환하며, 함수형 프로그래밍 언어에서 유래되었다. 다양한 프로그래밍 언어에서 구현되며, C++, C#, Python, Ruby 등 절차적/객체 지향 언어에서도 매핑 함수 또는 유사한 기능을 제공한다. 맵 퓨전, 맵-폴드 퓨전 등의 최적화 기법을 통해 성능을 향상시킬 수 있으며, Haskell에서는 Functor 타입 클래스를 통해 일반화되어 다양한 데이터 구조에 적용될 수 있다.

2. 개념

매핑은 주어진 함수를 입력 자료 구조의 각 원소에 적용하여 새로운 값을 계산하고, 이를 모아 새로운 자료 구조를 생성하는 과정을 의미한다.

예를 들어 정수 목록 `[1, 2, 3, 4, 5]`가 있고 각 정수의 제곱을 계산하려 한다고 가정해 보자. 이를 위해 먼저 단일 숫자를 제곱하는 함수를 정의한 뒤, `map` 함수를 사용하여 각 요소에 해당 함수를 적용할 수 있다.

2.1. 기본 원리

`map` 함수는 정수 목록 `[1, 2, 3, 4, 5]`가 있을 때, 각 정수의 제곱을 계산하는 것과 같이 사용된다. 먼저, 단일 숫자를 제곱하는 함수를 정의한다. (다음은 Haskell로 나타낸 것이다.)

```haskell
square x = x * x
```

그런 다음 `map square [1, 2, 3, 4, 5]`를 호출하면 `[1, 4, 9, 16, 25]`가 생성된다. 이는 `map`이 목록 전체를 순회하며 각 요소에 `square` 함수를 적용했음을 보여준다.

위 그림은 정수 목록 `X = [0, 5, 8, 3, 2, 1]`에 대해 함수 $f(x)\; =\; x\; +\; 1$에 따라 새로운 목록 `X'`으로 매핑하는 각 단계를 시각적으로 보여준다.

`map` 함수는 Haskell의 기본 전주곡(즉, "표준 라이브러리")의 일부로 제공되며 다음과 같이 구현된다.

```haskell
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x : xs) = f x : map f xs

2.2. 함수형 프로그래밍

매핑은 함수형 프로그래밍의 핵심 개념 중 하나이며, 부작용(side effect) 없이 자료를 처리하는 데 사용된다. 고차 함수(higher-order function)를 사용하여 함수를 인자로 받거나 결과로 반환할 수 있다.

정수 목록 `[1, 2, 3, 4, 5]`가 있고 각 정수의 제곱을 계산한다고 가정해 보자. 이를 위해 먼저 단일 숫자를 제곱하는 함수를 정의한다. (다음은 Haskell로 나타낸 것이다).

```haskell
square x = x * x
```

그런 다음 다음을 호출한다.

```haskell
>>> map square [1, 2, 3, 4, 5]
```

그러면 `[1, 4, 9, 16, 25]`가 생성되는데, 이는 `map`이 전체 목록을 거치면서 각 요소에 함수 `square`를 적용했음을 보여준다.

Haskell에서, 다형 함수 `map :: (a -> b) -> [a] -> [b]`는 다형적 함수 `fmap :: Functor f => (a -> b) -> f a -> f b`로 일반화되는데, 이는 `Functor` 타입 클래스에 속하는 모든 타입에 적용된다.

리스트의 타입 생성자 `[]`는 이전 예제의 `map` 함수를 사용하여 `Functor` 타입 클래스의 인스턴스로 정의할 수 있다.

```haskell
instance Functor [] where
fmap = map
```

`Functor` 인스턴스의 다른 예로는 트리가 있다.

```haskell
-- 간단한 이진 트리
data Tree a = Leaf a | Fork (Tree a) (Tree a)

instance Functor Tree where
fmap f (Leaf x) = Leaf (f x)
fmap f (Fork l r) = Fork (fmap f l) (fmap f r)
```

트리에 매핑하면 다음과 같은 결과가 생성된다.

```haskell
>>> fmap square (Fork (Fork (Leaf 1) (Leaf 2)) (Fork (Leaf 3) (Leaf 4)))
Fork (Fork (Leaf 1) (Leaf 4)) (Fork (Leaf 9) (Leaf 16))
```

`Functor` 타입 클래스의 모든 인스턴스에 대해, `fmap`은 펀터 법칙을 준수해야 한다.

```haskell
fmap id ≡ id -- 항등 법칙
fmap (f . g) ≡ fmap f . fmap g -- 합성 법칙
```
여기서 `.`는 Haskell의 함수 합성을 나타낸다.

이것은 무엇보다도 다양한 종류의 컬렉션에 대한 요소별 연산을 정의할 수 있게 해준다.

3. 언어별 구현 및 비교

map 함수는 함수형 프로그래밍 언어에서 유래되었다. 오늘날에는 많은 절차적, 객체 지향, 다중 패러다임 언어에서도 지원되거나 정의될 수 있다.

Lisp는 1959년에 `maplist`라는 함수를 도입했으며, 1958년에는 약간 다른 버전이 이미 등장했다. Common Lisp와 같은 최신 Lisp에서는 `maplist` 대신 `mapcar` 또는 더 일반적인 `map` 함수를 사용하는 것이 일반적이다.

C++의 표준 라이브러리에서는 `std::transform`, C# (3.0)의 LINQ 라이브러리에서는 `Select`라는 확장 메서드로 제공된다. 콜드퓨전 마크업 언어 (CFML), Perl, Python, Ruby와 같은 고급 언어에서도 `map`이라는 이름으로 자주 사용되며, Ruby에서는 `collect`라는 별칭도 제공된다 (Smalltalk에서 유래).

2개 이상의 목록에서 해당하는 요소에 함수를 적용하는 기능(예: `map2`, `zipWith`)을 제공하는 언어도 있다. 목록의 길이가 다른 경우, 언어마다 처리 방식이 다르다. 예외를 발생시키거나, 가장 짧은 목록을 기준으로 중지하거나, 가장 긴 목록까지 진행하며 값이 없는 경우 특정 값을 전달하는 방식 등이 있다.

1급 함수와 커링을 지원하는 언어에서 `map`은 단일 값에 작동하는 함수를 컨테이너 전체에 작동하는 함수로 만들 수 있다. 예를 들어, Haskell에서 `map square`는 목록의 각 요소를 제곱하는 함수가 된다.

다음 표는 다양한 프로그래밍 언어에서의 map 함수 구현 및 다중 목록 매핑 방식을 비교한 것이다.

3.1. 함수형 언어

함수형 프로그래밍 언어에서 map 함수는 기본적으로 제공된다. Haskell, Lisp, Scheme, Clojure, Erlang, Elixir, F# 등 다양한 함수형 언어에서 찾아볼 수 있다.

3.1.1. Haskell

Haskell에서 정수 목록 `[1, 2, 3, 4, 5]`의 각 정수를 제곱하려면, 먼저 단일 숫자를 제곱하는 함수를 정의한다.


square x = x * x


그런 다음 `map` 함수를 호출한다.


>>> map square [1, 2, 3, 4, 5]


결과는 `[1, 4, 9, 16, 25]`이다. 이는 `map`이 목록 전체를 순회하며 각 요소에 `square` 함수를 적용했음을 보여준다.

Haskell에서 다형 함수 `map :: (a -> b) -> [a] -> [b]`는 `Functor` 타입 클래스에 속하는 모든 타입에 적용되는 다형적 함수 `fmap :: Functor f => (a -> b) -> f a -> f b`로 일반화된다.

리스트의 타입 생성자 `[]`는 `map` 함수를 사용하여 `Functor` 타입 클래스의 인스턴스로 정의할 수 있다.


instance Functor [] where
fmap = map


`Functor` 인스턴스의 다른 예로 트리가 있다.


-- 간단한 이진 트리
data Tree a = Leaf a | Fork (Tree a) (Tree a)

instance Functor Tree where
fmap f (Leaf x) = Leaf (f x)
fmap f (Fork l r) = Fork (fmap f l) (fmap f r)


트리에 매핑을 적용하면 다음과 같은 결과가 나타난다.


>>> fmap square (Fork (Fork (Leaf 1) (Leaf 2)) (Fork (Leaf 3) (Leaf 4)))
Fork (Fork (Leaf 1) (Leaf 4)) (Fork (Leaf 9) (Leaf 16))


`Functor` 타입 클래스의 모든 인스턴스에 대해, `fmap`은 펀터 법칙을 준수해야 한다.


fmap id ≡ id -- 항등 법칙
fmap (f . g) ≡ fmap f . fmap g -- 합성 법칙

여기서 `.`는 Haskell의 함수 합성을 나타낸다.

이는 다양한 종류의 컬렉션에 대한 요소별 연산을 정의할 수 있게 해준다.

3.1.2. Lisp

Lisp는 1959년에 `maplist`라는 map 함수를 도입했으며, 1958년에는 약간 다른 버전이 이미 등장했다. 다음은 `maplist`의 원래 정의로, 연속적인 나머지 목록에 함수를 매핑한다.

maplist[x;f] = [null[x] -> NIL;T -> cons[f[x];maplist[cdr[x];f]]]

`maplist` 함수는 Common Lisp와 같은 최신 Lisp에서도 사용할 수 있지만, `mapcar` 또는 더 일반적인 `map`과 같은 함수를 사용하는 것이 선호된다.

목록의 요소를 제곱하는 데 `maplist`를 사용하는 것은 S-표현식 표기법으로 다음과 같이 작성할 수 있다.


(maplist (lambda (l) (sqr (car l))) '(1 2 3 4 5))


`mapcar` 함수를 사용하면 위의 예제는 다음과 같이 표현할 수 있다.


(mapcar (function sqr) '(1 2 3 4 5))

3.2. 절차적/객체지향 언어

C++의 표준 라이브러리에서는 `std::transform`을 사용하며, C# (3.0)의 LINQ 라이브러리에서는 `Select`라는 확장 메서드로 제공된다. Python, Ruby와 같은 고급 언어에서도 `map`이라는 이름으로 매핑 연산을 지원한다. Ruby에서는 `collect`라는 `map`의 별칭도 제공된다.

3.2.1. C++

C++의 표준 라이브러리에서는 `std::transform`을 사용하여 매핑을 구현할 수 있다.

3.2.2. C#

C# (3.0)의 LINQ 라이브러리에서는 `Select`라는 확장 메서드로 매핑 기능을 제공한다.

3.2.3. Python

파이썬에서 `map` 함수는 주어진 함수를 리스트, 튜플 등 반복 가능한 자료 구조의 각 요소에 적용한다. Python 2에서는 `map` 함수가 목록을 반환했지만, Python 3에서는 반복자를 반환하도록 변경되었다.

기본적인 사용법은 다음과 같다.

```python
map(func, list)
```

두 개 이상의 목록에 대해서도 `map` 함수를 적용할 수 있다.

```python
map(func, list1, list2)
```

이때, 각 목록에서 동일한 위치에 있는 요소들이 함수의 인자로 전달된다.

`map` 함수는 여러 개의 목록을 인자로 받을 수 있다.

```python
map(func, list1, list2, ...)
```
이 경우, `func`에 전달되는 인자의 수는 목록의 수와 일치해야 한다.

길이가 다른 목록 처리

`zip()` 및 `map()` (Python 3.x)은 가장 짧은 목록이 끝나면 중지한다. 반면 `map()` (Python 2.x) 및 `itertools.zip_longest()` (Python 3.x)는 더 짧은 목록을 `None` 항목으로 확장한다.

3.2.4. Ruby

Ruby에서는 `map` 또는 `collect` 메서드를 사용하여 매핑을 수행할 수 있다. `map`의 별칭인 `collect`도 Ruby에서 제공된다 (Smalltalk에서 유래).

다음은 Ruby에서 `map` 메서드를 사용하는 예시이다.

```ruby
(1..5).map { |i| i * i } #=> [1, 4, 9, 16, 25]
```

2개 이상의 목록에 대해 `map`을 적용하려면, `zip` 메서드를 함께 사용할 수 있다.

```ruby
enum1.zip(enum2).map { |block| ... }
[enum1, enum2, ...].transpose.map { |block| ... }
```

`zip` 메서드는 호출된 객체(첫 번째 목록)의 끝에서 중지되며, 다른 목록이 더 짧으면 `nil` 항목으로 확장한다.

3.3. 기타 언어

Perl에서는 `map {block} list` 또는 `map expr, list` 형태로 map 함수를 사용한다. 이때, `block`이나 `expr` 내에서 특수 변수 `$_`는 목록의 각 값을 차례로 가진다. PHP에서는 `array_map(callable, array)` 형태로 사용하며, `callable`에 전달되는 인수의 수는 배열의 수와 일치해야 한다. 더 짧은 목록은 `NULL` 항목으로 확장된다.

R에서는 `lapply(list, func)` 형태로 사용하며, 2개 이상의 목록에 대해서는 `mapply(func, list1, list2, ...)`를 사용한다. 이때, 더 짧은 목록은 순환된다.

Swift에서는 `sequence.map(func)` 형태로 사용하며, 2개의 목록에 대해서는 `zip(sequence1, sequence2).map(func)`를 사용한다. 가장 짧은 목록의 길이에서 중지된다.

Scala에서는 `list.map(func)` 형태로 사용하며, 2개의 목록에 대해서는 `(list1, list2).zipped.map(func)`를 사용한다. 3개 이상의 목록에 대한 zipped.map은 불가능하며 가장 짧은 목록의 길이에서 중지된다.

3.4. 다중 목록 매핑

일부 프로그래밍 언어에서는 둘 이상의 목록에 대해 매핑을 수행하는 기능을 제공한다. 예를 들어, map2 또는 zipWith와 같은 특수 이름을 사용하기도 한다. 2개 이상의 목록이 있는 경우, 목록의 길이가 다르면 처리 방식이 각 언어마다 다르다.

* 어떤 언어들은 예외를 발생시킨다.
* 어떤 언어들은 가장 짧은 목록의 길이를 기준으로, 해당 길이를 초과하면 중지하고 다른 목록의 추가 항목은 무시한다.
* 어떤 언어들은 가장 긴 목록의 길이를 기준으로, 이미 종료된 목록에 대해서는 값이 없음을 나타내는 특정 자리 표시자 값을 함수에 전달한다.

다음은 여러 프로그래밍 언어에서 제공하는 다중 목록 매핑 방식이다.

4. 최적화

맵의 수학적 기반은 여러 가지 최적화를 가능하게 한다.

위의 단일 연결 리스트에 대한 맵 구현은 꼬리 재귀가 아니므로, 큰 리스트로 호출될 때 스택에 많은 프레임을 쌓을 수 있다. 많은 언어는 대안으로 "역 맵" 함수를 제공하는데, 이는 매핑된 리스트를 뒤집는 것과 동일하지만 꼬리 재귀이다. 다음은 접기-왼쪽 함수를 사용하는 구현이다.


reverseMap f = foldl (\ys x -> f x : ys) []


단일 연결 리스트를 뒤집는 것 또한 꼬리 재귀이므로, 역 맵과 뒤집기를 함께 사용하여 꼬리 재귀 방식으로 일반 맵을 수행할 수 있지만, 리스트를 두 번 반복해야 한다.

4.1. 맵 퓨전 (Map Fusion)

합성 법칙은 다음 두 가지가 동일한 결과를 낸다는 것을 보장한다.

* `(map f . map g) list`
* `map (f . g) list`

즉, $\backslash operatorname\{map\}(f)\; \backslash circ\; \backslash operatorname\{map\}(g)\; =\; \backslash operatorname\{map\}(f\; \backslash circ\; g)$이다. 하지만, 두 번째 형태가 첫 번째 형태보다 계산 효율성이 더 높다. 왜냐하면 각 `map`은 처음부터 전체 리스트를 다시 만들어야 하기 때문이다. 따라서, 컴파일러는 첫 번째 형태를 두 번째 형태로 변환하려고 시도한다. 이러한 유형의 최적화를 맵 퓨전이라고 하며, 이는 함수형 프로그래밍의 루프 퓨전과 유사하다.

4.2. 맵-폴드 퓨전 (Map-Fold Fusion)

`map` 함수는 접기 (예: `foldr`)를 사용하여 정의할 수 있으며, 종종 그렇게 정의된다. 이는 `foldr f z . map g`가 `foldr (f . g) z`와 동일한 map-fold 퓨전을 수행할 수 있음을 의미한다.

5. 일반화

Haskell에서, 다형 함수 `map :: (a -> b) -> [a] -> [b]`는 다형적 함수 `fmap :: Functor f => (a -> b) -> f a -> f b`로 일반화되는데, 이는 `Functor` 타입 클래스에 속하는 모든 타입에 적용된다.

리스트의 타입 생성자 `[]`는 `map` 함수를 사용하여 `Functor` 타입 클래스의 인스턴스로 정의할 수 있다.


instance Functor [] where
fmap = map


`Functor` 인스턴스의 다른 예로는 아래와 같은 간단한 이진 트리가 있다.


data Tree a = Leaf a | Fork (Tree a) (Tree a)

instance Functor Tree where
fmap f (Leaf x) = Leaf (f x)
fmap f (Fork l r) = Fork (fmap f l) (fmap f r)


트리에 맵핑하면 다음과 같은 결과가 생성된다.


>>> fmap square (Fork (Fork (Leaf 1) (Leaf 2)) (Fork (Leaf 3) (Leaf 4)))
Fork (Fork (Leaf 1) (Leaf 4)) (Fork (Leaf 9) (Leaf 16))


`Functor` 타입 클래스의 모든 인스턴스에 대해, `fmap`은 다음의 펀터 법칙을 준수해야 한다.


fmap id ≡ id -- 항등 법칙
fmap (f . g) ≡ fmap f . fmap g -- 합성 법칙

여기서 `.`는 Haskell의 함수 합성을 나타낸다.

이는 다양한 종류의 컬렉션에 대한 요소별 연산을 정의할 수 있게 해준다.

5.1. 범주론적 배경

범주론에서 함자(Functor)는 두 범주 사이의 사상(morphism)을 보존하는 구조이다. `Functor` 타입 클래스는 이러한 함자의 개념을 프로그래밍 언어에 도입한 것이다. 함자 법칙을 준수함으로써 요소별 연산을 다양한 종류의 컬렉션에 대해 정의할 수 있다.

Haskell에서, 다형 함수 `map :: (a -> b) -> [a] -> [b]`는 다형적 함수 `fmap :: Functor f => (a -> b) -> f a -> f b`로 일반화되는데, 이는 `Functor` 타입 클래스에 속하는 모든 타입에 적용된다.

데이터 유형의 우주를 함수를 사상으로 하는 범주 $Type$으로 해석하면, `Functor` 타입 클래스의 멤버인 타입 생성자 `F`는 함자의 객체 부분이고, `fmap :: (a -> b) -> F a -> F b`는 사상 부분이다.

함자 법칙은 다음과 같다.

* `fmap id ≡ id` (항등 법칙)
* `fmap (f . g) ≡ fmap f . fmap g` (합성 법칙)

여기서 `.`는 함수 합성을 나타낸다.

자연 변환(Natural Transformation)은 두 함자 사이의 변환을 나타내는 개념이다. 두 함자 $F,\; G\; :\; C\; \backslash rarr\; D$가 주어지면, 자연 변환 $\backslash eta\; :\; F\; \backslash rarr\; G$는 범주 $D$의 각 객체 $A$에 대해 하나의 사상 $\backslash eta\_A\; :\; FA\; \backslash rarr\; GA$의 모음으로 구성된다. 자연 변환은 `eta :: F a -> G a` 형식의 함수에 해당하며, 여기서 `a`는 보편적으로 정량화된 타입 변수이다.

6. 활용 예시

map 함수는 리스트의 각 원소에 특정 함수를 적용하는 데 사용된다. 예를 들어, `[1, 2, 3, 4, 5]`와 같은 정수 목록이 있을 때, 각 숫자를 제곱하는 경우를 생각해 볼 수 있다. 하스켈(Haskell)에서는 먼저 숫자를 제곱하는 함수를 정의한다.

```haskell
square x = x * x
```

그런 다음 `map` 함수를 사용하여 다음과 같이 각 숫자에 `square` 함수를 적용할 수 있다.

```haskell
>>> map square [1, 2, 3, 4, 5]
```

결과는 `[1, 4, 9, 16, 25]`가 된다. 이는 `map` 함수가 목록의 각 원소를 순회하며 `square` 함수를 적용했음을 보여준다.

정수 목록에 대한 매핑의 시각적 예시는 시각적 예시 섹션에서 확인할 수 있다.

6.1. 시각적 예시

정수 목록 `X = [0, 5, 8, 3, 2, 1]`에 대해 함수 $f(x)\; =\; x\; +\; 1$에 따라 새로운 목록 `X'`으로 매핑하는 각 단계를 시각적으로 표현하였다.