맨위로가기

대수적 자료형

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

대수적 자료형은 1970년대 호프 프로그래밍 언어에서 처음 소개되었으며, 여러 프로그래밍 언어에서 지원하는 자료형의 한 종류이다. 대수적 자료형은 합 타입, 곱 타입, 재귀 자료형을 포함하며, 단일 연결 리스트, 이진 트리, 추상 구문 등을 표현하는 데 사용된다. 패턴 매칭을 통해 대수적 자료형의 값을 처리하며, 컴파일러는 패턴 매칭의 완전성을 검사하여 타입 안전성을 제공한다. 대수적 자료형은 재귀적 자료형의 합 타입과 곱 타입의 조합으로, 타입 이론에서는 람다 표기법을 사용하여 표현된다. 클린, 하스켈, OCaml, 스칼라, 코틀린 등 다양한 프로그래밍 언어에서 대수적 자료형을 지원한다.

2. 역사

대수적 자료형은 1970년대 에든버러 대학교에서 개발된 소규모 함수형 프로그래밍 프로그래밍 언어인 호프에서 처음 소개되었다.[2]

3. 개념

자료형 이론에서 대수적 자료형(algebraic data type|ADT영어)은 다른 자료형들을 조합하여 만들어지는 복합 자료형의 한 종류이다. 대수적 자료형은 크게 두 가지 방식으로 구성된다. 하나는 여러 자료형의 값들을 하나로 묶는 곱 타입(튜플, 레코드 등)이고, 다른 하나는 여러 자료형 중 하나의 값을 선택하여 나타내는 합 타입(태그가 있는 유니온, Variant 등)이다.

합 타입의 값은 보통 특정 생성자(constructor)와 그 생성자에 해당하는 인수로 구성된다. 생성자는 일종의 태그 역할을 하여 어떤 종류의 값인지를 구별해주며, 해당 생성자가 요구하는 타입의 값(인수)을 함께 가진다. 예를 들어, 이진 트리를 표현하는 대수적 자료형은 '리프 노드(Leaf)'와 '내부 노드(Branch)'라는 두 가지 경우를 가질 수 있다. 'Leaf' 생성자는 특정 데이터 값을 인수로 가질 수 있고, 'Branch' 생성자는 두 개의 하위 트리를 인수로 가질 수 있다. 어떤 값이 'Leaf'인지 'Branch'인지는 생성자를 통해 구별된다. 만약 생성자가 인수를 가지지 않는다면, 이는 열거형과 유사하게 단순히 특정 상태나 종류를 나타낸다. 반대로 생성자가 단 하나만 존재한다면, 이는 사실상 곱 타입과 동일하게 여러 값을 묶는 역할을 한다.

대수적 자료형은 재귀적으로 정의될 수 있다. 즉, 자료형의 정의 안에 자기 자신이 포함될 수 있다. 이는 리스트나 트리와 같이 자기 참조적인 구조를 가진 자료 구조를 자연스럽게 표현하는 데 매우 유용하다. 예를 들어, 리스트는 '빈 리스트'이거나 '어떤 값과 나머지 리스트의 결합'으로 정의될 수 있으며, 트리는 '리프 노드'이거나 '값과 여러 개의 하위 트리들의 결합'으로 정의될 수 있다.

집합론적 관점에서 보면, 대수적 자료형은 직합(disjoint union) 개념과 유사하다. 합 타입은 여러 가능한 타입들의 직합으로 볼 수 있으며, 각 타입에 해당하는 값들은 고유한 태그(생성자)를 통해 구분된다. 곱 타입은 여러 타입들의 곱집합에 해당한다. 따라서 대수적 자료형은 기본적으로 여러 곱 타입들의 합으로 구성된 형태라고 할 수 있다.

함수형 프로그래밍 언어에서는 대수적 자료형을 사용하여 추상 자료형을 구현하기도 한다. 모듈 시스템 등을 이용해 생성자를 직접 노출하지 않고, 대신 데이터를 생성하고 조작하는 함수만을 외부에 공개함으로써 내부 구현을 감추고 인터페이스만을 제공할 수 있다. 이때 외부에 공개된 함수가 객체 지향 언어의 생성자와 유사한 역할을 수행한다. 데이터의 내부 구조에 접근하거나 값을 변경할 때는 주로 패턴 매칭 기법이 사용된다.

3. 1. 예시

