대수 타입 Algebraic data type

혼자서 오랫동안 들고 있다 보니, 용어 하나 하나에 집착이 심해졌습니다. 용어의 진짜 속 뜻을 놓쳐 헤매는 일을 줄이고 싶다란 생각에 그런 듯 합니다. 진도를 느리게 하는 안좋은 습관이기도 합니다. 이 포스트는 공부한 결과를 정리한게 아니라, 풀지 못한 의문을 정리했습니다.

하스켈 문서들을 보다 보면, algebraic이란 말을 정말 많이 만납니다. 대수적이다란 말에서 어떤 뜻, 뉘앙스를 잡아내야 할까요? 대수 구조는 모여 있는 구성원들 사이에 연산이 존재하고, 일정한 규칙을 따르면 대수 구조라 말합니다. 구조를 떼어내고 대수란 말만, algebraic이란 말만 붙여 놓으면 무슨 뜻일까요?

위키피디아에 따르면 수를 대신한다는 의미로 중국 학자가 대수란 번역을 사용했다고 하는데, 역시나 번역 의미로 영어권 사람들이 사용하는 말은 아닌 것 같습니다. 어떨 때 algebraic이란 말을 붙일까요?

다른 타입들의 조합으로 구성된 타입이 대수 타입이다?

다른 타입을 감싸고 있는 타입을 대수 타입이라 한다고 되어있는 곳이 있고, 여러 타입의 조합으로 이루어진 타입이란 정의를 내리는 곳도 있습니다.
a datatype in computer programming each of whose values is data from other datatypes wrapped in one of the constructors of the datatype - https://en.wikipedia.org/wiki/Algebraic
data () = () 는 다른 타입을 감싼 모양도 아니고, 타입의 조합도 아니지만 대수 타입 종류 중에 unit type에 속합니다. data Bool = True | False 불린 데이터 타입도 다른 타입을 래핑하지 않지만, sum 종류의 대수 타입입니다. 타입을 감싸거나, 조합한다는 정의만으론 부족해 보이는데, 왜 다른 타입으로 래핑한 타입을 대수 타입이라 불렀을까요?

모든 타입은 대수 타입이다?

모든 타입들은 나중에 어떤 함수에겐가는 인자로 들어갈텐데, 그럼 모두 연산이 존재한다고 볼수 있고, 이 연산들의 결과로 자신들만의 구조가 생길텐데, 그럼 모두 대수 타입이라 볼 수 있는 건 아닐까요? 문서들을 보면 sums, products, recursive, unit 형태만 대수 타입이라 부르니, 모든 타입이 대수 타입인 건 아닌가 봅니다. 그런데, 이 모양들 이외의 모양이 뭐가 있을까요?

근원

Hope (programming language) - Wikipedia Hope란 언어에서 처음 나온 용어라 하는데(개념 자체가 처음일리는 없고, 명시적인 용어가 처음이지 않을까요?) Hope에 깊이 들어가지 않기 위해 잠깐 모양만 보면

Hope언어에서 factorial 예시

dec fact : num -> num;
    fact 0 <= 1;
    fact n <= n*fact(n-1);

이런 모양의 언어로 하스켈의 조상쯤 되는 Miranda 보다 먼저 나왔던 언어로 ML과 비슷한 시기에 나왔다고 합니다. 하스켈과 많이 닮아 있습니다.

Sum, Product, recursive, unit

대표적인 대수 타입 종류class가 product types, sum types입니다. 좁은 뜻으로 product와 sum형태만 대수 타입이라고 말하는 자료들도 만납니다.

Product 타입

data Pair = P Int Double 

Sum 타입

data Pair = I Int | D Double

일반적인 데이터 구조는 sums, products, recursive, unit 타입으로 설명할 수 있습니다. 해외 하스켈 커뮤니티에서 정말 활발히 글을 공개하고 있는 Gabriel Gonzalez의 글이 꽤 직관적인 것 같습니다.
https://www.schoolofhaskell.com/school/to-infinity-and-beyond/pick-of-the-week/sum-types

타입에 속하는 값들이 각각의 모양을 가지고 있을 때

https://wiki.haskell.org/Algebraic_data_type 엘리먼트들의 모양을 각각 지정하는 타입으로 설명합니다. “Algebraic Data Type은 algebraic 연산으로 만든다. 여기서 쓰인 algebra는 sums와 products다.”
역시 잘 와닿지 않긴 한데, sums와 products를 연산으로 볼 수 있다는 아이디어를 얻었습니다.

Sum 타입

하스켈에선 전혀 모양이 비슷하지 않은 값들을 하나의 타입으로 묶어 사용할 수 있습니다.

data Maybe a = Just a | Nothing
data Something = Val1 Int | Val2 Bool
...

※ 그런데, 다른 타입을 감싸고 있는 게 대수 타입이라 했으니, 감싸지 않게 다음 모양으로 하면 대수 타입이 아닌 걸까요?

data Something = Int | Bool

