대수적 자료형(Algebraic Data Type)

2023. 7. 16.

대수적 자료형(Algebraic Data Type)

함수형 프로그래밍은 그 자체로 많은 사랑을 받고 있는 프로그래밍 패러다임이지만, 그 기저에 도사리고 있는 이론적 배경의 난이도 때문에 선뜻 발을 담그기는 힘들다고 널리 알려져 있다. 그러나, 함수형 프로그래밍에서 파생된 여러 개념들 중 생각보다 우리 곁에 가까이 자리하고 있는 것들이 있다. 우리는 어쩌면 함수형 프로그래밍을 사용하고 있다는 자각도 없이, 어느 정도 자연스럽게 이들을 받아들이고 있는 것이다.

switch 문을 작성하며 default문 없이 가능한 모든 값의 경우에 대한 처리를 할 수는 없을까 생각하던 당신! TypeScript를 사용하며 여러 개의 문자열을 |으로 연결하여 일종의 ‘자료형’같이 사용해본 적이 있는 당신! 우리는 함수형으로 사고하는 방법을 정확히 모르더라도, 그 장점에 공감하고 눈앞에 주어진 문제에 함수형의 개념을 적용하고 있다. 이번 글에서는 그러한 개념 중에서도 자주 다루어지는 대수적 자료형에 대해 미약하나마 공부한 바를 정리하려 한다. 완벽하게 이해한 것이 아니기에 비약이 있을 수도 있는 점 넓은 아량으로 봐주시기 부탁드리며, 오류가 있다면 어떠한 경로로든 알려주시기 바란다.

범주? 사상의 합성?

대수적 자료형은 추상대수학의 이론 중 하나인 ‘범주론’(Category Theory)에 그 이론적 근거가 있다. 따라서 범주란 무엇인가에 대해 어렴풋이나마 감을 잡고 가야 글을 따라가기 편할 것으로 예상한다.

범주(Category)란, 대상(Object)와 사상(Morphism)의 모음이다. 그림으로 그리는 경우 흔히 대상을 점으로, 사상을 ‘두 점 사이에 존재하는 화살표’의 형태로 표현하는 것이 일반적이다. 고등학교 수학 시간에 벡터를 공부해본 사람들이라면 익숙한 구조일 수 있겠다. 여기서 가장 중요한 것이 ‘사상의 합성’인데, 대상 a에서 대상 b를 연결하는 사상 f: a → b와 대상 b에서 대상 c를 연결하는 사상 g: b → c가 존재할 때, f와 g를 합성하여 사상 g ∘ f를 얻을 수 있다. 이는 사상을 피연산자로 하는 이항 연산의 일종이며, 합성함수는 이러한 형태의 특수한 예라고 볼 수 있겠다.

어떠한 ‘대상과 사상의 모음’이 범주가 되기 위해서는 사상들이 만족해야 하는 두 가지 조건이 필요한데, 바로 사상 합성의 결합법칙과 항등사상의 존재이다. 사상 f, g, h가 존재할 때, h ∘ (g ∘ f) = (h ∘ g) ∘ f = h ∘ g ∘ f이며, 이는 곧 사상을 합성함에 있어 괄호로 인해 연산의 결과가 달라지지 않는다는 것을 의미하며, 괄호를 생략할 수 있다는 것을 나타낸다. 항등사상은 임의의 사상 f와 합성하여 f를 다시금 얻을 수 있는 사상을 말한다. 임의의 대상 X에는 각 유일한 사상이 존재하여, 임의의 사상 f: A → B에 대해 (B의 항등사상 ∘ f) = f = (f ∘ A의 항등사상)이 성립해야 한다. 사칙연산 등에서 사용하는 항등원(곱셈의 1, 덧셈의 0 등)과는 다르게, 왼쪽에서 이루어지는 연산과 오른쪽에서 이루어지는 연산 모두가 성립해야 하는 것을 확인할 수 있다. 고등학교 수학 시간에 행렬을 공부해본 사람들이라면 단위행렬을 떠올려도 좋을 것이다.

‘대수적’ 자료형?

범주론은 추상대수학의 일부인 만큼, 단번에 이해하기에는 무리가 있다. 그럼에도 불구하고 거칠게나마 범주론을 짚고 넘어가야 하는 이유는 우리가 다뤄야 할 주제가 ‘대수적’ 자료형이기 때문이다.