대수적 자료형은 다양한 자료 구조와 개념을 간결하고 명확하게 표현하는 데 효과적으로 사용된다. 대표적인 예시로는 함수형 프로그래밍 언어에서 기본적인 자료 구조로 활용되는 단일 연결 리스트가 있다. 또한, 재귀 자료형의 대표적인 예시인 이진 트리와 같이 더 복잡한 구조도 대수적 자료형을 통해 명확하게 정의하고 다룰 수 있다. 더 나아가, 프로그래밍 언어의 구문을 추상적인 형태로 표현하고 이를 분석하거나 변환하는 작업에도 대수적 자료형이 유용하게 활용된다.

3. 1. 1. 단일 연결 리스트

대수적 자료형의 가장 흔한 예시 중 하나는 단일 연결 리스트이다. 리스트 타입은 두 가지 경우를 가진 합 타입으로, 빈 리스트를 나타내는 'Nil'과 새로운 요소 ''x''와 리스트 ''xs''를 결합하여 새로운 리스트를 생성하는 'Cons ''x'' ''xs'''가 있다. 다음은 Haskell에서 단일 연결 리스트를 선언하는 예시이다.



data List a = Nil | Cons a (List a)



또는



data [] a = [] | a : [a]



'Cons'는 'construct'(생성)의 약자이다. 많은 언어에서 이 방식으로 정의된 리스트에 대한 특별한 구문을 사용한다. 예를 들어, Haskell과 ML은 'Nil'에 대해 '[]', 'Cons'에 대해 ':' 또는 '::'를 각각 사용하며, 전체 리스트에 대괄호를 사용한다. 따라서 'Cons 1 (Cons 2 (Cons 3 Nil))'는 Haskell에서는 일반적으로 '1:2:3:[]' 또는 '[1,2,3]'으로, ML에서는 '1::2::3::[]' 또는 '[1,2,3]'으로 작성된다.

기본적인 대수적 자료형으로, 많은 함수형 언어에서 언어 내장 리스트 형이 제공되며, 빈 리스트를 위한 생성자에 해당하는 리터럴과, 추가하고 싶은 요소와 나머지 리스트를 인수로 취하는 생성자(Lisp의 cons)에 해당하는, 중위 표기법 스타일의 생성자(":" 등)가 언어 내장 기능으로 준비되어 있는 경우가 많다.

3. 1. 2. 이진 트리

이진 트리는 대수적 자료형으로 표현할 수 있는 더 복잡한 자료 구조의 예시이다. Haskell에서는 다음과 같이 `data` 선언을 사용하여 이진 트리를 정의할 수 있다.



data Tree = Empty -- 빈 트리

| Leaf Int -- 정수 값을 가지는 리프 노드

| Node Int Tree Tree -- 정수 값과 두 개의 서브 트리를 가지는 노드



여기서 `Empty`는 아무것도 없는 빈 트리를 나타내고, `Leaf`는 데이터를 담고 있는 끝 노드(리프 노드)를 의미한다. `Node`는 데이터와 함께 두 개의 하위 트리(왼쪽 자식과 오른쪽 자식)를 가지는 분기 노드를 구성한다. `Leaf` 생성자는 정수(`Int`) 하나를 받아 `Tree` 타입의 값을 만들고 (`Int -> Tree`), `Node` 생성자는 정수 하나와 두 개의 `Tree` 타입 값(자기 자신을 참조)을 받아 새로운 `Tree` 값을 만든다. 이처럼 자기 자신을 참조하여 정의되는 데이터 타입을 재귀 자료형이라고 한다.

다른 예시로, 리프 노드에만 값을 저장하는 형태의 이진 트리는 다음과 같이 정의할 수도 있다.



data Node = Leaf Integer -- 정수 값을 가지는 리프 노드

| Branch Node Node -- 두 개의 서브 노드를 가지는 분기 노드



대수적 자료형으로 정의된 데이터에 대한 연산은 주로 패턴 매칭을 사용하여 구현한다. 예를 들어, 위에서 정의한 `Tree` 타입의 깊이를 계산하는 Haskell 함수는 다음과 같다.



depth :: Tree -> Int

depth Empty = 0 -- 빈 트리의 깊이는 0

depth (Leaf n) = 1 -- 리프 노드의 깊이는 1

depth (Node n l r) = 1 + max (depth l) (depth r) -- 노드의 깊이는 1 + (두 서브 트리의 깊이 중 큰 값)