이렇게 정의하는게 가능하긴 한데, 따로 생성자 없이 정수, 불린을 묶어 한 타입으로 묶겠다는 의미와는 다르게 작동합니다.

위의 오른 쪽에 있는 Int, Bool 은 값 생성자로 Int 타입, Bool 타입과는 아무 관계가 없습니다. 그냥 사용자가 지정한 인자가 없는Nullary 값 생성자일 뿐입니다.

data Something = Some1 | Some2 

이렇게 써준 것과 같은 상황입니다. 값에 Int 타입의 값을 넣어주려면 값 생성자를 따로 지정하는 수 밖에 없습니다.

> data Something = Int Int | Bool Bool
> let a = Int 3
> :t a
a :: Something

Int Int에서 앞에 Int는 사용자가 새로 정의한 값 생성자이고, 뒤에 Int는 Int타입을 인자로 갖는다는 뜻입니다. Int 타입을 가지고 있는 새로운 타입을 만들려면 Int를 래핑한 모양으로 만듭니다.

Algebraic …

https://en.wikipedia.org/wiki/Algebraic
Algebraic functions , 다항식을 만족하는 함수
Algebraic definition, 양쪽 항이 같음을 이용한 수학 논리적 정의
Algebraic expression, 상수, 변수, 연산으로 이루어진 표현식
Algebra에서 다뤘던 주제들 (군, 환 같은 추상 대수학이나 방정식 같은 이론들)과 관련된 어떤 걸 얘기 할 때 Algebraic이란 말을 붙이고, 연산이 존재하는 대상들의 집합이라는 단어 뜻에 맞춰 쓰이기도 합니다.

방정식

방정식을 가능한 한 추상화해서 설명하면, 이미 알고 있는 대상들과 모르는 대상들이 섞여 있는 서로 다른 모양의 표현식이 같음을(관계를) 이용하여 모르는 대상을 알아내는 전체 표현식을 방정식이라 합니다. 이 방정식을 푸는 방법을 연구하는 분야를 대수학이라 불렀습니다.

그래서 지금까지 이해한 대수 타입이란?

연산(관계)을 거쳐 집합 내 다른 값으로 바뀌는 엘리먼트들의 관계를 대수적이라 말합니다. 왜 Sum 타입과 Product 타입이 대수적일까요? 타입에 속하는 값 레벨에서 보는 게 아니라, 타입만 놓고 봤을 때,

서로 다른 타입들끼리 묶여, 어떤식으로든 관계가 맺어져 새로운 타입이 되는 타입을 대수 타입이라 합니다.

제 생각은, 어떤 타입을 꼭 래핑하고 있어야 하는 건 아니라는 결론입니다. 새로운 타입을 만들기 위해 하나 이상의 타입이 쓰이기만 하면 됩니다.

넓은 의미로 보면, 또는 엄격하게 정의에만 기대서 본다면 모든 타입이 대수 타입으로 볼 수 있습니다. 하지만, 프로그래밍 언어에서 콕 집어 말할 때는 Sum, Product 관계로 여러 타입들이 묶인 걸 말합니다. (이렇게 말하는게 정확한지 의견을 나눴으면 좋겠습니다.)

여러 타입이 동시에 참여 해서 새로운 타입 값이 정해지는 걸 Product 타입, 여러 타입 중 하나가 새로운 타입의 값이 될 수 있는 타입을 Sum 타입이라 부릅니다. Product 형태와 Sum 형태를 타입을 만들기 위한 연산으로 볼 수 있습니다. Product 형태와 Sum 형태는 타입들간의 관계에 대한 구분입니다.

data PairProduct = P Int Double 
data PairSum = I Int | D Double

I와 D는 Or(Sum “연산”)의 관계로 묶여 PairSum이 되는 관계에 있습니다.
P는 Int와 Double을 묶어 (Product “연산”) PairProduct가 되는 관계에 있습니다.

이렇게 해석하면

data () = ()

값 생성자 () 하나(Unit “연산”)로 타입 생성자 ()이 되는 관계에 있습니다.

ADT - Abstract Data Type

Algebraic Data Type 과 Abstract Data Type 이 동일한 줄임말을 쓰니 헷갈릴 수 있습니다.

아!, 대수학 깊숙히 들어갔다 나오면 당연히 더 많이 알게 되겠지만, 그렇게까지 빠지면 하스켈을 포기하기 십상이라, 가능하면 가벼운 문서들만을 봤습니다.

Algebra of ADT

Product 타입을 곱으로 놓고, Sum 타입을 합으로 놓고, 익숙하게 해왔던 산술 계산을 하면 타입이 가지는 경우의 수(Counting inhabitants)를 계산할 수 있습니다.

Algebra and Calculus of Algebraic Data Types

[1] 용어를 궁금해 하는 사람들이 많긴 많나봅니다. 하지만 이해하기 좋은 딱부러지는 문서를 못찾았습니다. Wikipedia 추상 대수학 관련 대화