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定義されている．

stdlib/public/core/Sequence.swift

public protocol IteratorProtocol {
    associatedtype Element

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

associated typeとしてElementという型をひとつ持つprotocolで，イテレータが次にyieldする値をElement?型^*2で返すnext()メソッドを持っている．また，next()メソッドにはmutatingキーワードが付いているので，この際にデータ型の内部状態として持つ値は破壊的に変更してもよい^*3．

試しに，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に適合していることを宣言すればよい．これは以下のような宣言で実現されている^*4．

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

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

自然数の列は無限に長い^*5ので，for-inループでイテレーションを行うと停止せず，困ってしまう．そこで，与えられた自然数nについて，0からnまでの有限列を返す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ループで使用できていることがわかる．

遅延評価#

Sequenceはlazyという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 }
}

これはSelfをgeneric parameterとして持っているLazySequenceを返す．これがSequenceの遅延版であり，mapやfilterなどのメソッドが遅延評価されるように実装されている．これを用いて，いつも通りではあるが，フィボナッチ数列のそれぞれの要素を自乗し，奇数のもののみ抜き出したのち，先頭から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）を施したもので，残念なことにこれがないと型推論がおかしくなって死ぬ．というのも，コンパイルには成功するが，メソッド呼び出しが何故か正格な方に解決されてしまい，大きな数を扱おうとしてillegal hardware instructionで死ぬ．なんとも情けない話である．

参考資料#

脚注#

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

*2: 返すことができる値がない場合にはnilを返す

*3: かつてはassociated type declarationのためにtypealiasキーワードが用いられていたが，Swift 2.2からはassociatedtypeキーワードに変更されている．

*4: https://github.com/apple/swift/blob/5256d774eaf774ec1e3c566aa8047764a1124837/stdlib/public/core/Sequence.swift#L625-L633

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

これまでの流れ#

IteratorProtocol#

Sequence#

遅延評価#

参考資料#

脚注#

`IteratorProtocol`#

`Sequence`#