이 `depth` 함수는 입력으로 주어진 `Tree`가 `Empty`, `Leaf`, `Node` 중 어떤 생성자로 만들어졌는지 각 경우에 따라 패턴 매칭을 수행한다. `Node`의 경우에는 패턴 `(Node n l r)`을 통해 노드의 값 `n`과 왼쪽 서브 트리 `l`, 오른쪽 서브 트리 `r`을 추출하여 재귀적으로 깊이를 계산한다.

OCaml (전통적인 ML 계열 언어)에서는 변형 타입(variant type)이라고 부르며, 유사한 이진 트리를 다음과 같이 정의할 수 있다.



type node = Leaf of int | Branch of node * node



OCaml에서는 `of` 키워드 뒤에 생성자가 받는 인수의 타입을 명시한다. `Branch` 생성자처럼 여러 인수를 받는 경우, 튜플을 사용하여 `node * node` 형태로 표현한다. 패턴 매칭은 `match ... with` 구문을 사용한다.



let rec depth tree = match tree with

| Leaf _ -> 1

| Branch (a, b) -> 1 + max (depth a) (depth b)



Visual Prolog에서도 대수적 자료형과 유사한 방식으로 트리를 정의할 수 있다.



domains

tree =

empty(); (* 빈 트리 *)

leaf(integer Leaf); (* 정수 값을 가지는 리프 *)

node(tree Left, tree Right). (* 두 서브 트리를 가지는 노드 *)



이처럼 대수적 자료형은 다양한 프로그래밍 언어에서 복잡한 자료 구조를 간결하고 명확하게 표현하는 데 유용하게 사용된다. 또한, 매개변수 다형성을 지원하는 언어에서는 특정 타입(예: `Int`, `Integer`)에 국한되지 않고 다양한 타입의 데이터를 저장할 수 있는 일반적인 트리 타입을 정의할 수도 있다. 예를 들어 Haskell에서는 다음과 같이 타입 변수 `a`를 사용하여 어떤 타입의 값이든 저장할 수 있는 이진 트리를 정의할 수 있다.



data BinaryTree a = BTNil

| BTNode a (BinaryTree a) (BinaryTree a)


3. 1. 3. 추상 구문

대수적 자료형은 추상 구문을 구현하는 데 매우 적합하다. 예를 들어, 아래의 대수적 자료형은 숫자를 이용한 표현식을 나타내는 간단한 언어를 설명한다.



data Expression = Number Int

| Add Expression Expression

| Minus Expression Expression

| Mult Expression Expression

| Divide Expression Expression



이 자료형을 사용하면 Mult (Add (Number 4) (Minus (Number 0) (Number 1))) (Number 2)와 같은 형태로 표현식을 나타낼 수 있다.

이러한 자료형을 기반으로 표현식의 값을 계산하는 평가 함수를 작성하는 것은 비교적 간단하다. 더 나아가, 컴파일러의 최적화 과정처럼 추상적인 표현식을 입력받아 더 효율적인 형태로 변환하는 함수를 작성하는 등 복잡한 변환 작업에도 활용될 수 있다.

4. 패턴 매칭

대수적 자료형의 값을 다루기 위해 패턴 매칭을 사용한다. 이는 값을 해당 데이터 종류를 나타내는 생성자(예: 이진 트리 `Tree`의 `Empty`, `Leaf`, `Node`)에 따라 여러 패턴과 비교하여 분해하는 과정이다. 각 생성자는 각기 다른 종류나 개수의 데이터를 가질 수 있다. 예를 들어, `Tree` 자료형에서 `Empty` 생성자는 데이터를 가지지 않지만, `Leaf` 생성자는 정수 값 하나를, `Node` 생성자는 두 개의 하위 `Tree` 값을 가진다.

패턴 매칭은 값의 구조를 분해하는 데 사용된다. 예를 들어, `Tree` 자료형의 깊이를 계산하는 `depth` 함수는 주어진 `Tree` 값을 다음과 같은 패턴들과 순서대로 비교한다.


  • 값이 `Empty` 생성자와 일치하는 패턴: 특정 동작(예: 깊이 0 반환)을 수행한다.
  • 값이 `Leaf` 생성자와 일치하는 패턴: `Leaf`가 가진 데이터(정수 값)를 변수(예: `n`)에 할당하고, 이를 사용하여 계산한다(예: 깊이 1 반환).
  • 값이 `Node` 생성자와 일치하는 패턴: `Node`가 가진 두 개의 하위 `Tree`를 각각 변수(예: `l`, `r`)에 할당하고, 이 변수들을 재귀적으로 사용하여 계산한다(예: `1 + max (depth l) (depth r)`).