‘대수적’이라는 말은 무슨 의미일까? 추상대수학은 ‘대수적 구조’(Algebraic Structure)를 다루는 분야이다. 우리는 아무런 의문 없이 아주 자연스럽게 사칙연산을 이용하여 수를 다루곤 한다. 그 뿐인가? “1 + 1은 어째서 2인가?” 따위의 질문을 던지는 사람들을 다소 이상한 눈으로 바라보곤 한다. 물론 사탕 하나를 가지고 있는 아이에게 사탕 하나를 더 주면 아이는 사탕을 두 개 가지게 될 것이다. 그러나 그런 ‘경험적’인 방식이 아니라, ‘실수 1’을 ‘실수 1’과 덧셈한 결과를 2가 될 수 있도록 하는 이론적 토대를 제공하기 위해 수학자들은 대수학을 발전시켜왔다. 그리고 이러한 연구가 더 진전되어감에 따라, ‘수’ 이외의 수학적 대상에 대수적 구조를 적용하여 각 분야의 문제들을 대수학적인 시각으로 바라볼 수 있게 되었다. 결국 ‘대수적’ 자료형이라는 용어의 참된 의미는 원래 ‘수’로 생각할 수 없었던 ‘형’(Type, 이하 타입)이라는 ‘범주’의 대상에 대수적 구조를 적용하여, 대수학에서 문제를 다루는 방식으로 타입에 대한 문제를 해결해보자는 뜻으로 이해할 수 있다. 어떻게 이것이 가능한가? 바로 범주론이 있기 때문이다.

‘곱’ 타입? ‘합’ 타입?

대수적 자료형에 대해 정리된 여러 블로그 글들을 보면 공통적으로 나오는 말들이 있다. “대수적 자료형의 두 가지 일반적인 종류로는 곱(Product) 타입과 합(Sum) 타입이 있다”는 사실이다. 그러나 대부분의 글들은 너무 어려워질 것을 걱정하였는지 이 두 가지 자료형이 있다는 사실 자체만 담백하게 전달하고 있다. ‘곱 타입과 합 타입을 이용하면 범주 ‘타입’이 대수적 구조 중 하나인 ‘반환’(Semiring, Rig)과 동형(isomorphic)이 된다’는 말은 언뜻 보면 글만 한글로 써져있지, 외계어와도 같으니 말이다.

곱 타입

여기서 이야기하는 ‘곱’이란 정확히는 ‘데카르트 곱’(Cartesian Product)를 의미한다. 행렬의 곱셈과도 같다고 생각할 수 있다. 혹은 관계형 데이터베이스를 만져본 분들이라면 Cross Join을 떠올릴 수도 있겠다. 두 타입에 대한 곱 결과가 두 집합 간의 데카르트 곱의 결과와 같은 모양으로 나온다면, 우리는 범주 ‘타입’에 대한 곱과 집합 간의 데카르트 곱을 같은 느낌으로 쓸 수 있을 것이다. 문제는 범주의 관점에서는 개별적인 원소에 대한 개념이 없다는 것이다.

따라서 우리는 임의의 대상 C: (a, b)에서 a, b를 각각 취하는 두 가지 종류의 사상 f: C → a와 g: C → b를 생각할 수 있다. 범주 ‘타입’에는 이러한 사상을 가지는 비슷한 대상 C’이 하나 이상일 수 있으며, 그 중 가장 적절한 대상 C를 찾아 이를 ‘대상 a와 b의 곱’이라고 정의한다.

직관적으로 이야기하자면 ‘a 타입과 b 타입이 가질 수 있는 정보값을 잃지 않는 한에서, 표현할 수 있는 정보값의 범위가 가장 작은 대상’을 찾는 것이 목표라고 할 수 있겠다. 예를 들어, a가 Boolean이고 b가 Int인 경우, C가 만약 Int라면 어떻게 될까? C는 b 타입의 모든 정보를 표현할 수 있지만, a의 정보를 표현할 수는 없다. Int와 Boolean은 서로 다른 타입이고, Int를 통해 표현할 수 있는 Boolean 정보값은 없기 때문이다(물론 이런 짓이 가능한 관대한 언어들이 있긴 하다). 따라서 모든 Int 타입에 대해 True를 만들어내거나, 모든 Int에 대해 False를 만들어내는 경우밖에 없다. 어느 쪽이든 a 타입의 모든 정보값을 표현할 수는 없다. 또한 넘침은 곧 모자람만 못한 법. C가 a와 b의 표현 범위 이상을 표현할 수 있는 만큼의 정보값을 가질 수 있는 것도 낭비이기 때문에, 자연스럽게 C가 (Boolean, Int)인 경우가 최적임을 알 수 있다.

합 타입

