2024-06-01프로그래밍

[번역] 프로그래머를 위한 카테고리 이론 - 10. 자연 변환

필자는 지금까지 카테고리 사이의 구조를 보존하는 사상으로써의 펑터에 대해 이야기하였다. 펑터는 한 카테고리를 다른 카테고리에 포함(Embeds)한다. 이는 결국 펑터가 여러 대상을 하나로 합칠 수는 있지만, 절대 구조를 변형하지는 않는다는 것을 의미한다. 펑터에 대해 이해하는 방법 중 하나는 함자를 사용하여 하나의 카테고리를 다른 카테고리 내부에서 모델링해보는 것이다.

소스가 되는 카테고리는 대상이 될 카테고리의 일부인 구조적인 모델 또는 청사진 역할을 한다.

어떤 하나의 카테고리를 다른 카테고리에 포함시키는 방법에는 여러가지가 있을 수 있다. 대표적인 두 방법 중 하나의 방법은 소스 카테고리를 대상 카테고리가 가진 하나의 대상으로 축소시키는 방법, 그리고 다른 방법은 소스 카테고리의 각 대상을 대상 카테고리의 각 대상으로, 소스 카테고리의 각 사상을 대상 카테고리의 각 사상으로 매핑하는 방법이다. 즉, 같은 청사진이라고 해도 여러가지 방법으로 표현될 수 있다는 의미이다. 자연 변환은 이런 방법들을 비교하는 데 큰 도움이 된다. 자연 변환은 펑터들의 펑터적 성질을 보존해주는 특별한 사상이기 때문이다.

카테고리 $C$ 와 $D$ 를 매핑하는 두 개의 펑터 F와 G를 한번 상상해보자. $C$ 가 가진 하나의 대상인 a에 대해서 한번 생각해보자면, 이 펑터들은 두 개의 대상인 F a와 G a로 매핑될 것이다. 여기서 펑터들의 매핑이라는 말의 의미는 F a를 G a로 매핑하는 행위를 의미하는 것이다.

여기서 한 가지 유의해야할 점은 F a와 G a 모두 카테고리 $D$ 의 대상이라는 것이다. 동일한 카테고리 내의 대상들 사이의 매핑은 카테고리가 가진 특성을 위반해서는 안된다. 우리는 카테고리 $D$ 의 대상들 사이에 인위적인 연결을 만들어내는 것이 아니라, 그저 사상이라는 개념을 자연스럽게 이용하면 되는 것이다.

즉, 자연 변환은 a라는 대상으로 인해 발생할 수 있는 사상들 중 F a → G a와 같은 하나의 사상을 선택하는 것이라고 볼 수 있다. 이 자연 변환을 $α$ (알파: a가 아니다.)라고 부른다면 이 사상은 $α$ 의 성분 또는 $α_a$ (밑은 알파가 아닌 대상 a이다)라고 불린다.

α_a :: F a -> G a

여기서 우리가 신경써야 하는 점은 대상 a는 카테고리 $C$ 의 대상이고, 사상 $α_a$ 는 카테고리 $D$ 의 사상이라는 것이다.

만약 어떠한 대상 a를 기반으로 한 매핑 결과 F a와 G a 사이에 사상이 존재하지 않는다면, 펑터 F와 펑터 G 간의 자연 변환 또한 존재할 수 없다는 의미이다.

물론 이 이야기는 대상에 대한 이야기이므로 펑터가 만들어낼 수 있는 모든 케이스를 커버할 수 있는 것은 아니다. 왜냐하면 펑터들은 대상 뿐 아니라 사상 또한 매핑하기 때문이다. 그렇다면 사상들에 대해서는 자연 변환이 어떻게 작용하는 것일까?

한번 임의의 사상을 f라고 해보자. 사상들이 표현하는 매핑 행위는 고정되어있으니, F와 G 사이의 어떤 자연 변환에서도 F f는 반드시 G f로 변환되어야 한다.

이에 더해 펑터는 이 사상들의 매핑이 가진 특성을 보존해야한다는 제약을 가지고 있기 때문에 자연 변환의 정의 또한 이 제약에 얽매일 수 밖에 없다. 한번 카테고리 $C$ 가 가진 두 대상 a와 b 사이에 적용되는 사상 f를 생각해보자. 이 사상은 카테고리 $D$ 가 가진 두 개의 사상인 F f와 G f로 매핑될 것이다.

F f :: F a -> F b
G f :: G a -> G b

이때 자연 변환 $α$ 는 카테고리 $D$ 내의 다이어그램을 완성할 수 있는 두 개의 사상을 추가적으로 제공한다.

α_a :: F a -> G a
α_b :: F b -> G b