함수가 호출되면, 인자와 일치하는 첫 번째 패턴을 찾아 해당 패턴 내의 변수에 값을 할당(바인딩)하고, 패턴에 연결된 표현식을 평가한다. 패턴은 생성자의 구조를 반영하며, 재귀적일 수 있어 복잡하게 중첩된 데이터 구조(예: 레드-블랙 트리의 균형 조정)도 효과적으로 처리할 수 있다.

패턴 매칭은 다음과 같은 장점을 가진다.

첫째, 타입 안전성을 높인다. 각 패턴은 특정 생성자에 해당하므로, 해당 생성자가 가지는 데이터의 종류와 수에 맞춰 안전하게 값을 추출할 수 있다. 예를 들어, `Leaf` 패턴에서는 정수 값만 접근하고, `Node` 패턴에서는 두 개의 하위 `Tree`만 접근하게 된다. 이는 컴파일러가 데이터 접근 오류(예: `Leaf` 값에서 하위 트리에 접근하려는 시도)를 컴파일 시점에 방지할 수 있게 해준다. 이는 전통적인 레코드 데이터 구조와 `switch` 문과 유사한 방식(예: 의사 코드에서 `data.constructor`를 확인하고 `data.field1`, `data.field2`에 접근하는 방식)을 사용할 때 프로그래머의 주의가 필요한 것과 대조된다.

둘째, 완전성(exhaustiveness) 검사가 가능하다. 컴파일러는 패턴 매칭이 정의된 모든 생성자(즉, 모든 가능한 경우)를 처리하는지 검사할 수 있다. 만약 누락된 경우가 있다면 컴파일러는 경고를 표시하여, 런타임 오류로 이어질 수 있는 불완전한 처리를 방지한다. 이는 복잡한 재귀 패턴이 많을 경우 특히 유용하다. 마찬가지로, 이미 이전 패턴에서 처리되어 실제로는 도달할 수 없는 중복되거나 불필요한 패턴에 대해서도 컴파일러가 검사하고 경고하여 논리적 오류를 발견하는 데 도움을 줄 수 있다.

대수적 자료형의 패턴 매칭은 문자열의 내용을 검색하고 처리하는 정규 표현식의 패턴 매칭과는 구별된다. 대수적 자료형 패턴 매칭은 데이터의 구조적 속성을 기반으로 값을 분해하고 일치시키는 방식이다.

Haskell과 같은 함수형 프로그래밍 언어에서는 대수적 자료형과 패턴 매칭이 핵심적인 기능으로 사용된다. 예를 들어, 이진 트리를 선언하고, `case ... of` 구문을 사용하여 트리의 깊이를 계산하는 함수를 패턴 매칭을 통해 간결하고 안전하게 구현할 수 있다.

5. 이론

일반적인 대수적 자료형은 재귀적 자료형, 합 타입, 곱 타입으로 이루어진다. 각 생성자는 다른 생성자와 구별하기 위해 곱 타입을 태그(tag)하며, 만약 생성자가 하나뿐이라면 해당 자료형은 곱 타입이 된다. 생성자의 매개변수 타입은 곱 타입의 요소가 되며, 매개변수가 없는 생성자는 공집합 곱에 해당한다. 자료형이 재귀적일 경우, 곱의 전체 합은 재귀 타입으로 감싸지며(wrapped), 각 생성자는 자료형을 재귀 타입으로 롤(roll)하는 역할을 한다.[3]

대수적 자료형의 특수한 예로는 하나의 생성자만 가지는 직적형(곱 타입)과, 인수가 없는 여러 생성자를 가지는 열거형이 있다.

타입 이론의 관점에서 대수적 자료형을 살펴보자. 예를 들어, Haskell에서 리스트 자료형은 다음과 같이 정의될 수 있다.



data List a = Nil | Cons a (List a)



이는 타입 이론에서 다음과 같이 표현될 수 있다.

\lambda \alpha. \mu \beta. 1 + \alpha \times \beta

여기서 생성자 \mathrm{Nil}과 \mathrm{Cons}는 각각 다음과 같이 표현된다.

