Swift 2.0 の indirect で2分探索木(Binary search tree)を試す

indirectが使用できる前はBoxクラスなんかを使って再帰的なenumデータ型 を実装していたみたいだが、indirectを使えばBoxクラス等を使わずにシンプルにList, Tree なんかを書ける。

環境

• Xcode 7.0 beta 4
• Swift 2.0

2分探索木

元ネタは すごいHaskellたのしく学ぼう! の第７章の再帰的なデータ構造

木

indirectで木を定義

indirect enum Tree<T> {
    case EmptyTree
    case Node(T, left: Tree<T>, right: Tree<T>)
}

要素と２つの空部分木からなるノードを作る関数

func singleton<T>(a: T) -> Tree<T> {
    return .Node(a, left: .EmptyTree, right: .EmptyTree)
}

2分探索木に要素を挿入する関数

func treeInsert<T: Comparable>(x: T, tree: Tree<T>) -> Tree<T> {
    switch tree {
    case .EmptyTree:
        return singleton(x)

    case let .Node(a, left: left, right: right):
        if x == a {
            return .Node(a, left: left, right: right)
        } else if x < a {
            return .Node(a, left: treeInsert(x, tree: left), right: right)
        } else {
            return .Node(a, left: left, right: treeInsert(x, tree: right))
        }
    }
}