위 다이어그램을 보면 F a에서 G b로 가는 방법은 총 두 가지이다. 이 두 가지 방법이 동일한지 확인하려면 모든 f에 대해서 성립할 수 있는 자연성 조건을 부여해야한다.

G f ◦ α_a = α_b ◦ F f

이러한 자연성 조건은 매우 엄격한 제약이라고 볼 수 있다. 예를 들어 사상 F f가 가역적이라면 자연성 조건을 통해 $α_a$ 만 사용해서 $α_b$ 를 결정해버릴 수 있다. 아래와 같이 말이다.

α_b = (G f) ◦ α_a ◦ (F f)^-1

만약 두 대상 사이에 여러 개의 가역적인 사상들이 존재한다면, 이 변환들은 모두 이 조건을 만족시켜야한다. 즉, 자연성 조건이 보장되는 상황이라면 어떤 경로를 따라가더라도 결국 동일한 결과에 다다라야 한다는 것이다. 그러나 일반적으로 사상들이 가역적인 경우는 별로 없기 때문에, 두 펑터 간의 자연 변환이 존재한다는 것이 항상 보장되는 것은 아니라고 이야기한 것이다.

결과적으로는 이런 자연 변환을 통해 여러 펑터들이 작용하는 카테고리의 구조에 대한 많은 정보들을 표현해낼 수 있다. 추후 리미트와 요네다 보조정리에 대해 이야기할 때 이에 대한 몇 가지 예시를 다시 살펴볼 것이다.

자연 변환을 각 요소 별로 뜯어서 살펴보면 결국 대상을 사상으로 매핑하는 것이라고 말할 수 있다. 자연성 조건으로 인해 사상을 교차하는 사각형 다이어그램으로 매핑한다고 볼 수도 있다는 것이다. 즉, 카테고리 $C$ 가 가진 각각의 사상에 대해서 카테고리 $D$ 는 이 사상들을 교차하는 자연성 사각형 다이어그램을 가지고 있다.

자연 변환이 가진 이러한 성질은 카테고리적인 구성을 할 때 매우 유용하다. 카테고리적인 구성을 할 때 종종 교차 다이어그램이 포함되는 경우가 많은데, 이때 적절한 펑터를 선택함으로써 이러한 교차성 조건을 자연성 조건으로 변환할 수 있다. 이는 추후 극한(limits), 쌍대극한(colimits), 수반(Adjunctions)에 대한 예시를 다룰 때 더 자세히 살펴보도록 하겠다.

마지막으로 자연 변환은 펑터들의 동형사상을 정의하는 데에도 사용될 수 있다. 두 펑터가 자연적으로 동형이라고 말하는 것은 두 펑터가 거의 같다고 말하는 것과 동일한 말이다. 자연 동형성은 모든 요소가 동형사상인 자연 변환으로 정의된다.

10.1 다형성 함수(Polymorphic Functions)

지금까지 필자는 프로그래밍에서의 펑터(특히 엔도펑터)에 대해서 이야기해왔었다. 이 펑터는 타입을 다른 타입으로 매핑하는 타입 생성자에 해당한다. 또한 함수를 함수로 매핑하기도 하며, 이 매핑은 고계 함수 fmap에 의해 구현된다.

자연 변환을 구성하기 위해서는 대상, 여기서는 타입 a부터 시작한다. 펑터 F는 이 타입을 타입 F a로 매핑할 것이다. 그리고 또 다른 펑터 G는 이 타입을 G a로 매핑한다. 이때 alpha라는 자연 변환의 성분은 타입 a이며, 이것은 결국 F a에서 G a로 매핑되는 함수를 의미한다. 이것을 Haskell 의사코드로 표현해보면 아래와 같다.

alpha_a :: F a -> G a

자연 변환은 모든 타입 a에 대해 정의되는 다형성 함수라고 할 수 있다.

alpha :: forall a . F a -> G a

Haskell에서 forall 키워드는 선택적으로 사용할 수 있으며, 이 키워드를 사용하기 위해서는 ExplicitForAll 언어 확장을 활성화해야한다. 일반적으로는 아래와 같이 표현한다.

alpha :: F a -> G a

이 표현은 a에 의해 매개변수화된 함수라는 점에 주의하자. 이는 Haskell 구문의 간결함에 대한 또 다른 예시이기도 하다. 만약 C++에서 이와 유사한 구조를 표현하려면 약간 더 복잡해질 수 있다.

template<class A> G<A> alpha(F<A>);

Haskell에서의 다형성 함수와 C++의 일반적인 함수 사이에는 더 깊은 차이가 있으며, 이 차이는 이러한 함수들이 구현되고 타입 검사되는 방식에도 그대로 적용된다. Haskell의 다형성 함수는 모든 타입에 적용될 수 있도록 일관되게 정의되어야한다. 즉, 하나의 공식이 모든 타입에 대해 작동해야한다는 것이다. 이를 매개변수 다형성(Parametric polymorphism)이라고 한다.

