Burt.K

코코아를 좋아하는 프로그래머입니다 ;)

대수적 데이터 타입과 Enum

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

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

data Bool = True | False

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

data Point = Point Int Int
data Either a b = Left a | Right b

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

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

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

data Tree a = Leaf a 
            | Node a (Tree a) (Tree a)

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

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

inTree :: Eq a => a -> Tree a -> Bool
inTree x (Leaf a) = a == x
inTree x (Node a l r) = x == a || (inTree x l) || (inTree x r)

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

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로 트리를 정의해 보고 트리를 검색하는 함수를 패턴 매칭을 사용해 기술 해 보자.

indirect enum Tree<T> {
    case Leaf(T)
    case Node(Tree<T>, T, Tree<T>)
}

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

let tree : Tree<Int> = Tree.Node(.Leaf(2), 4, .Leaf(5))
let tree2 : Tree<Int> = Tree.Node(.Leaf(2), 3, .Node(.Leaf(4), 5, .Leaf(10)))

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

func inTree<T: Equatable>(ele: T, tree: Tree<T>) -> Bool {
    switch tree {
    case .Leaf(let x):
        return x == ele
    case .Node(let left, let x, let right):
        return x == ele || inTree(ele, tree: left) || inTree(ele, tree: right)
    }
}

함수를 사용해 보자.

inTree(5, tree: tree2) 
=> true
inTree(1, tree: tree2) 
=> false

아주 근사하다!

Kotlin의 data class

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

interface Tree<T>
data class Leaf<T>(val value : T) : Tree<T>
data class Node<T>(val left: Tree<T>, val value: T, val right: Tree<T>) : Tree<T>

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

fun <T> inTree(t: Tree<T>, v : T) : Boolean  = when(t) {
	is Leaf -> t.value == v
    is Node -> t.value == v || inTree(t.left, v) || inTree(t.right, v) 
    else -> false
}

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

fun main(args: Array<String>) {
    val tree = Node<Int>(Leaf(1), 2, Node(Leaf(3), 4, Leaf(5)))
    print(inTree(tree, 3))
    print(inTree(tree, 6))
}

Binary Search Three

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

import Cocoa

indirect enum BST<T: Comparable> {
    case Leaf
    case Node(BST<T>, T, BST<T>)
}



extension BST {
    
    init(_ value: T) {
        self = .Node(.Leaf, value, .Leaf)
    }
    
    init() {
        self = .Leaf
    }
    
    mutating func insert(x: T) {
        switch self {
        case .Leaf:
            self = BST(x)
        case .Node(var left, let v, var right):
            if x < v { left.insert(x) }
            if x > v { right.insert(x) }
            self = .Node(left, v, right)
        }
    }
    
    func contains(x: T) -> Bool {
        switch self {
        case .Leaf:
            return false
        case let .Node(_, y, _) where x == y:
            return true
        case let .Node(left, y, _) where x < y:
            return left.contains(x)
        case let .Node(_, y, right) where x > y:
            return right.contains(x)
        default:
            return false
        }
    }
    
    
    
    var count: Int {
        switch self {
        case .Leaf:
            return 0
        case let .Node(left, _, right):
            return left.count + 1 + right.count
        }
    }
    
    var elements: [T] {
        switch self {
        case .Leaf:
            return []
        case let .Node(left, x, right):
            return left.elements + [x] + right.elements
        }
    }
    
    var isEmpty: Bool {
        switch self {
        case .Leaf:
            return true
        default:
            return false
        }
    }
    
    var isBST: Bool {
        switch self {
        case .Leaf:
            return true
        case let .Node(left, x, right):
            return left.elements.all { y in y < x }
                && right.elements.all { y in y > x }
                && left.isBST
                && right.isBST
        }
    }
}

extension Array {
    func all<T> (predicate: (T) -> Bool) -> Bool {
        for x in self {
            let t = x as! T
            if !predicate(t) {
                return false
            }
        }
        return true
    }

}

var bst = BST.Node(.Leaf, 10, .Leaf)
bst.insert(20)
bst.insert(30)
bst.insert(1)
bst.contains(20)
bst.contains(102)
bst.elements
bst.count
bst.isEmpty
bst.isBST

 

참고

← 함수를 정의하자.
Swift로 아주 큰 수를 곱해 보자. →