[번역] 프로그래머를 위한 카테고리 이론 - 6. 단순한 대수적 타입

앞서 우리는 곱과 합이라는 두 가지 기본적인 방법을 통해 타입을 결합하는 것을 보았다. 사실 우리가 일상적인 프로그래밍에서 자주 접하는 데이터 구조는 이 두 가지 메커니즘만으로도 충분히 표현할 수 있다.

이처럼 데이터 구조의 많은 속성들을 합성할 수 있다는 사실은 굉장히 중요한 포인트이다. 예를 들어 동등성을 사용하여 기본적인 타입의 값들을 비교하는 방법과 이러한 비교 행위를 곱과 합 타입으로 일반화하는 방법을 알고 있다면, 우리는 자연스럽게 합성 타입에 대한 동등 연산자라는 개념을 유도할 수 있다. Haskell에서는 이렇게 합성된 타입의 하위 집합에 대해 동등성, 비교, 문자열로의 변환과 같은 연산들을 유도할 수 있다.

그럼 프로그래밍에서 곱 및 합 타입이 나타나는 방식에 대해서 자세히 살펴보도록 하자.

6.1 곱 타입(Product Types)

프로그래밍 언어에서 두 타입의 곱의 대표적인 구현은 바로 쌍(Pair)이다. Haskell에서는 쌍이 원시 타입 생성자이며, C++에서는 표준 라이브러리에서 정의된 템플릿이다.

엄밀히 말해 쌍은 교환 법칙을 따르지 않는다. 어떠한 쌍 (Int, Bool)은 (Bool, Int)으로 대체될 수 없다는 것이다. 하지만 이 두 타입은 동형성(Isomorphism)을 지니고 있다. 이 동형성은 Swap 함수에 의해 제공되며, Swap 함수는 아래와 같이 정의할 수 있다.

swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

이때 두 쌍은 동일한 데이터를 저장하지만 단순히 다른 형식을 사용하고 있는 것이라고 생각할 수 있다. 이는 마치 빅 엔디안(Big Endian) vs 리틀 엔디안(Little Endian)의 관계와도 비슷하다.

💡 역주

엔디안(Endian)은 컴퓨터 메모리에 데이터를 저장하는 방식을 의미한다. 빅 엔디안(Big Endian)은 가장 상위 바이트(Most Significant Byte, MSB)를 가장 낮은 주소에 저장하고, 반대로 리틀 엔디안은 MSB를 가장 높은 주소에 저장한다. 즉, 같은 데이터를 다루더라도 저장하는 방식만 다르다는 것이다.

이는 (Int, Bool)과 (Bool, Int) 쌍처럼 같은 타입들의 곱이지만 각 구성 요소의 위치만 다른 상황과도 유사하기에 작가는 이러한 예시를 든 것이다.

만약 임의의 개수인 타입들을 곱으로 결합하려면 그저 쌍을 중첩시키는 것만으로도 표현할 수 있지만 더 쉬운 방법도 있다. 이렇게 중첩된 쌍은 튜플과 동일한데, 이는 쌍을 중첩하는 다양한 방법들이 동형(Isomorphic)이기 때문이다. 세가지 타입 a, b, c를 순서대로 곱으로 결합하려면 아래와 같은 두 가지 방법을 사용해볼 수 있다.

((a, b), c)
-- 또는
(a, (b, c))

이 타입들은 분명히 다른 타입이다. ((a, b), c) 타입을 받을 수 있는 함수에 (a, (b, c)) 타입을 전달할 수 없다는 것을 생각해보면 된다. 하지만 이 타입들이 가진 각각의 요소들은 분명 일대일 대응 관계에 놓여있다.

여기 이 두 타입을 서로 매핑해주는 함수가 있다.

alpha :: ((a, b), c) -> (a, (b, c))
alpha ((x, y), z) = (x, (y, z))

그리고 이 함수에는 역함수 또한 존재한다.

alpha_inv :: (a, (b, c)) -> ((a, b), c)
alpha_inv (x, (y, z)) = ((x, y), z)

즉, 이 매핑 함수는 동형사상(Isomorphism)이며, 이 과정에서 이 타입들이 결국 동일한 데이터를 여러 방법으로 패키징하고 있을 뿐이라는 사실을 알 수 있다.

