함자(Functor)

목록의 모든 원소에 같은 함수를 적용하는 일을 프로그래밍에서는 map이라 합니다. f(x) = x + 1이면 map f [3, 1, 4] = [4, 2, 5]입니다. map은 '수를 수로 보내는 함수' f를 받아 '수의 목록을 수의 목록으로 보내는 함수' map f를 만듭니다. 그리고 두 규칙을 지킵니다. 아무것도 하지 않는 함수를 map하면 아무것도 하지 않고(map id = id), 두 함수를 이어 붙인 뒤 map하든 따로 map한 뒤 이어 붙이든 같습니다. g(x) = 2x라 하면 map (g∘f) [3, 1, 4] = [8, 4, 10]이고, map g (map f [3, 1, 4]) = map g [4, 2, 5] = [8, 4, 10]입니다. 목록을 두 번 훑든 한 번 훑든 결과가 같다는 뜻입니다.

이것을 일반화한 것이 함자(functor)입니다. 범주 𝒞에서 𝒟로 가는 함자 F는 𝒞의 대상 A마다 𝒟의 대상 F(A)를, 화살표 $f: A\to B$마다 화살표 $F(f): F(A)\to F(B)$를 정하되

$$F(\mathrm{id}_A) = \mathrm{id}_{F(A)},\qquad F(g\circ f) = F(g)\circ F(f)$$

를 지키는 것입니다. 목록은 집합⁠(set)⁠ A를 'A의 원소로 된 유한 목록 전체' List A로, 함수 f를 map f로 보내는, 집합의 범주에서 집합의 범주로 가는 함자입니다. 값이 하나 있거나 없는 상자 Maybe A도 함자입니다. 없는 값에 map하면 그대로 없음입니다. 함자는 구조를 지키며 옮기므로, 𝒞에서 가환하던 그림을 F로 옮기면 𝒟에서도 가환합니다. 두 길의 합성이 같으면 F를 씌운 두 합성도 같기 때문입니다.

순서도 범주이므로 순서 사이의 함자도 있습니다. 12의 약수⁠(divisor)⁠들을 나누어떨어짐으로 이은 범주에서 자기 자신으로 가는 사상을 생각해 봅시다. 화살표 a → b(a가 b를 나눔)는 화살표 F(a) → F(b)(F(a)가 F(b)를 나눔)로 가야 합니다. 순서에서는 두 대상 사이에 화살표가 많아야 하나라서 합성과 항등 화살표의 조건은 저절로 성립하고, 남는 조건은 '화살표가 있으면 옮긴 곳에도 화살표가 있다', 곧 단조성 하나입니다. 사상: . 왼쪽 점을 누르면 그 수가 가는 곳을 바꿀 수 있습니다.

그림의 일곱 화살표만 확인하면 충분하다는 데 주목하세요. 1 → 12 같은 다른 화살표는 이 일곱 개의 합성이고, 함자는 합성을 지키므로 합성된 화살표는 저절로 옮겨집니다. 두 수가 같은 곳으로 가면 그 사이의 화살표는 항등 화살표로 갑니다. 12/n으로 보내는 사상은 모든 화살표를 거꾸로 보냅니다(a | b이면 12/b | 12/a). 방향을 뒤집어 합성 순서도 뒤집는 사상을 반변 함자(contravariant functor)라 하는데, 행렬⁠(matrix)⁠의 전치가 그 예입니다. 전치는 m×n 행렬을 n×m 행렬로 보내므로 화살표의 방향이 바뀌고, $(AB)^{\mathsf T} = B^{\mathsf T}A^{\mathsf T}$처럼 곱의 순서도 바뀝니다.

함자의 가장 중요한 성질은 동형⁠(isomorphism)⁠을 동형으로 보낸다는 것입니다. $g\circ f = \mathrm{id}$이면 $F(g)\circ F(f) = F(g\circ f) = F(\mathrm{id}) = \mathrm{id}$이고, $f\circ g = \mathrm{id}$ 쪽도 똑같기 때문입니다. 뒤집어 읽으면, F(X)와 F(Y)가 동형이 아니면 X와 Y도 동형이 아닙니다. 불변량⁠(invariant)⁠은 이렇게 일합니다. 푸앵카레가 1895년 도입한 기본군은, 기준점을 정한 위상 공간⁠(topological space)⁠마다 '기준점에서 출발해 돌아오는 고리들을, 연속적으로 변형해 겹칠 수 있는 것끼리 같게 본 것'의 군을 붙이고, 기준점을 기준점으로 보내는 연속 함수마다 군 준동형⁠(homomorphism)⁠을 붙이는 함자입니다. 원주의 기본군은 정수⁠(integer)⁠ ℤ(몇 바퀴 감았는가)이고, 원판의 기본군은 원소가 하나뿐인 군입니다.