\mathrm{nil}_\alpha = \mathrm{roll}\ (\mathrm{inl}\ \langle\rangle)

\mathrm{cons}_\alpha\ x\ l = \mathrm{roll}\ (\mathrm{inr}\ \langle x, l\rangle)

이 Haskell `List` 자료형은 타입 이론에서 약간 다른 형태로도 표현될 수 있다.

\mu \phi. \lambda \alpha. 1 + \alpha \times \phi\ \alpha

(\mu와 \lambda의 순서가 이전 표현과 반대임에 유의해야 한다.) 첫 번째 형식은 본문이 재귀 타입인 타입 함수를 정의한 것이고, 두 번째 형식은 타입에 대한 재귀 함수를 정의한 것이다. (타입 변수 \phi는 기본 타입이 아닌 함수임을 나타낸다.) 함수는 이제 타입 본문 내에서 인자 타입 \alpha에 \phi를 적용해야 한다.

`List` 예제의 경우 이 두 표현 방식에 큰 차이는 없지만, 두 번째 형태는 소위 중첩된 자료형(nested data type)을 표현할 수 있게 해준다. 중첩된 자료형은 재귀 타입이 원래 타입과 매개변수적으로 다른 경우를 의미한다. (더 자세한 내용은 리처드 버드, 람베르트 메르텐스, 로스 패터슨 등의 연구를 참조할 수 있다.)

집합론에서 합 타입에 해당하는 개념은 분리된 합집합(disjoint union)이다. 이 집합의 각 원소는 태그(생성자와 동일한 역할)와 그 태그에 해당하는 타입의 객체(생성자의 인수와 동일한 역할)로 구성된 쌍이다.[3]

생성자는 타입만 보면 함수와 유사해 보일 수 있다. 예를 들어 Haskell 이진 트리 예시에서 `Leaf` 생성자는 `Integer -> Node` 타입을, `Branch` 생성자는 `Node -> Node -> Node` 타입을 가진다. 하지만 함수와 달리 생성자는 평가(실행)되지 않고 단순히 데이터를 구성하는 역할을 한다. 즉, 함수 적용식은 축약될 수 있지만, 생성자로 만들어진 식은 그 자체로 값을 나타내며 더 이상 축약되지 않는다.

6. 대수적 자료형을 지원하는 프로그래밍 언어

많은 프로그래밍 언어는 대수적 자료형을 일급 개념으로 통합하고 있으며, 여기에는 다음이 포함된다.

참조

[1] 웹사이트 Records and variants http://caml.inria.fr[...] 2020-04-28
[2] 간행물 Proceedings of the third ACM SIGPLAN conference on History of programming languages http://dl.acm.org/ci[...] 2007-06-09
[3] 문서 Algebraic+data+type
[4] 문서 Calculus of Inductive Constructions https://coq.inria.fr[...]
[5] 웹사이트 CppCon 2016: Ben Deane "Using Types Effectively" https://www.youtube.[...]
[6] 웹사이트 Sealed class modifier https://dart.dev/lan[...]
[7] 웹사이트 Algebraic Data Types in Haskell https://serokell.io/[...]
[8] 웹사이트 Enum Instance https://haxe.org/man[...]
[9] 웹사이트 JEP 395: Records https://openjdk.org/[...]
[10] 웹사이트 JEP 409: Sealed Classes https://openjdk.org/[...]
[11] 웹사이트 Sealed Classes - Kotlin Programming Language https://kotlinlang.o[...]
[12] 웹사이트 Reason · Reason lets you write simple, fast and quality type safe code while leveraging both the JavaScript & OCaml ecosystems. https://reasonml.git[...]
[13] 웹사이트 Enums and Pattern Matching - The Rust Programming Language https://doc.rust-lan[...] 2021-08-31
[14] 웹사이트 Calculus of Inductive Constructions https://coq.inria.fr[...]
[15] 웹인용 CppCon 2016: Ben Deane "Using Types Effectively" https://www.youtube.[...]
[16] 웹인용 Enum Instance https://haxe.org/man[...]
[17] 웹인용 JEP 360: Sealed Classes (Preview) https://openjdk.java[...]
[18] 웹인용 Reason · Reason lets you write simple, fast and quality type safe code while leveraging both the JavaScript & OCaml ecosystems. https://reasonml.git[...]
[19] 웹인용 Sealed Classes - Kotlin Programming Language https://kotlinlang.o[...]


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com