이렇게 생성된 곱 타입을 타입에 대한 이항 연산이라고 생각해볼 수도 있다. 이 관점에서 바라보면 위에서 알아본 동형사상은 모노이드(Monoid)에서 본 결합 법칙과 매우 유사한 형태를 띄고 있다.

(a * b) * c = a * (b * c)

그러나 모노이드의 경우 이 두 가지 방법이 완전히 동일하다고 말할 수 있겠지만, 곱 타입의 경우 완전히 동일하다는 의미가 아닌 동형사상에 따라 동일하다고 말할 수 있다.

💡 역주

만약 (a * b) * c와 a * (b * c)를 모노이드인 곱 연산의 관점에서 바라본다면, 이 연산은 교환법칙을 만족하기 때문에 완벽히 동일(Equal)하다고 이야기할 수 있다.

하지만 곱 타입의 경우 각 튜플 안에 있는 요소들이 서로 정보의 손실 없이 매핑될 수 있는 일대일 대응함수가 존재하는 동형(Isomorphic)일 뿐이다.

즉, 두 곱 타입이 동형사상을 통해 서로 매핑이 가능하므로 “동형성에 의해 같다”고 말할 수는 있겠지만 엄밀한 의미에서 동일하지는 않다는 것이다.

만약 우리가 동형사상을 수용할 수 있고 엄격한 동일성을 요구하지 않는다면, 유닛 타입인 ()이 곱셈의 항등원인 1과 같이 작동한다는 것을 보일 수도 있다. 실제로 임의의 타입 a인 값과 Unit을 쌍으로 묶는 것은 어떠한 정보도 추가하지 않는다.

(a, ())

결국 이 타입은 a와 동형(Isomorphic)이다. 아래와 같이 동형사상을 정의할 수도 있다.

rho :: (a, ()) -> a
rho (x, ()) = x

rho_inv :: a -> (a, ())
rho_inv x = (x, ())

이러한 분석을 통해 집합의 카테고리가 모노이드 카테고리(Monoidal Category)라는 것을 형식적으로 설명할 수 있다. 결국 집합의 카테고리는 각 대상을 데카르트 곱(Cartesian Product)의 형태로 곱할 수 있는 카테고리라는 것이다. 이에 대한 자세한 정의는 추후 다시 논의해보도록 하자.

Haskell에서는 곱 타입을 더 일반적인 방식으로 정의할 수 있는 방법을 제공하고 있다. 나중에 다시 보겠지만 이런 방법은 특히 곱 타입이 합 타입과 합쳐질 때 빛을 발하게 된다. 이 방법은 여러 개의 인자를 받는 생성자로 표현되는데, 쌍의 경우는 아래와 같이 정의될 수 있다.

data Pair a b = P a b

여기서 Pair a b는 매개변수화된 두 개의 타입 a와 b, 그리고 데이터 생성자인 P를 의미한다. 우리는 Pair 타입 생성자에 두 개의 타입을 전달함으로써 간단하게 쌍이라는 타입을 생성할 수 있다. 그리고 P에는 정의해둔 타입에 맞는 두 값을 전달하여 쌍 타입의 값을 생성할 수 있다.

한번 String과 Bool의 쌍으로 값을 정의해보자.

stmt :: Pair String Bool
stmt = P "This statements is" False

첫 번째 줄은 타입 선언부이다. 여기서 Pair 타입 생성자를 사용하며, 일반화했었던 Pair 정의의 매개변수인 a와 b 대신에 String과 Bool을 직접 넘겨준다. 두 번째 줄은 데이터 생성자 P를 사용하여 구체적인 문자열과 부울값을 전달하여 실제 값을 정의하고 있다. 타입 생성자는 타입을 생성할 때 사용되고, 데이터 생성자는 해당 타입을 가진 값을 생성할 때 사용되는 것이다.

💡 역주

완전히 동일하지는 않지만, 위 Haskell 코드를 TypeScript로 표현해보자면 아래와 같다.

// 데이터 생성자
const P = (a: A, b: B) => [a, b];