C++은 기본적으로 특수 다형성(Ad hoc polymorphism)을 지원한다. 이는 어떤 하나의 템플릿이 반드시 모든 타입에 대해 적용될 수 있도록 정의될 필요는 없다는 것을 의미한다. 주어진 타입에 대해 템플릿이 적용될 수 있는지에 대한 여부는 인스턴스화 타임에 결정며, 이때 타입 매개변수가 구체적인 타입으로 대체된다. 이러한 과정 때문에 타입 검사가 느려지기도 하며, 가끔은 이해하기 어려운 에러 메시지를 만나기도 한다.

C++에는 함수 오버로딩이나 템플릿 특수화 같은 매커니즘도 존재한다. 이를 통해 하나의 함수가 각기 다른 타입에 맞춰 다른 정의를 제공할 수도 있다. Haskell에서는 이런 기능이 타입 클래스와 타입 패밀리를 통해 제공된다.

Haskell의 매개변수 다형성은 종종 예상치 못한 결과를 가져오기도 한다.

alpha :: F a -> G a

여기서 F와 G는 펑터이며 자연성 조건을 자동으로 만족한다. 이를 카테고리적 표기법으로 나타내면 다음과 같다. (f는 함수 f :: a -> b이다)

G f ◦ α_a = α_b ◦ F f

Haskell에서 펑터 G의 사상 f에 대한 작용은 fmap을 사용하여 구현된다. 먼저 명시적인 타입 주석을 사용하여 Haskell 의사 코드로 작성해보겠다.

fmap_G f . alpha_a = alpha_b . fmap_F f

사실 타입 추론 덕분에 이러한 주석들은 필요하지 않으며, 다음의 등식이 성립할 수 있게 된다.

fmap f . alpha = alpha . fmap f

이건 진짜 Haskell 문법이 아니라 의사 코드이다. 함수의 동등성은 코드로 표현할 수 없기 때문이다. 하지만 이런 항등식은 방정식 추론에 이용할 수 있으며, 컴파일러가 최적화를 구현하는 데에도 사용될 수 있다.

Haskell에서 자연성 조건이 자동으로 성립하는 이유는 “공짜 정리(Theorems for free)와 관련이 있다. Haskell에서 자연 변환을 정의하는데 사용되는 매개변수 다형성은 모든 타입에 대해 작동할 수 있는 하나의 공식을 구현해야한다는 강력한 제한을 부과한다. 이러한 제한은 함수에 대해 방정식 정리를 사용할 수 있도록 만든다. 펑터를 변환하는 함수의 경우 공짜 정리는 자연성 조건을 의미한다.

Haskell에서 펑터를 다루는 아이디어 중 하나는 바로 펑터를 일반화된 컨테이너로 간주하는 것이다. 비유를 해보자면 펑터는 자연 변환한 컨테이너의 내용을 다른 컨테이너로 다시 포장하는 일종의 레시피라고 볼 수 있다. 우리는 컨테이너 내부 요소 자체를 수정하거나 새로운 요소를 만드는 것과 같은 변화를 가하지 않는다. 단지 그 요소들을 복사하여 새로운 컨테이너에 담을 뿐이다.

자연성 조건은 내부 요소를 fmap을 통해 먼저 수정하고 나중에 재포장하든, 재포장을 먼저 하고 새로운 컨테이너에서 내부 요소를 수정하든 상관없다는 것을 명시적으로 표현한다. 재포장과 fmap이라는 두 개의 동작은 마치 “계란을 옮긴다”, “계란을 끓인다”와 같이 직교적(서로 독립적)이라고 할 수 있다.

한번 Haskell에서의 자연 변환을 보여주는 몇 가지 예시를 살펴보도록 하자. 첫 번째 예시는 List 펑터와 Maybe 펑터와의 자연 변환이다. 이 함수는 리스트의 첫 번째 요소를 반환하지만, 만약 리스트가 비어있다면 Nothing을 반환한다.

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:xs) = Just x

이 함수는 a에 대해 다형적이다. a가 어떤 타입이든 함수는 제한없이 작동하기 때문에 매개변수 다형성을 갖추고 있다고 하는 것이다. 따라서 이 함수는 두 개의 펑터 사이의 자연 변환의 예시가 될 수 있다. 하지만 확실히 짚고 넘어가기 위해 자연성 조건을 한번 검증해보도록 하겠다.

fmap f . safeHead = safeHead . fmap f

우리는 두 개의 경우를 고려해야한다. 먼저 빈 리스트에 대한 경우를 생각해보자.

fmap f (safeHead []) = fmap f Nothing = Nothing

