Swift - 再帰的enumの書き方 #Swift

その日は来ないと弾言しちゃいます。

[Swiftで気になった所]

代数的データ構造を彷彿とさせる魔改造を施されたenumですが、再帰的データ構造が出来そうで出来ないのでガッカリ感が有ります。
enum List { // (!) Recursive value type 'List' is not allowed
    case Car(AnyObject)
    case Cdr(List?)
}
正座して実装される日を待ちます。

[Swiftで気になった所]: http://qiita.com/ykst/items/3aba08ba1bf8955004d1

なぜなら、それが出来るようにするということはSwiftの型システムのありようを根本から崩壊させてしまうことになるからです。

結論を述べる前に、上記のコードをあえてCで書いたらどうなるのか見てみましょう。

typedef void *AnyObject;
typedef union List {
    AnyObject  car;
    union List cdr;
} List;

どこがおかしいかおわかりになるでしょうか?

そうです。union List cdrがおかしい。試しにコンパイルしてみると、clangではdefinition of 'union List' is not complete until the closing '}'というエラーが出ます。Listの中にListを入れることは、数学的にはできても物理学的にはできないのです。

なので、再帰的データ構造は、データそのものの代わりにデータへの参照を入れることで実現されています。マトリョーシカではなくロケット鉛筆なわけですね。

Cにおける参照とはポインターのことなので、上記コードは

typedef void *AnyObject;
typedef union List {
    AnyObject   car;
    union List *cdr;
} List;

として、*をcdrの前に加えるだけでいいわけです。

ところが、Swiftにポインターはありません[^0]。どうしたらよいでしょうか?

[^0]: Cのポインターの読み書きはできますが、あくまでもポインターではなくUnsafePointer<Type>などのStructとしてそれを実現しています。

参照型なのは`Class`だけ

[The Swift Programming Language]にはこう明記されています。

[The Swift Programming Language]: https://itun.es/jp/jEUH0.l

"Classes Are Reference Types”

そうです。Classを使えばいいのです。

import Foundation
class List {
    var car:AnyObject = NSNull()
    var cdr:List? = nil
}

これは問題なく動きます。

以下のようにすれば、さらによいでしょう。

class Atom<T> {
    var value:T
    init(_ value:T) {
        self.value = value
    }
}

enum Node<T> {
    case None
    case Data(Atom<T>)
    case Link(Pair<T>)
}

class Pair<T> {
    var car:Node<T> = .None
    var cdr:Node<T> = .None
}

enumとclassが相互参照することで、再帰的なenumが実現しました。

`struct`と`enum`は実体型

上記のコードは、こう書きたくなる誘惑に駆られます。

enum Node<T> {
    case None
    case Data(T)
    case Link(Pair<T>)
}

ところが、これは動きません。なぜかといえば、[The Swift Programming Language]にも"Structures and Enumerations Are Value Types"とあるように、enumは実体型だから。実体型ということは、実際に必要なメモリーの量を割り出して確保しなければならないということですが、上記のコードではTの大きさがわからないと必要なメモリーの量もわかりません。

そこでAtomというclassで包んでいる(wrap)わけです。classは参照型なので、sizeof(Atom<T>)は必ずCにおけるポインターのサイズと一致します[^1]。

実は、サイズが固定であれば包装はclassでなくても構いません。Atom<T>のかわりに[T]でも()->Tでも動きます。が、一番メモリーを食わないのはラッパークラスを使う方法。見た目もこれが一番すっきりしていると思います。

[^1]: 64bit環境なら8、32bit環境なら4。

マシン語が透けて見える

モダンな言語のほとんどは、ポインターを追放しています。その代償としてデータ構造の実装もまた隠蔽されているのですが、[@shi3zがポエムに歌ったように]、Swiftはポインターを追放したにも関わらずマシン語が透けて見える言語でもあります。型がstruct、enum、classと分かれているのは透明度が一番高い部分ではないでしょうか。

[@shi3zがポエムに歌ったように]: https://twitter.com/shi3z/status/473627881055485952

まとめ

再帰的データ構造を有限のメモリーで実現するには、参照が必要
Swiftにおける唯一の参照型はclass
classとenumを相互再帰することで、再帰的enumが実現できる。

Dan the Self-Referential Coder

Swift - 再帰的enumの書き方

参照型なのはClassだけ

structとenumは実体型

マシン語が透けて見える

まとめ

参照型なのは`Class`だけ

`struct`と`enum`は実体型