// 타입 생성자
type Pair<A, B> = ReturnType<typeof P>; 

const stmt: Pair<A, B> = P("This statements is", false);

Haskell에서는 타입 생성자와 데이터 생성자의 네임스페이스가 분리되어있기 때문에 아래와 같이 동일한 이름도 종종 사용되고는 한다.

data Pair a b = Pair a b

더 깊게 들여다보면 Pair를 이항 연산자인 (,)으로 대체하고 있는 것 또한 결국은 빌트인 쌍(Pair) 타입의 선언을 변형한 것이라고 볼 수 있다. 실제로 (,)을 전위 연산자로 표현하여 타입 생성자처럼 사용할 수도 있다.

stmt = (,) "This statement is" False

이와 유사하게 (,,)을 사용하면 트리플(원소가 3개인 튜플)을 생성할 수 있으며, 같은 방법으로 계속 해서 튜플을 확장해나갈 수도 있다. 또한 일반적인 쌍이나 튜플 대신 원하는 곱 타입을 정의할 수도 있다.

data Stmt = Stmt String Bool

이 타입은 단순히 String과 Bool의 곱이지만 이 타입은 자체적인 이름과 생성자를 가지고 있다. 이러한 선언 방법의 장점은 동일한 내용을 가지지만 의미와 기능이 다른 타입을 다양하게 정의할 수 있다는 것이다. 또한 이렇게 선언된 각 타입들은 서로 대체될 수 없다.

이처럼 튜플과 다중 인자 생성자를 사용하는 생성자는 각 구성 요소가 무엇을 나타내고 있는지 추적하기 어렵기 떄문에 종종 혼란스러운 표현이 되기 쉽고 오류가 발생하기도 쉽다. 그래서 때로는 각 구성 요소에 이름을 지정해주는 것이 나을 수도 있다. 이처럼 이름이 지정된 필드를 가진 곱 타입을 Haskell에서는 record라고 하며, C에서는 struct라고 한다.

6.2 레코드(Records)

본격적인 설명에 앞서 간단한 예시를 먼저 살펴보도록 하자. 우리는 화학 원소들을 설명하기 위해 원소의 이름과 원소 기호로 이루어진 두 개의 문자열과 원자 번호를 표현하는 하나의 정수가 결합된 데이터 구조를 만드려고 한다. 먼저 (String, String, Int)와 같이 튜플을 사용하여 각 구성 요소를 표현해볼 수 있다. 그 다음 원소 기호가 원소 이름의 접두사가 맞는지 확인하는 함수로 패턴 매칭하여 구성 요소들을 추출할 것이다. 아래는 He가 Helium의 접두사인지 확인하는 함수이다.

startsWithSymbol :: (String, String, Int) -> Bool
startsWithSymbol (name, symbol, _) = isPrefixOf symbol name

그러나 이 코드는 에러가 발생할 가능성이 있고 유지 보수하기도 쉽지 않은 코드이다. 이런 경우에는 레코드를 정의하는 것이 훨씬 더 낫다.

data Element = Element { name :: String
                       , symbol :: String
                       , atomicNumber :: Int }

위 표현과 튜플을 사용한 표현은 동형(Isomorphic)이다.이는 서로 역함수의 관계를 가지는 두 개의 변환 함수를 통해 확인할 수 있다.

tupleToElem :: (String, String, Int) -> Element
tupleToElem (n, s, a) = Element { name = n
                                , symbol = s
                                , atomicNumber = a }

elemToTuple :: Element -> (String, String, Int)
elemToTuple e = (name e, symbol e, atomicNumber e)

여기서 레코드 필드의 이름은 필드에 액세스하기 위한 함수로도 작동한다는 사실에 주목하도록 하자. 예를 들어 atomicNumber e라는 표현은 e에서 atomicNumber필드를 검색한다. 이처럼 e라는 레코드의 필드에 액세스하는 atomicNumber 함수의 타입은 다음과 같이 표현된다.

atomicNumber :: Element -> Int

Element의 레코드 문법을 사용하면 이제 startWithSymbol 함수도 더 읽기 쉬운 형태로 다시 표현해볼 수 있다.

startsWithSymbol :: Element -> Bool
startsWithSymbol e = isPrefixOf (symbol e) (name e)

