[Swift] 再帰enumで単連結リストを実装する

Xcode 7 beta 4からSwiftのenumのcaseの型に自分と同じ型を利用して、再帰構造をつくることができるようになりました。

これを利用して、単連結リストを実装してみました。

indirect case

Xcode 7 beta 4からSwiftに新キーワードindirectが追加されています。 これを利用するとAssociate Valueに自分と同じ型を指定することができます。

それを利用することで、次のように単連結リストをつくることができます。

enum List<T> {
    case Nil
    indirect case Cons(head: T, tail: List<T>)
}

例えば、次のようにリストをつくることができます。

let list = List.Cons(head: 7, tail: .Cons(head: 5, tail: .Cons(head: 8, tail: .Nil)))
// => Cons(7, List<Swift.Int>.Cons(5, List<Swift.Int>.Cons(8, List<Swift.Int>.Nil)))

このままではリストを作るのがかなり面倒だったり、表示が見づらいので、そこらを拡張していきます。

CustomStringConvertible

まず、CustomStringConvertibleプロトコルを実装して、結果の表示がわかりやすくなるようにカスタマイズします。

extension List: CustomStringConvertible {
    var description: String {
        switch self {
        case .Nil: return "[]"
        case .Cons(let v): return "\(v.head):\(v.tail)"
        }
    }
}

これで次のように表示されるようになります。

print(list)
// => "7:5:8:[]"

ArrayLiteralConvertible

続いて、配列から簡単にリストを作成できるようにします。

extension List {
    init(_ elements: [T]) {
        self = elements
            .reverse()
            .reduce(.Nil) { (a, e) in
                return List.Cons(head: e, tail: a)
        }
    }
}

外部パラメタ名を_にしたので、パラメタ名を省略して簡単に書けるようになりました。

let list2 = List([9, 8, 4, 5, 6])
// => 9:8:4:5:6:[]

このままでもかなり楽になりました。配列リテラルから自動で変換させたいので、さらにArrayLiteralConvertibleプロトコルを実装します。

extension List: ArrayLiteralConvertible {
    init(arrayLiteral elements: T...) {
        self.init(elements)
    }
}

これで配列リテラルからの自動変換が効くようになります。

let list3: List = [1, 5, 4, 2]
// => 1:5:4:2:[]

SequenceType, map, reduce

最後にこのList型でmapやreduceを使えるようにしましょう。

Swift 2.0からはmapやreduceはプロトコル拡張として、SequenceTypeプロトコルに実装済みです。

よって、ListをSequenceTypeプロトコルに適合させるだけでこれらのメソッドが利用できるようになります。

SequenceTypeプロトコルに適合させるには、先頭から要素をひとつづつ取るようなジェネレータを得るメソッドgenerateを実装します。

extension List: SequenceType {
    typealias Generator = ListGenerator<T>
    func generate() -> Generator {
        return ListGenerator(list: self)
    }
}

struct ListGenerator<T>: GeneratorType {
    typealias Element = T

    var list: List<T>

    mutating func next() -> Element? {
        switch list {
        case .Nil:
            return .None
        case .Cons(let v):
            self.list = v.tail
            return v.head
        }
    }
}

これで、mapやreduceが使えるようになります。ただし、mapで返されるものは配列になってしまいますので、必要ならListでラップする必要があります。

let mapped = List(a.map { $0 * 3 })
// => 3:15:12:6:[]

let len = list.reduce(0) { (a, e) in
    return a + 1
}
// => 4

おわりに

再帰enumの個人的な問題点は、いろいろな型を混在させられる点です。

let mix: List = [9, "doo", 11.5]

逆にこれを利用できれば、いろいろおもしろいことができるかもしれませんね。

関連リンク

• Recursive Enumerations