Swift - 再帰的enumの書き方

  • 35
    Like
  • 2
    Comment
More than 1 year has passed since last update.

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

Swiftで気になった所

代数的データ構造を彷彿とさせる魔改造を施されたenumですが、再帰的データ構造が出来そうで出来ないのでガッカリ感が有ります。

enum List { // (!) Recursive value type 'List' is not allowed
    case Car(AnyObject)
    case Cdr(List?)
}

正座して実装される日を待ちます。

なぜなら、それが出来るようにするということは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にポインターはありません1。どうしたらよいでしょうか?

参照型なのはClassだけ

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

"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
}

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

structenumは実体型

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

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におけるポインターのサイズと一致します2

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

マシン語が透けて見える

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

まとめ

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

Dan the Self-Referential Coder


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

  2. 64bit環境なら8、32bit環境なら4。