심지어 Haskell이 제공하는 트릭을 사용하여 함수인 isPrefixOf를 중위 연산자로 표현하여 거의 하나의 자연어 문장처럼 읽히도록 만들어 볼 수도 있다.

startsWithSymbol e = symbol e `isPrefixOf` name e

6.3 합 타입(Sum Types)

집합의 카테고리의 곱 연산에서 곱 타입을 유도할 수 있듯이, 합 연산에서 합 타입을 유도해볼 수도 있다. Haskell에서 합 타입을 표현하는 전형적인 방법은 아래와 같다.

data Either a b = Left a | Right b

쌍과 마찬가지로 Either도 두 연산 대상이 동형성(Isomorphic)인 경우에 한해 교환 법칙을 만족하고 중첩도 가능하다. 또한 두 대상이 동형이라는 전제 하에 중첩 순서 또한 중요하지 않다. 그런 이유로 다음과 같이 세 개의 구성 요소를 가진 합 타입을 정의해볼 수 있다.

data OneOfThree a b c = Sinistral a | Medial b | Dextral c

이제 집합의 카테고리가 합을 기준으로 대칭적인 모노이드 카테고리라는 것이 밝혀졌다. 여기서 이항 연산의 역할은 서로소 합에 의해 수행되며 단위 원소의 역할은 초기 대상에 의해 수행된다.

타입 관점에서 바라보면 Either는 모노이드 연산자, 그리고 Uninhabited(아무런 값도 가질 수 없는) 타입인 Void는 이 연산에 대한 항등원으로 볼 수 있다. Either를 덧셈으로, Void를 0이라고 생각해보자. 실제로 Void를 합 타입에 추가하더라도 해당 타입의 내용은 변하지 않는다.

Either a Void

위 정의는 a와 동형(Isomorphic)이다. 그 이유는 Void는 아무런 값도 가질 수 없는 타입이기 때문에 이 합 타입에서 Right 생성자 부분을 채워넣을 방법이 없기 때문이다. Either a Void 타입을 가질 수 있는 유일한 값은 Left 생성자를 사용하여 생성되기 때문에 결과적으로는 그저 타입 a의 값을 캡슐화하는 역할만 하게 될 것이다. 따라서 형식적으로 a + 0 = a와 같은 관점이 성립한다.

이처럼 Haskell에서는 합 타입이라는 개념이 일상적으로 사용되지만, C++의 합 타입이라고 할 수 있는 union이나 variants은 Haskell처럼 일상적으로 사용되지는 않는다.

이에는 여러 이유가 있다. 일단 C++에서 간단한 합 타입은 굳이 union을 사용하지 않더라도 enum 키워드를 사용하여 선언하는 열거형(Enumerations)으로 표현할 수 있다.

Haskell에서 합 타입을 표현하는 방법을 다시 살펴보도록 하자.

data Color = Red | Green | Blue

위 합 타입을 C++에서 다시 표현해보면 아래와 같다.

enum { Red, Green, Blue };

마찬가지로 Haskell에서는 간단한 합 타입 중 하나인 Bool을 아래와 같이 합 타입임을 명시하여 표현된다.

data Bool = True | False

하지만 C++에서 이러한 합 타입은 그저 원시 자료형인 bool일 뿐이다.

C++에서 값의 존재나 부재를 인코딩하는 간단한 합 타입은 여러가지 트릭과 빈 문자열, 음수, Null 포인터와 같이 “불가능한” 값들을 사용하여 다양하게 구현되고 있다. 이렇게 선택적으로 값이 존재할 수 있는 경우 Haskell에서는 Maybe 타입을 사용하여 표현한다.

data Maybe a = Nothing | Just a

Maybe 타입은 두 타입의 합 타입으로 구성되어있다. Maybe 타입을 구성하는 두 생성자를 각각의 개별적인 타입으로 분리하면 아래와 같이 보일 것이다. 먼저 첫 번째 생성자를 보도록 하자.

data NothingType = Nothing

이 타입은 값이 단 하나뿐인 열거형(Enumeration)이며, Nothing이라는 하나의 값만 가지고 있다. 다시 말해 이 타입은 싱글톤, 즉 단일 원소 집합이며 이는 유닛 타입인 ()와 동등하다.