사상 f: C → a와 g: C → b가 모여 곱을 구성한다면, 그 반대 방향도 생각할 수 있지 않을까? 그러니까, 사상 i: a → C와 사상 j: b → C가 모여 어떠한 대상 C를 만드는 a와 b를 생각할 수 있겠다는 말이다. 이러한 C는 ‘곱’과는 방향만 반대지 같은 아이디어에서 출발하였다. 이런 관계성을 수학적으로는 보통 ‘쌍대성’(duality)이라고 하며, 따라서 C는 ‘쌍대곱’(Coproduct)이라고 부른다. 이 경우에는 ‘오직 a 타입이거나 b 타입일 수밖에 없는 대상 C’를 찾는 것이 목표이다. a 타입이면서 동시에 b타입일 수 없고, a 타입이 아닌 동시에 b 타입일 수는 없다는 말이다. 집합의 관점에서는 이러한 형태를 가지는 집합을 분리합집합이라고 한다(서로소 집합과는 다르니 주의하자).

왜 곱 타입이고, 왜 합 타입인가?

곱 타입은 애초에 데카르트 ‘곱’에서 온 개념이니 그렇다 치자. 합 타입은 쌍대곱이라는 결과를 내는 주제에 왜 하필 ‘합’ 타입일까? 위에서 대수적 자료형이란, 타입이라는 범주의 대상에 대수적 구조를 적용하는 것이라고 말한 바 있다. 또한 위에서 잠시 나온 ‘반환’이라는 대수적 구조는 교환법칙, 결합법칙이 성립하고 항등원이 존재하는 덧셈과, 결합법칙과 분배법칙이 성립하고 항등원이 존재하며 0과의 곱이 0인 곱셈이 갖추어진 대수적 구조이다. 그렇다면, 타입이라는 범주의 곱과 쌍대곱을 사용하여 이와 형태가 같게 만들 수 있다면(즉 동형이라면) 덧셈과 곱셈을 통해 수를 다루는 것처럼 타입 시스템을 다룰 수 있다는 말이다. 이 때, 타입의 ‘곱’은 반환의 곱셈과 성질이 유사하며, 타입의 ‘쌍대곱’은 반환의 덧셈과 성질이 유사하기 때문에 각각의 이름이 그렇게 붙은 것이다.

항등원의 경우 이 글에서 별도로 설명하지는 않고, 편의를 위해 Scala의 자료형인 Nothing과 Unit을 빌려 이야기하겠다. Nothing이란 어떠한 값도 원소로 가질 수 없는, 집합의 관점에서 보았을 때 공집합을 나타내는 타입이며, Unit이란 단일 값이자 아무런 정보가 없는 ()라는 값만을 원소로 가질 수 있는 집합이다. 거두절미하자면 Nothing은 합 타입의(혹은 쌍대곱의) 항등원이고, Unit은 곱 타입의(혹은 곱의) 항등원이다. 간단한 예시를 통해 타입 시스템이 반환과 동형이라는 것을 보이도록 하자.

반환은 곱셈에 대해 결합법칙과 분배법칙의 성립, 0과의 곱이 0임을 만족해야 한다.

  1. 타입 (Int, (String, Int))와 타입 ((Int, String), Int)는 서로 같은 타입인가? 완벽히 동일한 타입은 아니다. 그러나 두 타입은 서로 같은 정보값을 표현할 수 있으며, 그 순서가 동일하다. 사상의 합성을 설명한 문단에서 괄호를 생략할 수 있음을 이미 설명한 바 있으므로, 둘은 완벽히 동일하지는 않지만 동형이므로 ‘같다고 치고’ 똑같은 방식으로 다룰 수 있다.
  2. 타입 (String, Boolean | Nothing)과 타입 (String, Boolean) | (String, Nothing)은 서로 같은 타입인가? 완벽히 동일한 타입은 아니다. 그러나 2번째 타입이 Boolean이면서 Nothing일 수는 없으므로, 각각의 경우에 대해 어떠한 결과가 나오는 지를 확인해보면 2번째 타입이 Boolean인 경우 (String, Boolean), Nothing인 경우 (String, Nothing)의 2가지가 나오며, 각 경우는 다른 하나를 절대 침범할 수 없다. 따라서 둘은 완벽히 동일하지는 않지만 동형이므로 ‘같다고 치고’ 똑같은 방식으로 다룰 수 있다.
  3. Nothing의 경우, 대수적 구조를 범주에 적용할 때 0처럼 사용할 수 있다. (String, Nothing)은 Nothing과 같은가? Nothing은 어떠한 값도 원소로 가질 수 없으며, 따라서 (String, Nothing) 형태의 어떠한 값을 만들려고 할 때 제공해줄 수 있는 값이 단 하나도 없다. 따라서 (String, Nothing)의 형태는 String에 어떤 값이 오든 관계없이 만들어질 수 없으며, 이 결과는 결국 Nothing과 같아진다. 따라서 a * 0 = 0의 형태를 보존한다고 볼 수 있다.

