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

Swift でのジェネレータの取扱いや遅延評価については,ymyzk 先生の Swift でジェネレータを作ったり、遅延評価してみる において解説されているが,2015年5月の記事であり,Swift のバージョンも1.2だった頃の記事なので,改めて書くことにした.

2017年7月16日現在,Xcode 9.0 beta 上では Swift 4.0 がサポートされているが,手元の環境は Xcode 8.3.3 であるため,Swift 3.1 をベースに解説する.Apple の先走りで,ドキュメントのリンク先が一部 Swift 4 に関するものになっている部分があるが,本記事の理解にあたって本質的な違いはないはずである.

これまでの流れ

IteratorProtocol

IteratorProtocol は,

A type that supplies the values of a sequence one at a time.

と説明されるプロトコルで,かつては GeneratorType と呼ばれていたものである.stdlib/public/core/Sequence.swift で以下のように*1定義されている.

public protocol IteratorProtocol {
    associatedtype Element

    public mutating func next() -> Self.Element?
}

associated type として Element という型をひとつ持つ protocol で,イテレータが次に yield する値を Element? 型で返す next() メソッドを持っている(返すことができる値がない場合には nil を返す).また,next() メソッドには mutating キーワードが付いているので,この際にデータ型の内部状態として持つ値は破壊的に変更してもよい.(かつては associated type declaration のためにtypealias キーワードが用いられていたが,Swift 2.2 からは associatedtype キーワードに変更されている.)

試しに,next() を呼び出す度,自然数を順に返す Nat を定義してみよう.

struct Nat: IteratorProtocol {
    var n = 0

    mutating func next() -> Int? {
        defer { n += 1 }

        return n
    }
}

var nat = Nat()

print(nat.next()) // Optional(0)
print(nat.next()) // Optional(1)
print(nat.next()) // Optional(2)
print(nat.next()) // Optional(3)
print(nat.next()) // Optional(4)

ここで defer statement というものが登場しているが,これは,defer が宣言されたスコープを抜ける際に,与えられた code block を実行してくれるものである.言語機構として yield を持つ言語ならば,yield した後に値をインクリメントするといった処理が行えるが,構造体とメソッドしか持たない場合はそうもいかない.そこで,このような解決策を取っている.余談ではあるが,Swift 3 からは昔ながらのC言語スタイルの ++ (および --)演算子が削除された

Sequence

Sequence は,かつては SequenceType と呼ばれていたもので,

A type that provides sequential, iterated access to its elements.

と紹介されており,データ型をこのプロトコルに適合させると,for-in によるループ操作ができるようになる.データ型を Sequence プロトコルに適合させるためには, イテレータを返す makeIterator() メソッドを実装すればよいが,既に ProtocolIterator に適合している場合はもっと簡単で,単に Sequence に適合していることを宣言すればよい.これは以下のような宣言で実現されている.(GitHub より引用)

/// A default makeIterator() function for `IteratorProtocol` instances that
/// are declared to conform to `Sequence`
extension Sequence where Self.Iterator == Self {
  /// Returns an iterator over the elements of this sequence.
  @_inlineable
  public func makeIterator() -> Self {
    return self
  }
}

Sequenceassociated type として,IteratorProtocol に適合するような Iterator を持っているのだが,この Iterator が自分自身のときには, makeIterator()self を返すようなデフォルト実装が与えられている.

自然数の列は無限に長い*2ので,for-in ループでイテレーションを行うと停止せず,困ってしまうので,0 から与えられた自然数までの(有限)列を返す Upto イテレータを定義した上で,for-in の挙動を確かめてみよう.

struct Upto: IteratorProtocol, Sequence {
    let n: Int
    var curr = 0

    init(_ n: Int) {
        self.n = n
    }

    mutating func next() -> Int? {
        defer { curr += 1 }

        return curr <= n ? curr : nil
    }
}

for k in Upto(4) {
    print(k) // 0, 1, 2, 3, 4 が順に表示される
}

あまりにも馴染みがある記法なので,目新しさはないが,自分で定義したデータ型が for-in ループで使用できていることがわかる.

遅延評価

Sequencelazy という instance property を持っているが,これは以下のようなシグネチャで表現されている.

extension Sequence {

    /// A sequence containing the same elements as this sequence,
    /// but on which some operations, such as `map` and `filter`, are
    /// implemented lazily.
    ///
    /// - SeeAlso: `LazySequenceProtocol`, `LazySequence`
    public var lazy: LazySequence<Self> { get }
}

これは Selfgeneric parameter として持っている LazySequence を返す.これが Sequence の遅延版であり,mapfilter などのメソッドが遅延評価されるように実装されている.これを用いて,いつも通りではあるが,フィボナッチ数列のそれぞれの要素を自乗し,奇数のもののみ抜き出したのち,先頭から10個の要素を取り出してみよう.

struct Fib: IteratorProtocol, Sequence {
    var (a, b) = (0, 1)

    mutating func next() -> Int? {
        defer { (a, b) = (b, a + b) }

        return a
    }
}

let xs: AnySequence<Int> = Fib().lazy
    .map({ $0 * $0 })
    .filter({ $0 % 2 != 0 })
    .prefix(10)

print(Array(xs)) // [1, 1, 9, 25, 169, 441, 3025, 7921, 54289, 142129]

ここで AnySequence という型が登場しているが,これは Sequence に 型消去 (type erasure) *3を施したもので,残念なことにこれがないと型推論がおかしくなって死ぬ.死ぬというのも,コンパイルには成功するが,メソッド呼び出しが何故か正格な方に解決されてしまい,大きな数を扱おうとして illegal hardware instruction で死ぬ.なんとも情けない話である.

参考

*1:ただしコメント部は除く.

*2:もちろんメモリを考慮すればこの限りではない.

*3:Swift で型消去と言えば,一時期 AnyPokemon が流行ったのを思い出す.