이제 두 번째 생성자도 한번 보도록 하자.

data JustType a = Just a

사실 위 타입은 그저 타입 a를 캡슐화한 것에 불과하다. 결과적으로 우리는 Maybe 타입을 다음과 같이 표현할 수도 있다.

data Maybe a = Either () a

C++에서 이보다 더 복잡한 합 타입을 표현하고 싶을 때는 포인터를 사용하여 일종의 모방을 한다. 포인터는 null이거나 특정 타입인 값을 가리킬 수 있다. 예를 들어 Haskell의 List 타입은 재귀적인 합 타입으로 정의될 수 있다.

List a = Nil | Cons a (List a)

C++에서 이 표현을 모방하려면 Null 포인터 트릭을 사용하여 빈 리스트를 구현하는 방법으로 시도해볼 수 있다.

template<class A>
class List {
    Node<A> * _head;
public:
    List() : _head(nullptr) {} // Nil
    List(A a, List<A> l)       // Cons
      : _head(new Node<A>(a, l))
    {}
};

두 개의 Haskell 생성자인 Nil과 Cons는 오버로딩된 두 개의 List 생성자로 번역된다. List 클래스는 합 타입의 두 구성 요소를 구별하는데 별도의 태그가 필요하지는 않지만, 리스트의 헤드를 의미하는 _head를 nullptr로 초기화함으로써 Nil 생성자를 표현하고 있다.

Haskell과 C++ 타입 간의 주요한 차이는 Haskell의 데이터 구조가 불변(Immutable)하다는 점에서 발생한다. 특정한 생성자를 사용하여 객체를 생성하면 해당 객체는 자신을 생성할 때 어떤 생성자가 사용되었는지, 그리고 어떤 인수가 전달되었는지 영원히 기억하고 있다. 따라서 Just "energy"로 생성된 Maybe 객체는 절대 Nothing으로 변하지 않는다는 것이다. 마찬가지로 빈 리스트는 영원히 빈 상태로 유지되며, 세 개의 원소를 가진 리스트는 영원히 동일한 세 개의 원소를 가진다.

이러한 불변성은 구성 자체를 뒤집을 수 있도록 만들어주기도 한다. 주어진 객체를 항상 해당 구성에 사용된 부분으로 분해할 수 있다는 뜻이다. 이러한 분해에는 패턴 매칭이 사용되며 주어진 생성자를 패턴으로 다시 사용한다. 생성자에 인자가 주어진 경우 해당 인자는 변수로 대체된다.

List 데이터 타입은 두 개의 생성자를 가지고 있기 때문에 List를 해체할 때는 해당 생성자들에 각각 대응하는 두 가지 패턴을 사용해야 한다. 하나는 빈 Nil 리스트와 매칭될 것이고 다른 하나는 Cons로 생성된 리스트와 매칭될 것이다. 아래는 List에 대한 간단한 함수의 정의들이다.

maybeTail :: List a -> Maybe (List a)
maybeTail Nil = Nothing
maybeTail (Cons _ t) = Just t

maybeTail의 정의의 첫 번째 부분은 Nil 생성자를 패턴으로 사용하여 Nothing을 반환하고 있다. 두 번째 부분은 Cons 생성자를 패턴으로 사용하고 있는데, 생성자에게 주어진 첫 번째 인자는 필요없기 때문에 와일드 카드인 _로 대체하고 있다. 생성자에게 주어진 두 번째 인자는 변수 t에 바인딩되며 최종 반환 값은 Just t이다. 이제 List가 어떻게 생성되었느냐에 따라 두 정의 중 하나와 패턴 매칭이 될 것이다. 만약 Cons를 사용하여 생성되었다면 생성자에 전달된 두 인자 중 두 번째인자가 검색될 것이고 이후 Just t의 형태로 반환될 것이다.

C++에서 이보다 더 복잡한 합 타입은 다형적인 클래스 계층을 사용하여 구현한다. 공통 조상을 가진 클래스 패밀리는 숨겨진 태그로 이해될 수 있으며, Haskell에서 생성자에 대한 패턴 매칭을 통해 수행되는 작업은 C++의 vtable 포인터를 기반으로 가상 함수 호출을 디스패치함으로써 수행된다.