반환은 덧셈에 대해 교환법칙과 결합법칙의 성립을 만족해야 한다.

  1. 타입 Int | Boolean과 타입 Boolean | Int는 서로 같은 타입인가? 완벽히 동일한 타입은 아니다. 그러나 둘 중 어느 타입을 사용하든 그 결과는 변하지 않는다. Int가 주어지면 Int를 만들고, Boolean이 주어지면 Boolean을 만든다. 따라서 둘은 완벽히 동일하지는 않지만 동형이므로 ‘같다고 치고’ 똑같은 방식으로 다룰 수 있다.
  2. 타입 (Boolean | Int) | String과 타입 Boolean | (Int | String)은 서로 같은 타입인가? 완벽히 동일한 타입은 아니다. 그러나 곱셈의 결합법칙 부분에서 말했듯이, 괄호는 생략할 수 있음을 이미 설명하였으므로 둘은 완벽히 동일하지는 않지만 동형이고, 따라서 ‘같다고 치고’ 똑같은 방식으로 다룰 수 있다.

이로써 우리는 합 타입과 곱 타입을 이용한 타입 시스템이 대수적 구조인 반환과 동형임을 보였으며, 따라서 정해진 방식 안에서라면 어떻게든 연산을 수행하여도 그 엄밀성이 보장된다는 사실을 알게 되었다. 이 타입은 이제 우리 겁니다. 우리 마음대로(까지는 아니지만) 할 수 있는 겁니다.

패턴 매칭?

합 타입과 곱 타입을 통해 타입 시스템에 수학적 엄밀성을 부여하는 데 성공한 우리에게 있어 패턴 매칭은 사실 추가로 해야 하는 숙제가 아니라, 편의점에서 파는 1 + 1 행사상품과 같다고 볼 수 있다. 객체지향의 세계에서 타입 선언이란 메모리에 할당될 인스턴스를 만들기 위한 청사진을 만드는 것과 같다. 그러나 함수형의 세계에서 타입 선언이란 기존 타입을 입력으로 하고 새로운 타입을 출력으로 하는 함수를 만드는 것으로 이해할 수 있다. 별다른 요소가 더 있는 것이 아니고, 타입 선언 그 자체가 함수라는 것이다. 입력 타입의 값을 생성할 수 있는 함수를 모두 제공할 수 있다면 새로운 타입을 만들 수 있는 것이고, 그렇지 못하다면 타입 체커를 통과할 수 없다.

패턴 매칭은 타입 생성의 반대 방향으로 진행된다. 타입을 생성하기 위해 값을 생성할 수 있는 함수(이하 생성자, 객체지향의 생성자가 아님에 주의하자)들을 합과 곱을 이용하여 합성해야 했다면, 그 타입의 값을 사용하기 위해서는 합과 곱으로 합성된 생성자들로 ‘분해’하여, 그 각각에 따라 알맞은 처리를 해주어야 한다. 위에서 곱을 도출한 후, 반대 방향의 쌍대곱을 알아본 것과 비슷하다고 볼 수 있겠다.

분할 정복 알고리즘이라는 유명한 사고방식이 있다. 인간은 큰 규모의 문제를 단번에 해결할 수 없으며, 자신이 이해할 수 있는 만큼의 크기로 분할하여 각각을 해결한 다음, 그 결과를 합쳐서 큰 문제를 해결한다. 전산학을 배운 사람이라면 항상 유념해야 할 사고방식이며, 이는 복합 타입을 우리가 이미 알고 있는 타입들로 ‘분해’하는 것이나 기초 타입을 합과 곱을 이용해 복합 타입으로 ‘합성’하는 것이 굉장히 자연스러운 사고방식임을 알 수 있다.

정리

  1. 범주란 무엇인가? 범주는 대상과 사상의 모음이며, 시작 대상과 끝 대상이 같은 사상은 합성할 수 있다. 대상과 사상의 모음이 범주가 되기 위해서는 항등사상의 존재와 사상 합성의 결합법칙의 두 가지 조건을 만족해야 한다.
  2. 대수적 자료형이란, 타입에 대수적 구조를 적용하여 타입 간 덧셈과 곱셈 등의 연산을 가할 수 있게 했다는 의미이다.
  3. 곱 타입은 데카르트 곱에, 합 타입은 쌍대곱에 그 배경이 있으며, 각각에 상응하는 성질이 있기 때문에 그렇게 이름이 붙여졌다.
  4. 합 타입과 곱 타입을 적용한 타입 시스템은 반환과 동형이기 때문에 반환에서 사용하는 연산을 사용할 수 있다.
  5. 패턴 매칭은 타입 선언의 반대 방향으로 이루어지는 작업이며, (패턴 매칭, 타입 선언)의 관계는 마치 (곱, 쌍대곱)의 관계와 비슷하다.

관련 자료

  1. Category Theory Lecture from Bartosz Milewski
  2. Category Theory for Programmers
  3. Category Theory - Wikipedia 외 다수 항목