safeHead (fmap f []) = safeHead [] = Nothing

그리고 비어있지 않은 리스트에 대해서도 대응해야한다.

fmap f (safeHead (x:xs)) = fmap f (Just x) = Just (f x)
safeHead (fmap f (x:xs)) = safeHead (f x : fmap f xs) = Just (fx)

List 펑터와 Maybe 펑터의 fmap 구현에 대해서도 한번 되짚어보자.

-- List
fmap f [] = []
fmap f (x:xs) = f x : fmap f xs

-- Maybe
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)

더 흥미로운 예시는 펑터 중 하나가 단순한 Const 펑터인 경우이다. Const 펑터로부터 출발하거나 Const 펑터로 향하는 자연 변환은 반환 타입이나 인수 타입 중 하나에 다형성을 가진 함수와 동일하다.

예를 들어 길이(length)는 List 펑터에서 Const Int 펑터로의 자연 변환으로 볼 수 있다.

length :: [a] -> Const Int a
length [] = Const 0
length (x:xs) = Const (1 + unConst (length xs))

여기서 unConst는 Const 생성자를 제거하는데 사용된다.

unConst :: Const c a -> c
unConst (Const x) = x

물론 실제 length는 아래와 같이 단순하게 정의된다.

length :: [a] -> Int

이 타입 시그니처는 length가 List 펑터에서 Const 펑터로의 자연 변환이라는 사실을 숨기고 있다.

반면 Const 펑터에서 출발하는 매개변수 다형성 함수를 찾는 것은 조금 더 어려운 일이다. 왜냐하면 아무것도 없는 상태에서 값을 생성하기를 요구하기 때문이다. 따라서 우리가 할 수 있는 최선은 다음과 같다.

scam :: Const Int a -> Maybe a
scam (Const x) = Nothing

또 다른 펑터는 예전에 보았던 Reader 펑터이며, 이 펑터는 요네다 보조정리에서도 중요한 역할을 한다. newtype 키워드를 사용하여 Reader 펑터의 정의를 다시 작성해보겠다.

newtype Reader e a = Reader (e -> a)

이것은 두 가지 타입으로 매개변수화되지만, 두 번째 유형에 대해서만 공변적으로 펑터적이다.

instance Functor (Reader e) where
    fmap f (Reader g) = Reader (\x -> f (g x))

모든 타입 e에 대해서, Reader e에서 다른 펑터 f로의 자연 변환들을 정의할 수도 있다. 나중에 요네다 보조정리에 대한 이야기를 할 때 이 변환들의 구성원들이 항상 f e의 요소와 일대일 대응되는 것을 보게될 것이다.

예를 들어 유닛 타입 ()를 생각해보자. 이 타입은 단 하나의 원소인 ()를 가진다. Reader 펑터는 임의의 타입 a를 가져와서 함수 타입 () -> a로 매핑한다. 그리고 이 함수는 집합 a에서 하나의 원소를 선택하는 모든 함수들을 의미한다. 즉, 이 함수들은 집합 a에 있는 원소들의 수만큼 존재하는 것이다.

그럼 이제 이 펑터에서 Maybe 펑터로의 자연 변환을 생각해보겠다.

alpha :: Reader () a -> Maybe a

이 자연 변환은 dumb와 obvious 두 가지 함수로 정의된다.

dumb (Reader _) = Nothing

obvious (Reader g) = Just (g ())

(어차피 함수 g가 할 수 있는 유일한 행위는 값 ()에 적용되는 것 뿐이다.)

실제로 요네다 보조정리에서 예측된대로 이 두 함수들은 Maybe () 타입의 두 요소들인 Nothing과 Just ()에 대응한다. 이에 대해서는 추후 요네다 보조정리를 이야기하며 더 자세히 살펴보도록 하겠다.

10.2 자연성을 넘어(Beyond Naturality)

두 펑터 사이의 매개변수 다형성 함수는 항상 자연 변환이다. 즉, 모든 표준 대수적 데이터 타입은 펑터이니 이러한 타입들 사이의 모든 다형성 함수는 자연 변환이다.

또한 우리는 함수 타입을 사용할 수 있으며, 함수 타입은 반환 타입에 대해 펑터적이다. 이를 사용하여 Reader 펑터와 같은 펑터를 만들고, 고차 함수인 자연 변환을 정의할 수도 있다.

그러나 함수 타입은 인자 타입에 대해 공변적이지 않으며 반공변적으로 작동한다. 물론 반공변 펑터는 반대 카테고리에서의 공변 펑터와 동등하다. 두 반공변 펑터 사이의 다형성 함수를 카테고리적 의미에서 보았을때는 여전히 자연 변환이다. 단, 이것들은 반대 카테고리에서 Haskell 타입으로 가는 펑터에서 작동한다.