사실 C++에서는 합 타입을 온전하게 구현하기 어려운 여러가지 제약 때문에 union이 많이 사용되지는 않는다. 심지어 string::std이 복사 생성자(Copy Constructor)를 가지고 있기 때문에 std::string를 union에 넣을 수 조차 없다.

6.4 타입의 대수학

곱 타입과 합 타입 모두 각각 데이터 구조를 정의할 때 유용하게 사용할 수 있지만, 실질적인 강점은 이 둘을 결합할 때 나타난다. 여기서 다시 한번 우리는 합성의 힘을 느끼게된다.

먼저 우리가 지금까지 발견한 내용을 요약해보도록 하자. 타입 시스템의 기초에는 교환 법칙을 만족하는 두 가지 모노이달(Monoidal) 구조가 있다. 바로 Void를 항등원으로 가지는 합 타입과 유닛 타입인 ()을 항등원으로 가지는 곱 타입이다. 우리는 이 개념들을 덧셈과 곱셉에 비유해서 생각해보려고 한다. 이 비유에서 Void는 덧셈의 항등원인 0, 그리고 ()는 곱셈의 항등원인 1에 해당할 것이다.

이 비유를 한번 어디까지 확장해서 적용할 수 있는지 보도록 하자. 우리는 이미 어떤 수에 0을 곱하게 되면 0이라는 결과를 얻는다는 사실을 알고 있다. 그렇다면 곱 타입인 쌍의 한 요소가 Void라면 이 타입은 Void와 동형일까? 예를 들면 Int와 Void를 구성요소로 가진 쌍을 만드는 것이 가능하냐는 것이다.

쌍이라는 타입을 가진 값을 생성하기 위해서는 쌍의 구성 요소가 될 두 개의 값이 필요하다. 문제는 정수는 쉽게 만들 수 있지만 문제는 Void 타입의 값이 존재하지 않는다는 것이다. 따라서 모든 타입 a에 대해 타입 (a, Void)는 값을 가질 수 없는 타입(Uninhabited Type)이며, 결과적으로 Void와 동등하다. 다시 말해 a*0 = 0인 것이다.

덧셈과 곱셈을 연결하는 또 다른 속성은 분배 법칙이다.

a * (b + c) = a * b + a * c

곱셈과 덧셈의 분배 법칙이라는 속성은 일반적으로 곱 타입과 합 타입에도 적용될 수 있다. 위 식의 좌변은 아래와 같은 타입에 해당한다.

(a, Either b c)

그리고 우변은 아래와 같은 타입에 해당한다.

Either (a, b) (a, c)

좌변과 우변에 해당하는 타입들은 아래와 같은 방법을 통해 상호 변환될 수 있다.

prodToSum :: (a, Either b c) -> Either (a, b) (a, c)
prodToSum (x, e) =
    case e of
      Left  y -> Left  (x, y)
      Right z -> Right (x, z)

또한 위 함수의 역함수도 존재한다.

sumToProd :: Either (a, b) (a, c) -> (a, Either b c)
sumToProd e =
    case e of
      Left  (x, y) -> (x, Left  y)
      Right (x, z) -> (x, Right z)

case of 문은 함수 내에서 패턴 매칭에 사용된다. 주어진 변수가 화살표 왼쪽의 패턴과 일치한다면 화살표 오른쪽의 표현식이 실행되는 것이다. 예를 들어 prodToSum 함수를 호출해보는 상황을 한번 보도록 하자.

prod1 :: (Int, Either String Float)
prod1 = (2, Left "Hi!")

case e 구문의 e는 Left "Hi!"에 해당한다. 이는 Left y라는 패턴과 일치하기 때문에 y는 “Hi!”라는 값으로 대체된다. 이 경우 x는 2에 매칭될 것이기 때문에 case 문을 사용한 전체 함수의 결과는 Left(2, "Hi!")가 되는 것이다.