이 함자로 고정점⁠(fixed point)⁠ 정리를 증명할 수 있습니다. 2차원 브라우어르 고정점 정리⁠(Brouwer fixed-point theorem)⁠는 원판에서 원판으로 가는 모든 연속 함수 f에 f(x) = x인 점이 있다는 정리입니다. 고정점이 없다고 해 봅시다. 그러면 점마다 f(x)에서 x 쪽으로 반직선을 그어 원주와 만나는 점을 r(x)라 할 수 있고, r은 원판에서 원주로 가는 연속 함수이며 원주 위의 점은 제자리에 둡니다. 원주를 원판에 넣는 함수를 i라 하면 $r\circ i = \mathrm{id}$입니다. 기본군 함자를 씌우면 $\pi_1(r)\circ\pi_1(i) = \mathrm{id}_{\mathbb Z}$인데, 이 합성은 원소 하나짜리 군을 거쳐 가므로 모든 정수를 0으로 보냅니다. ℤ의 항등 사상이 그럴 수는 없으니 모순입니다. 위상수학⁠(topology)⁠의 질문(그런 연속 함수가 있는가)이 대수의 질문(그런 준동형이 있는가)으로 바뀌어 풀린 것입니다.

함자는 흔합니다. 군에서 연산을 잊고 원소의 집합만 남기는 '잊는 함자⁠(forgetful functor)⁠' Grp → Set, 집합을 멱집합⁠(power set)⁠으로 보내고 함수를 '상(image)을 구하는 함수'로 보내는 함자, 대상이 하나인 범주로 본 모노이드⁠(monoid)⁠ 사이의 준동형이 모두 함자입니다. 가역 행렬들의 곱셈 군에서 0이 아닌 실수⁠(real number)⁠들의 곱셈 군으로 가는 행렬식⁠(determinant)⁠도 그렇습니다(det AB = det A · det B, det I = 1). 함자끼리는 합성할 수 있고 항등 함자가 있으므로, 범주들을 대상으로, 함자들을 화살표로 두면 범주들의 범주가 생깁니다. 다만 모든 범주를 모으면 러셀의 역설⁠(Russell's paradox)⁠과 같은 크기 문제가 생기므로, 대상과 화살표가 집합을 이루는 '작은' 범주들만 모아 Cat이라 부릅니다.

흔한 오해 하나를 짚어 둡니다. 프로그래밍에서 함자를 '값을 담는 상자'로 설명하곤 하는데, 핵심은 상자가 아니라 map이 지키는 두 법칙입니다. 이 법칙은 컴파일러⁠(compiler)⁠가 확인해 주지 않습니다. 예를 들어 map할 때마다 목록을 뒤집는 연산은 타입⁠(type)⁠은 맞지만 map id가 항등이 아니므로 함자가 아닙니다. 거꾸로 상자처럼 보이지 않는 것도 함자입니다. 타입 r을 하나 정해 두면, 'r을 받아 A를 돌려주는 함수'들의 모임은, 함수 f를 뒤에 합성하는 연산으로 map하면 함자입니다.

이어지는 곳. 같은 두 범주 사이의 두 함자를 잇는 사상이 자연 변환⁠(natural transformation)⁠이고, 목록의 첫 원소를 꺼내는 함수가 그 예입니다. 어떤 함자가 한 대상의 화살표들과 같은 모양인지 묻는 것이 요네다 보조정리⁠(Yoneda lemma)⁠와 보편 성질⁠(universal property)⁠의 핵심이고, 서로 반대 방향으로 가며 짝을 이루는 두 함자가 수반 함자⁠(adjoint functor)⁠입니다. 자기 자신으로 가는 함자 가운데 '두 겹을 한 겹으로 펴는' 구조를 가진 것이 모나드⁠(monad)⁠입니다. 목록 함자는 대수적 자료형⁠(algebraic data type)⁠에서 재귀적으로 정의되는 타입의 대표적인 예이고, 모든 타입에 대해 똑같이 작동하는 map이 어떻게 가능한지는 다형성⁠(polymorphism)⁠에서 이어집니다. 기본군이 보여 준 '공간을 대수로 옮기기'는 위상수학과 표현 바꾸기에서 더 볼 수 있습니다. 공변⁠(covariant)⁠ 함자와 반변 함자⁠(contravariant functor)⁠의 구별은 프로그래밍에서 하위 타입⁠(subtype)⁠의 공변·반변⁠(contravariant)⁠으로 그대로 나타나고(하위 타입과 변성⁠(variance)⁠), 열린 집합⁠(open set)⁠들의 순서에서 집합의 범주로 가는 반변 함자가 층의 출발점인 준층입니다.