ymyzk’s blog

Swift でジェネレータを作ったり、遅延評価してみる

—

by

Yusuke Miyazaki
in

Swift 1.2 を使ってジェネレータを作成したり, ジェネレータを使って遅延評価をしてみます. 同様のことをこれまでいくつかの言語で行っていますが, それについては以下を参照してください.

これまでの流れ

ジェネレータの基本

Swift でのジェネレータは GeneratorType プロトコル (protocol) に適合している型として表されます. GeneratorType の定義は以下のようになります.

protocol GeneratorType {
    typealias Element
    mutating func next() -> Element?
}

0 から 3 までの自然数を返すジェネレータの例は以下のようになります.

struct MyGenerator: GeneratorType {
    typealias Element = Int
    var i = 0
    mutating func next() -> Element? {
        if i <= 3 {
            return i++
        } else {
            return nil
        }
    }
}

var g = MyGenerator()
g.next()  // 0
g.next()  // 1
g.next()  // 2
g.next()  // 3
g.next()  // nil

Swift の for-in 文は SequenceType プロトコル (protocol) に適合している型のそれぞれの要素について処理を行うことが出来ます.

protocol _SequenceType {
}

protocol _Sequence_Type : _SequenceType {
    typealias Generator : GeneratorType
    func generate() -> Generator
}

protocol SequenceType : _Sequence_Type {
    typealias Generator : GeneratorType
    func generate() -> Generator
}

先ほどの MyGenerator を使って以下のようなシーケンスを定義して, for-in 文で利用することが出来ます.

struct MySequence: SequenceType {
    typealias Generator = MyGenerator
    func generate() -> Generator {
        return Generator()
    }
}

for i in MySequence() {
    println(i)  // 0, 1, 2, 3 が順に表示されます
}

Swift では SequenceType に適合したオブジェクトに対して, map や filter といった関数を適用することが出来ます.

println(map(MySequence(), { $0 * 2 }))
// [0, 2, 4, 6] が表示されます

println(filter(MySequence(), { $0 % 2 == 0 }))
// [0, 2] が表示されます

フィボナッチ数列のジェネレータ

例としてフィボナッチ数列を返すジェネレータを作成します. このジェネレータはフィボナッチ数を 0 から順に無限に返します.

struct FibonacciGenerator: GeneratorType {
    typealias Element = Int
    var (a, b) = (0, 1)
    mutating func next() -> Element? {
        let n = a
        (a, b) = (b, a + b)
        return n
    }
}

var fib = FibonacciGenerator()
fib.next()  // 0
fib.next()  // 1
fib.next()  // 1
fib.next()  // 2
fib.next()  // 3

struct FibonacciSequence: SequenceType {
    typealias Generator = FibonacciGenerator
    func generate() -> Generator {
        return Generator()
    }
}

// オーバーフローするまで停止しない
//for i in FibonacciSequence() {
//    println(i)
//}

for (i, n) in zip(0..<10, FibonacciSequence()) {
    println("F_\(i) = \(n)")  // F_0 = 0 から F_9 = 34 まで順に表示されます.
}

遅延評価

Swift では SequenceType に適合したオブジェクトから, LazySequence オブジェクトを返す lazy 関数が定義されています.

LazySequence オブジェクトには LazySequence オブジェクトを返す, map と filter メソッドが実装されています. これを用いて演算を遅延させることができます.

以下は, フィボナッチ数列の各要素を二乗して, 奇数だけの数列を作り, 先頭から10要素を順に表示する例です.

let fib2 = lazy(FibonacciSequence()).map({ $0 * $0 }).filter({ $0 % 2 == 1 })
for (i, n) in zip(0..<10, fib2) {
    println(n)  // 順に 1, 1, 9, 25, ..., 142129 が表示されます
}

参考

Swift のジェネレータ等については公式のドキュメントにもあまり情報が掲載されていません. それぞれの型や関数の定義にコメントで説明が記述されているため, それも合わせて確認することをおすすめします.

関連