여기서 굳이 이 두 함수가 서로의 역함수임을 증명할 생각은 없지만, 가만 생각해보면 이 두 함수는 서로의 역함수여야하는 것이 당연하다. 왜냐하면 이 두 함수는 그저 자신이 받은 두 데이터 구조의 내용을 간단하게 재포장하는 것에 불과하기 때문이다. 즉, 데이터는 동일하지만 표현 방식이 다른 것 뿐이다.

수학자들은 이처럼 얽혀있는 두 개의 모노이드에 대해 반환(Semiring)이라는 이름을 붙혔다. 이것은 이 경우 타입 간의 뺄셈에 대해서는 정의할 수 없기 때문에 완전한 “환(Ring)”이라고 말할 수는 없는 것이다.

반환(Semiring)은 환(Ring)에서 음의 요소(Negative) n이 빠진 것이므로, 말장난처럼 “Rig”라고 부르기도 한다.

하지만 음의 요소가 빠진 반환만으로도 자연수의 관한 명제를 타입에 관한 명제로 번역하여 많은 이점을 얻을 수 있다. 여기 몇 가지 흥미로운 항목들을 담은 번역 표가 있다.

리스트 타입은 특히 더 흥미로운데, 이 타입은 방정식의 해로 정의되기 때문이다. 우리가 정의하려는 타입은 일종의 방정식이며 아래와 같이 표현된다.

List a = Nil | Cons a (List a)

이 방정식의 List a를 x로 치환해서 이 식을 일반화하면 아래와 같은 방정식을 얻을 수 있다.

x = 1 + a * x

하지만 타입의 세계에는 뺄셈이나 나눗셈이 없으니 우리는 이 문제를 전통적인 대수적 방법론으로는 해결할 수 없다. 하지만 이 식에 표현되어있는 녀석들을 치환하는 것 정도는 할 수 있다. 우변에 있는 x를 (1 + a * x)로 계속 해서 치환하고 분배 법칙을 사용해보자. 그러면 이제 이러한 식으로 이어질 것이다.

x = 1 + a*x
x = 1 + a*(1 + a*x) = 1 + a + a*a*x
x = 1 + a + a*a*(1 + a*x) = 1 + a + a*a + a*a*a*x ...

x = 1 + a + a*a + a*a*a + a*a*a*a...

결국 이 식은 무한한 곱(튜플)의 합으로 끝나게 되는데, 이것은 리스트가 빈 경우 1, 단일 값인 경우 a, 쌍인 경우는 a*a, 트리플인 경우 a*a*a처럼 무한히 나아갈 것이라고 해석할 수 있다. 이게 결국 리스트의 정의 그 자체이다.

이외에도 리스트에 대한 더 많은 내용들이 있지만, 다른 내용들에 대해서는 추후 펑터(Functor)와 고정점(Fixed Point)에 대해서 배운 후에 리스트와 같은 기타 재귀적인 데이터 구조에 대해서 다시 다룰 때 이야기를 해볼 것이다.

결국 이처럼 기호로 표현되는 변수를 사용하여 어떠한 방정식을 해결하는 것이 바로 대수(Algebra)이며, 대수학으로 표현할 수 있는 타입에 이름을 붙힌 것이 대수적 데이터 타입(Algebraic Data Type)이다.

마지막으로 타입의 대수에 대한 아주 중요한 해석 중 하나를 이야기하려고 한다. 두 타입 a와 b의 곱 타입에는 a 타입의 값과 b 타입의 값이 모두 포함되어야 하지만, 두 타입의 합 타입에는 a 타입이나 b 타입의 값이 둘 중 하나라도 포함되어 있으면 충분하다. 이는 논리식인 AND와 OR도 반환(Semiring)을 형성한다는 것을 의미하며, 결국 논리식 또한 타입 이론으로 매핑될 수 있다.

논리식과 타입 이론 간의 유사성은 이외에도 더 깊게 이어질 수 있으며, 커리-하워드 동형성(Curry-Howard Isomorphism)의 기초라고 할 수 있다. 이 내용에 대해서는 추후 함수 타입에 대해 이야기할 때 다시 살펴보도록 하겠다.

• 6.1 곱 타입(Product Types)
• 6.2 레코드(Records)
• 6.3 합 타입(Sum Types)
• 6.4 타입의 대수학