이전에 보았던 반공변 펑터의 예시를 다시 한번 살펴보자.

newtype Op r a = Op (a -> r)

위 펑터는 a에 대해 반공변적이다.

instance Contravariant (Op r) where
    contramap f (Op g) = Op (g . f)

우리는 이 펑터를 가지고 Op Bool에서 Op String으로 향하는 다형성 함수를 작성해볼 수 있다.

predToStr (Op f) = Op (\x -> if f x then "T" else "F")

그러나 두 펑터가 모두 공변적이지 않기 때문에, 이것은 Hask에서의 자연 변환이 아니다. 그러나 두 펑터가 모두 반공변적이니, “반대” 자연성 조건을 만족할 수 있다.

contramap f . predToStr = predToStr . contramap f

contramap의 시그니처 때문에 함수 f는 fmap을 사용할 때와는 반대 방향으로 가야한다는 점을 주목하자.

contramap :: (b -> a) -> (Op Bool a -> Op Bool b)

그렇다면 공변적이든 반공변적이든 펑터가 아닌 타입 생성자도 있을까? 여기 한 가지 예시가 있다.

a -> a

이것은 동일한 타입 a가 반공변 위치, 공변 위치 모두에서 사용되기 때문에 펑터가 아니며, 이 타입에 대한 fmap이나 contramap을 구현할 수도 없다. 따라서 아래와 같은 시그니처를 가진 함수는 자연 변환이 될 수 없다.

(a -> a) -> f a

흥미롭게도 이러한 경우를 다루는 자연 변환의 일반화된 형태가 있으며, 이를 이자연 변환(Dinatural transformations)이라고 한다. 이에 대해서는 추후 끝(ends)에 대해 이야기할 때 다시 살펴볼 것이다.

10.3 펑터 카테고리(Functor Category)

이제 우리는 펑터 간의 사상인 자연 변환에 대해 알게 되었으므로, 펑터만으로 이루어진 카테고리도 존재하는지 대해서 이야기해볼 수 있게 되었다. 그리고 실제로 펑터로만 이루어진 카테고리는 존재한다. 각 카테고리 $C$ 에서 $D$ 로 향하는 펑터로만 이루어진 카테고리를 생각해보자. 이 카테고리의 대상은 $C$ 에서 $D$ 로 향하는 펑터이며, 사상은 이 펑터들 사이의 자연 변환일 것이다.

또한 이미 우리는 사상을 어떻게 합성하는지 알고 있으니, 두 자연 변환의 합성의 정의 또한 쉽게 할 수 있다.

한번 펑터 $F$ 에서 $G$ 로 향하는 자연 변환 $α$ 를 생각해보자. 이때 대상 a의 성분은 다음과 같은 사상이 될 것이다.

α_a :: F a -> G a

우리는 이 자연 변환 $α$ 를 펑터 $G$ 에서 $H$ 로 향하는 자연 변환 $β$ 와 합성하려고 한다. $β$ 의 대상 a의 성분은 다음과 같은 사상이 될 것이다.

β_a :: G a -> H a

당연히 이 사상들은 합성이 가능하며, 그 합성 결과는 또 다른 사상이 된다.

β_a ◦ α_a :: F a -> H a

이제 두 자연 변환 $α$ 와 $β$ 의 합성인 이 사상을 자연 변환 $β ⋅ α$ 의 성분으로 사용하면 된다.

(β ⋅ α)a = β_a ◦ α_a

아래 다이어그램을 보면, 이 합성의 결과가 실제로 $F$ 에서 $H$ 로 향하는 자연 변환임을 확인해볼 수 있다.

H f ◦ (β ⋅ α)_a = (β ⋅ α)_b ◦ F f

자연 변환의 합성은 일반적인 사상과 동일하기 때문에 합성에 대한 결합법칙 또한 만족한다.

마지막으로 각 펑터 $F$ 에 대해서는 성분이 항등 사상인 항등 자연 변환 $1_F$ 도 존재할 수 있다.

id_Fa :: F a -> F a

따라서 펑터로만 이루어진 카테고리도 존재한다고 말할 수 있는 것이다.

참고로 이 책에서는 카테고리 이론의 공동 창시자인 사운더스 맥레인(Saunders Mac Lane)의 방식을 따라, 자연 변환의 합성을 점으로 표기하고 있다.

문제는 자연 변환을 합성하는 방법이 하나가 아니라는 것이다. 이 방법들은 크게 수직 합성과 수평 합성으로 나누어진다. 그 중에서도 수직 합성은 일반적인 다이어그램에서 펑터와 자연 변환이 모두 수직으로 표기되기 때문에 불리는 명칭이며, 이는 펑터 카테고리를 이해할 때 중요한 개념이기도 하다. 또 다른 합성 방법인 수평 합성에 대해서는 다음 섹션에서 마저 설명하도록 하겠다.

