대수적 데이터 타입과 Enum

By | February 19, 2016

대수적 데이터 타입은 다른 데이터 타입을 조합 및 연산하여 하나의 새로운 집합을 정의할 때, 해당 집합을 대수적 데이터 타입이라고 한다. 쉽게 얘기해 집합을 정의하는 것이다.

헤스켈에서 대표적인 대수적 데이터 타입은 Bool 타입이다.

Bool 타입은 True타입과 False타입이 모여 Bool이라는 집합을 정의한다고 생각할 수 있다. 대수적 데이터 타입의 몇 가지 예를 더 살펴보자.

Point 집합은 Int Int 를 조합하여 만들어지는 집합이고 Either는 Left a 와 Right b 를 조합하여 만들어지는 집합니다.

대수적 데이터 타입이 왜 좋은가?

대수적 데이터 타입을 쓰면 패턴매칭과 재귀를 사용해 원하는 알고리즘을 쉽게 기술할 수 있기 때문이다. 이진 트리는 대표적인 재귀 타입인데 헤스켈로 트리를 정의해 보자.

Tree집합은 Leaf와 Node로 조합되는 집합이다. Leaf는 자식이 없는 Node의 특수한 경우다. Node는 두 개의 트리를 자식으로 갖는다. 이 예제에서 Node는 무조건 2개의 자식을 갖는다고 가정하고 있다.

위의 트리는 재귀를 사용하여 대수적 데이터 타입을 정의한 것이다. 이제 이 트리집합에서 특정 원소 a 가 존재하는지 검색하는 함수(알고리즘)를 기술해 보자.

패턴매칭과 재귀를 사용해 아주 간결하고 명확하게 알고리즘을 기술 할 수 있다.

Swfit의 Enum

Swift에서도 헤스켈처럼 대수적 데이터 타입을 정의하고 패턴 매칭을 사용해 알고리즘을 기술할 수 있을까? 그렇다 enum을 사용하면 가능하다. Swift 1.x 에서는 enum을 사용해 재귀적인 데이터 타입을 정의하기 어려웠지면 Swift 2.0 부터 indirect 키워드를 지원해 재귀적인 데이터 타입을 아주 쉽게 정의할 수 있다.

indirect가 필요한 이유는 enum이 값 타입이기 때문에 컴파일러가 컴파일할 때 해당 enum의 크기를 정확하게 알아야 한다. 하지만 재귀적으로 정의되어 있으면 자신의 크기를 구하기 위해 다시 자신의 크기를 구하는 무한 재귀 루프에 빠져버린다. 그래서 C,C++에서는 트리, 리스트 같은 재귀 데이터 구조를 작성할 때 포인터를 사용했던 것이다.

C, C++에 익숙한 사람들에게 enum은 단순히 플래그의 집합 정도로만 생각되기 쉽지만 Swift의 Enum은 패턴 매칭과 어울어져 Functional Programming에 다가가는 가교 역할을 하고 있다. 이제 Swift로 트리를 정의해 보고 트리를 검색하는 함수를 패턴 매칭을 사용해 기술 해 보자.

이렇게 정의한 트리는 아래처럼 사용할 수 있다.

이제 트리를 검색하는 함수를 패턴매칭을 사용해 기술해 보자.

함수를 사용해 보자.

아주 근사하다!

Kotlin의 data class

Kotlin도 data class 와 when 패턴 매칭을 사용하면 헤스켈처럼 대수적 데이터 타입을 기술할 수 있다. 위의 내용을 Kotlin으로 표현해 본 것은 아래와 같다.

트리를 검색하는 함수를 작성해 보자.

이제 트리를 정의하고 트리에서 원소를 검색해 보자.

Binary Search Three

아래는 Swift로 작성한 BST 코드이다.

 

참고

Share on FacebookTweet about this on TwitterShare on Google+Share on RedditEmail this to someone