카테고리 $C$ 와 $D$ 간의 펑터 카테고리는 Fun(C, D) 또는 [C, D]로 표기되며, 때로는 지수 형태인 $D^C$ 로 표기되기도 한다. 특히 마지막 표기법이 흥미로운데, 이는 펑터 카테고리 자체가 다른 카테고리에서 함수 대상(지수 대상)으로 간주될 수 있음을 암시하고 있기 때문이다. 이에 대해서 한번 알아보자.

지금까지 우리가 구축해온 추상화 계층들을 한번 살펴보자. 우리는 대상과 사상의 집합인 카테고리에서부터 시작해왔다. 카테고리 자체, 특히 집합의 카테고리인 작은 카테고리는 상위 레벨 카테고리인 Cat(카테고리의 카테고리)에서의 대상이 된다. 그리고 Cat의 사상은 결국 펑터이기 때문에 Cat의 Hom 집합은 펑터들의 집합이 될 것이다. 예를 들어 $Cat(C, D)$ 는 두 카테고리 $C$ 와 $D$ 간의 펑터들의 집합이다.

펑터 카테고리 $[C, D]$ 역시 사상으로 자연 변환을 가지고 있다는 점만 제외하면 두 카테고리 간의 펑터들의 집합이라고 볼 수 있다. 이 카테고리의 대상은 $Cat(C, D)$ 의 원소와 동일하기 때문이다. 게다가 펑터 카테고리 또한 카테고리이기 때문에 Cat의 대상이 되어야 한다. 즉, 우리는 이 관계를 하나의 카테고리 내의 Hom 집합과 대상 간의 관계로 표현할 수 있다는 것이며, 이건 이전 섹션에서 보았던 지수 대상과 정확하게 같은 개념이다.

한번 Cat에서 이 개념을 어떻게 구성할 수 있는지 살펴보자.

지수를 구성하기 위해서는 먼저 곱의 개념을 정의해야 한다는 것을 기억할 것이다. 다행히도 Cat에서는 곱을 정의하기가 비교적 쉽다. 각각의 작은 카테고리들은 대상들의 집합이므로, 곱이라는 개념을 집합의 곱으로 생각해도 무방할 것이다. 따라서 곱 카테고리 $C × D$ 의 대상은 그냥 $C$ 와 $D$ 의 대상들 중 하나씩 뽑아내어 구성된 대상들의 쌍 (c, d)이다.

마찬가지로 두 개의 쌍 (c, d)와 (c', d') 간의 사상은 사상의 쌍 (f, g)으로, 이때 각 사상들은 f :: c -> c'와 g :: d -> d'가 될 것이다. 이러한 사상의 쌍은 성분 별로 합성되고, 항상 항등 사상의 쌍인 항등 쌍 또한 존재할 수 있다. 간단하게 말하자면 Cat은 완전한 데카르트 폐쇄 카테고리이기 때문에 모든 카테고리 쌍에 대한 지수 대상 $D^C$ 를 가진다는 의미이다. 이때 Cat의 대상이라는 것은 결국 카테고리를 의미하므로, 결론적으로 $D^C$ 는 $C$ 와 $D$ 간의 펑터 카테고리라고 말할 수 있다.

10.4 2-카테고리

Cat을 조금 더 자세히 들여다보자. 앞서 언급한 정의에 따라 Cat의 Hom 집합은 펑터들의 집합이다. 하지만 방금 $[C, D]$ 의 사례에서 보았듯이 두 대상 사이의 펑터는 단순한 집합 이상으로 더 풍부한 구조를 지니고 있다. 자연 변환을 사상으로 적용하여 카테고리를 형성할 수도 있기 때문이다. 펑터는 Cat에서 사상으로 간주되므로, 자연 변환은 사상 간의 사상이라고 할 수 있다.

이처럼 더 풍부한 구조가 바로 2-카테고리의 예로, 2-카테고리에는 대상과 사상(또는 1-사상) 외에도 사상과 사상 간의 사상인 2-사상 또한 존재할 수 있다.

즉, Cat를 2-카테고리라고 본다면

대상: 작은 카테고리들
1-사상: 카테고리 간의 펑터
2-사상: 펑터 간의 자연 변환

으로 정의할 수 있다는 것이다.

그렇다면 이제 우리는 두 카테고리 $C$ 와 $D$ 간의 Hom 집합 대신에, Hom 카테고리인 펑터 카테고리 $D^C$ 를 가질 수 있게 된다. 그리고 이 펑터들은 합성될 수도 있다. $D^C$ 의 펑터 $F$ 와 $E^D$ 의 펑터 $G$ 가 합성되어 $E^C$ 의 펑터 $G ◦ F$ 를 얻을 수 있는 것처럼 말이다. 또한 각 Hom 카테고리 내에서 자연 변환 또는 2-사상이라고 부르는 수직 합성 또한 가질 수 있다.

이제 이렇게 두 종류의 합성이 있는 2-카테고리에서 이 합성 체계들이 어떻게 상호작용하는지를 알아보도록 하자.

우선 Cat에서 임의로 두 개의 펑터(1-사상)을 선택해보겠다.

F :: C -> D
G :: D -> E

그리고 이들의 합성은 아래와 같을 것이다.

G ◦ F :: C -> E

그리고 펑터 $F$ 와 $G$ 에 작용하는 두 자연 변환 $α$ 와 $β$ 도 있을 것이다.

α :: F -> F'
β :: G -> G'

이 쌍에는 수직 합성을 적용할 수가 없다. 왜냐하면 $α$ 를 통해 도달한 펑터 $F’$ 가 $β$ 의 소스가 아니기 때문이다. 사실 이들은 $D^C$ 와 $E^D$ 라는 서로 다른 펑터 카테고리의 멤버이다. 하지만 $F’$ 를 통해 도달한 카테고리 $D$ 가 $G’$ 의 소스이기 때문에 이 두 펑터는 합성할 수 있다.

$G ◦ F$ 와 $G’◦ F’$ 는 무슨 관계일까? $α$ 와 $β$ 를 가지고 $G ◦ F$ 에서 $G’◦ F’$ 로 향하는 자연 변환을 정의할 수는 있는 것일까? 다이어그램을 통해 전체적인 구조를 한번 살펴보자.

가장 먼저 $C$ 의 대상인 a에서 부터 출발해보자. 이 대상의 이미지는 카테고리 $D$ 에서 F a와 F'a라는 두 대상으로 나누어진다. 그리고 이때 이 두 대상을 연결하는 자연 변환 $α$ 의 성분인 사상도 함께 생긴다.

α_a :: F a -> F' a

그리고 카테고리 $D$ 에서 $E$ 로 갈 때, 이 두 개의 대상은 네 개의 대상으로 나누어진다.

G (F a), G'(F a), G (F'a), G'(F'a)

이때 이 네 개의 대상을 서로 연결하는 정사각형, 즉 네 개의 사상 또한 생긴다. 그리고 이 사상들 중 두 개는 자연 변환 $β$ 의 성분이다.

β_Fa  :: G (F a) -> G'(F a)
β_F’a :: G (F'a) -> G'(F'a)

그리고 다른 두 개의 사상은 두 펑터에 의한 $α_a$ 의 이미지이다. (펑터는 사상 또한 매핑한다는 사실을 기억하자)

G α_a :: G (F a) -> G (F'a)
G'α_a :: G'(F a) -> G'(F'a)

갑자기 사상이 너무 많아져서 조금 복잡해지긴 했지만, 결국 우리의 목표는 이 중 $G ◦ F$ 와 $G’◦ F’$ 를 연결하는 자연 변환의 성분이 될 수 있는 G (F a)에서 G'(F'a)로 향하는 사상 $(β◦α)_a$ 를 찾는 것이다.

사실 위 다이어그램을 보면 G (F a)에서 G'(F'a)로 가는 경로는 총 두 가지이다.

G'α_a ◦ β_Fa
β_F’a ◦ G α_a

다행히도 이 두 경로는 같기 때문에 위 다이어그램의 정사각형은 $β$ 의 자연성 정사각형이된다.(다이어그램이 가환한다는 의미이다)

이렇게 $G ◦ F$ 에서 $G’◦ F’$ 로 향하는 자연 변환의 성분을 정의해보았다. 그리고 이 변환의 자연성을 증명하는 것은 귀찮은 과정이기는 하지만 꽤나 간단하게 해결이 가능한 부분이다.

그리고 이 자연 변환을 $α$ 와 $β$ 의 수평 합성이라고 부르는 것이다.

β ◦ α :: G ◦ F -> G' ◦ F'

앞서 이야기했듯 이 책은 맥레인의 표기법을 따르고 있기 때문에, 수평 합성에는 작은 원(◦)을 사용한다. 참고로 다른 곳에서는 경우에 따라 별표(*)를 사용하는 경우도 있다.

카테고리 이론을 공부할 때의 원칙 중 하나는 어떠한 합성이 있을 때마다 이 합성이 속한 카테고리도 찾아내야 한다는 것이다. 앞서 언급했던 자연 변환의 수직 합성은 펑터 카테고리의 일부였다. 그렇다면 수평 합성은 어떤 카테고리에 속하는 것일까?

이것을 알아내는 방법은 Cat을 옆으로 보는 것이다. 자연 변환을 펑터 사이의 화살표가 아닌 카테고리 사이의 화살표로 본다. 그럼 이제 자연 변환은 자신이 변환하는 펑터가 연결하는 두 개의 카테고리 사이에 위치한다.

이제 Cat의 두 대상인 $C$ 와 $D$ 사이의 사상은 자신들을 연결해주던 펑터들을 연결하는 자연 변환이 되었다. 마찬가지로 $D$ 에서 $E$ 로 향하는 펑터들을 연결하는 자연 변환도 있을테니, 이를 $D$ 에서 $E$ 로 향하는 새로운 사상으로 간주할 수 있다. 결국 수평 합성은 이러한 관점에서 바라볼 때 사상들의 합성인 것이다.

또한 $C$ 에서 $C$ 로 향하는 항등 사상도 있을 것이다. 이때의 항등 사상은 $C$ 의 항등 펑터를 자기 자신으로 매핑하는 항등 자연 변환이다. 수직 합성에서의 항등 자연 변환은 모든 자연 변환의 수직 합성에 대해서 항등 역할을 할 수 있지만, 수평 합성에서는 항상 그렇지만은 않다는 것을 기억해두자.

마지막으로 두 합성은 교환 법칙을 만족한다.

(β' ⋅ α') ◦ (β ⋅ α) = (β' ◦ β) ⋅ (α' ◦ α)

사운더스 맥레인(Saunders Mac Lane)의 말을 인용하자면 독자들은 이 사실을 증명하기 위해 명확한 다이어그램을 작성하는 것을 즐기게 될지도 모른다고 한다.

나중에 유용하게 사용할 수 있는 표기법이 하나 더 있다. Cat을 옆에서 바라보겠다는 이 해석에서 어떤 대상에서 다른 대상으로 향하는 방법에는 펑터를 사용하는 방법과 자연 변환을 사용하는 두 가지 방법이 있었다. 이때 이 펑터 화살표를 펑터에 작용하는 특수한 종류의 자연 변환인 항등 자연 변환으로 재해석해볼 수도 있다. 그래서 종종 아래와 같은 표기법을 볼 수 있다.

F ◦ α

여기서 $F$ 는 $D$ 에서 $E$ 로 향하는 펑터이고, $α$ 는 $C$ 에서 $D$ 로 향하는 두 펑터 사이의 자연 변환이다. 펑터는 자연 변환과 합성할 수 없기 때문에, 이것은 $α$ 가 작용한 이후 항등 자연 변환 $1_F$ 가 작용하는 수평 합성으로 해석하게된다.

이와 마찬가지로 아래 표기는 항등 자연 변환 $1_F$ 의 작용 이후 자연 변환 $α$ 가 작용하는 것으로 해석하면 된다.

α ◦ F

10.5 결론

이렇게 이 책의 첫 번째 파트를 마쳤다. 이제 우리는 카테고리 이론의 기본적인 용어들을 배웠으며, 대상과 카테고리를 명사로 생각하고 사상, 펑터 그리고 자연 변환을 동사로 생각할 수 있는 역량을 얻었다.

사상은 대상을 연결하고 펑터는 카테고리를 연결하며 자연 변환은 펑터를 연결하는 것처럼 말이다.

하지만 앞서 살펴보았듯이 한 수준의 추상화 단계에서는 동사로 보이는 것이 다음 수준에서는 대상이 되기도 한다. 마치 사상의 집합이 함수 대상이 되었던 것처럼 말이다. 그러면 이제 이 대상은 다시 다른 사상의 출발점이나 목표지점이 될 수 있게 된다. 이것이 우리가 알고있는 고차 함수(Higher Order Function)의 아이디어였다.

펑터는 대상을 대상으로 매핑하기 때문에 이를 타입 생성자 또는 매개변수적 타입으로 사용할 수 있다. 또한 펑터는 사상도 매핑하는데, 이것이 바로 고차 함수인 fmap이다. Const, 곱, 쌍대곱과 같은 간단한 펑터들은 다양한 대수적 데이터 타입을 생성하는데 사용할 수도 있다. 함수 타입 또한 공변 펑터적인 성질과 반공변 펑터적인 성질을 모두 가지고 있으므로 대수적 데이터 타입을 확장하는데 사용할 수 있다.

펑터는 펑터 카테고리에서 대상으로 간주될 수도 있다. 따라서 펑터는 자연 변환의 출발점과 목표가 되며, 자연 변환은 다형성 함수의 특별한 타입이라고 볼 수 있다.

10.1 다형성 함수(Polymorphic Functions)

10.2 자연성을 넘어(Beyond Naturality)

10.3 펑터 카테고리(Functor Category)

10.4 2-카테고리

10.5 결론

Evan Moon