次回へ LINQ 記事一覧へ

Swift による LINQ to Objects の試作

2014-11-28 (鈴)

1. はじめに

OS X 10.9, 10.10 上の Swift 1.1 で C# の LINQ to Objects メソッド [microsoft.com] のいくつかを実験的に実装した。

Swift の配列型や範囲型には LINQ to Objects の Select メソッドに似た map メソッドがある。 配列型にはさらに Where メソッドに似た filter メソッドもある。 しかし,これらは遅延実行をせず,結果としてただちに配列を返す。

(1...10).map{$0 * 2} // => [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
[1, 2, 3, 4, 5, 6].filter{$0 % 2 == 0} // => [2, 4, 6]

Ruby の Enumerator::Lazy についての議論で示したように LINQ to Objects のメソッドには,こうしたメソッドにない利点がある。

Apple 社による仕様記述には Swift で LINQ to Objects を実現するために必要な情報が断片的に書かれている。 有志による記事から不明点を補った。

Swift Programming Language - Language Reference - Statements [apple.com] の "For-In Statement" のエントリによれば, For-In 文は SequenceType プロトコルに適合する任意の値に対し generate メソッドを呼び出して GeneratorType プロトコルに適合するジェネレータを得る。 このジェネレータの next メソッドが None (nil の誤記か) を返すまでループを繰り返す。 各ループでは For-In 文の制御変数に next メソッドの戻り値がセットされる。

[Swift]自作クラスでfor...in [qiita.com] ではこの SequenceType と GeneratorType (記事が書かれた当時はそれぞれ Sequence と Generator) の具体的な使用例を分かりやすく与えている。 本稿の内容は先週この記事に触発されて生まれた。

Swift Sequences and Lazy Evaluation [scottlogic.com] もまた当時の Sequence と Generator の具体的な使用例を与えている。 この記事は関数引数によって具体的な列やジェネレータとなる構造体 SequenceOf, Zip2, GeneratorOf も紹介している。

Swifter [natecook.com] はこれら二つの記事の内容を理解するために有用である。

Swift Standard Library Reference - Types - Array [apple.com] の "+=" 演算子のエントリではその宣言として説明なしに下記を挙げている。

1  func +=<T, S: SequenceType where S.Generator.Element == T>(inout lhs: [T], rhs: S)
2  func +=<T, C: CollectionType where C.Generator.Element == T>(inout lhs: [T], rhs: C)

ここで 1. について SequenceType や S.Generator.Element について説明はない。 しかし,これまでの情報と演算子の意味から逆算すれば SequenceType に適合する任意の型 S に対し, S.Generator とは GeneratorType に適合するそのジェネレータ型であり, S.Generator.Element とはジェネレータの next メソッドが返す値の型であること, そしてそれが T と同じであることから,結局,型変数 S が任意の型 T を要素型とする列型を表していることが分かる。 もし仮引数の rhs: S を C# で表現したならば IEnumerable<T> rhs となるだろう。 同様に S.Generator は C# の IEnumerator<T> に相当する。

以下,この対応関係を基礎として Swift による LINQ to Objects の実装について説明する。

2. ToArray メソッド

まず ToArray メソッドについて考えよう。 任意の型 T を要素型とする任意の列型 Ts に対し,列の各要素からなる配列を新しく作って返す ToArray_func は次のように定義できる。

// 列の各要素からなる配列を新しく作って返す。
func ToArray_func<Ts:SequenceType, T where T == Ts.Generator.Element>
    (sequence: Ts) -> Array<T> {
    var result = [T]()
    for e in sequence {
        result.append(e)
    }
    return result
}

この関数を下記のように範囲型のメソッドにすれば

extension Range {
    func ToArray() -> Array<T> {
        return ToArray_func(self)
    }
}

次のように範囲型の値に対して ToArray を使うことができる。

(1...10).ToArray() // => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

他の列型についても同様にメソッドにすることができる。

本来ならば,こうしたメソッドは C# の IEnumerable<T> に対する拡張メソッドのように Swift の SequenceType プロトコルに対する拡張メソッドとして定義したいところでした。 そうできれば配列であれ範囲であれすべての列に対して ToArray が使えるようになります。 残念ながら今の Swift ではプロトコルに extension は使えませんから,Range など個別の型についていちいち全く同じ extension を繰り返さなくてはいけません。:-(

3. 構造体 SequenceOf と GeneratorOf

過去作成した Ruby による実装, Go による実装 にみるように LINQ to Objects の実装とは高階関数の実装である。 ここで Swift では列の generate メソッドで得られたジェネレータの next メソッドを使うという枠組みが言語で与えられているから,関数引数とメソッドの橋渡しとなるクラスまたは構造体を使うことが妥当である。 Swift はそのような構造体 SequenceOf と GeneratorOf を標準で用意している。

SequenceOf は init 引数としてジェネレータを返すような無引数関数をとる。 SequenceOf の generate メソッドは,この無引数関数を呼び出してその戻り値を結果とする。

GeneratorOf は init 引数として nil または値を返すような無引数関数をとる。 GeneratorOf の next メソッドは,この無引数関数を呼び出してその戻り値を結果とする。

これらの使用例を示す。

// フィボナッチ数列
let fib = SequenceOf {
    () -> GeneratorOf<Int> in
    var a = 0, b = 1
    return GeneratorOf {
        () -> Int? in
        let c = a + b
        a = b
        b = c
        return a
    }
}

// 1000 以下の数を印字する
for e in fib {
    if e > 1000 {
        break
    }
    print(" \(e)")
}
println()
01:~/tmp$ xcrun swift fib_test.swift 
 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
01:~/tmp$  
実装の初期段階では SequenceOf と GeneratorOf が標準で用意されていることに気づかず,似た型を独自に定義していました。 今それを清書すると次のようなものになります。init で受け取った関数引数をそれぞれのメソッドでそのまま呼び出しているだけです。
// 関数引数をそのまま next メソッドとするジェネレータ
struct GeneratorOf<T>: GeneratorType {
    private let nextFunction: ()->T?

    init(nextFunction: ()->T?) {
        self.nextFunction = nextFunction
    }

    func next() -> T? {
        return nextFunction()
    }
}

// 関数引数をそのまま generate メソッドとする列
struct SequenceOf<T>: SequenceType {
    private let generateFunction: () -> GeneratorOf<T>

    init(generateFunction: () -> GeneratorOf<T>) {
        self.generateFunction = generateFunction
    }

    func generate() -> GeneratorOf<T> {
        return generateFunction()
    }
}
ちなみに標準で用意されている GeneratorOf はこの定義と異なり,SequenceType にも適合し,自ら列としても振る舞います。 その generate メソッドは単に自分自身を返すだけであり,1回どおり要素を取得できる使い捨て,ないし揮発性の列になります。 次々と発生するイベントを待ち受け,その都度その値を next メソッドで返すような「列」を作るのにちょうど良いでしょう。 Reactive Programming の基礎として有用です。
上記の定義をそのように変えるには GeneratorOf<T> の頭書きに SequenceType を追加し,self を返すだけの generate() を定義します。

4. transform 関数と Select メソッド

典型的な LINQ to Objects メソッドは,元になる列のジェネレータから新しい関数を作り,それをジェネレータとするような列を構築する関数として表現できる。 したがって元になる列 (Ts 型) のジェネレータ (Ts.Generator 型) から新しい関数 (任意の U 型に対して ()->U? 型) を作る変換関数 (Ts.Generator -> ()->U? 型) を引数にとるような高階関数をひとつ定義すれば,各メソッドをそうした高階関数の呼び出しとして与えることができる。

そのような高階関数 transform を前節で説明した SequenceOf と GeneratorOf を使って次のように定義する。

// 元になる列 source のジェネレータを transformer で変換した列を返す。
func transform<Ts:SequenceType, U>
    (source: Ts, transformer: Ts.Generator -> ()->U?) -> SequenceOf<U> {
    let g = {
        () -> GeneratorOf<U> in
        let generator = source.generate()
        let next = transformer(generator)
        return GeneratorOf(next)
    }
    return SequenceOf(g)
}

このとき列 (Ts 型) の各要素 (T 型) に関数 (T->U 型) を適用する Select_func 関数は次のように定義できる。 これが transform に与える変換関数は,ジェネレータ g に対して g.next() を呼び出し,その結果が nil でなければ関数適用を行い,その戻り値 (U 型) を返すような関数を生成する。

// source の各要素に selector を適用した結果からなる列を返す。
func Select_func<Ts:SequenceType, T, U where T == Ts.Generator.Element>
    (source: Ts, selector: T->U) -> SequenceOf<U> {
    return transform(source) {
        (var g: Ts.Generator) -> ()->U? in {
            ()->U? in
            if let e = g.next() {
                return selector(e)
            } else {
                return nil
            }
        }
    }
}

SequenceType はプロトコルであり,じかにメソッドを拡張することはできない。 SequenceType に適合する各列型で次のように拡張メソッドを定義する。

extension SequenceOf {
    func Select<U>(selector: T->U) -> SequenceOf<U> {
        return Select_func(self, selector)
    }
}
extension GeneratorOf {
    func Select<U>(selector: T->U) -> SequenceOf<U> {
        return Select_func(self, selector)
    }
}
extension Array {
    func Select<U>(selector: T->U) -> SequenceOf<U> {
        return Select_func(self, selector)
    }
}
extension Range {
    func Select<U>(selector: T->U) -> SequenceOf<U> {
        return Select_func(self, selector)
    }
}
extension Repeat {
    func Select<U>(selector: T->U) -> SequenceOf<U> {
        return Select_func(self, selector)
    }
}

これ以降もコードの掲載は省くが,同様にそれぞれの関数に対して拡張メソッドを定義する。

このメソッド拡張では各型の元の定義がどれもたまたま T を要素型の型変数としていることに依存しています……といいますか依存せざるを得ません。:-(

範囲型に対する使用例を示す。

01:~/tmp$ cat select_test.swift 
for x in (1...10).Select({$0 * 2}) {
    print(" \(x)")
}
println()
01:~/tmp$ cat linq.swift select_test.swift | xcrun swift -
 2 4 6 8 10 12 14 16 18 20
01:~/tmp$  

5. Where メソッド

列 (Ts 型) の各要素 (T 型) に述語関数 (T->Bool 型) を適用し,結果が真となった要素だけ残す Where_func 関数は次のように定義できる。 この変換関数ではジェネレータ g に対して, true か nil が得られるまで g.next() を何度でも (for ;; による無限ループで) 呼び出して述語関数を適用する関数を生成する。

// source の各要素のうち predicate を真にするものからなる列を返す。
func Where_func<Ts:SequenceType, T where T == Ts.Generator.Element>
    (source: Ts, predicate: T->Bool) -> SequenceOf<T> {
    return transform(source) {
        (var g: Ts.Generator) -> ()->T? in {
            ()->T? in
            for ;; {
                if let e = g.next() {
                    if predicate(e) {
                        return e
                    }
                } else {
                    return nil
                }
            }
        }
    }
}

範囲型に対する使用例を示す。

01:~/tmp$ cat where_test.swift 
for x in (1...10).Where({$0 % 2 == 0}) {
    print(" \(x)")
}
println()
01:~/tmp$ cat linq.swift where_test.swift | xcrun swift -
 2 4 6 8 10
01:~/tmp$  

6. Take メソッド

列 (Ts 型) の要素 (T 型) を最初の count 個だけ取り出す Take_func 関数は次のように定義できる。 この変換関数では与えられたジェネレータ g に対して内部カウンタ i を 0 にセットし, 呼び出されるごとに g.next() の値を返すとともに i を 1 だけ増やすような関数を生成する。

// source の最初の count 個の要素からなる列を返す。
func Take_func<Ts:SequenceType, T where T == Ts.Generator.Element>
    (source: Ts, count: Int) -> SequenceOf<T> {
    return transform(source) {
        (var g: Ts.Generator) -> ()->T? in
        var i = 0
        return {
            ()->T? in
            if i < count {
                if let e = g.next() {
                    i++
                    return e
                }
            }
            return nil
        }
    }
}

フィボナッチ数列の最初の 10 項を得る例を示す。

01:~/tmp$ cat take_test.swift 
let fib = SequenceOf {
    () -> GeneratorOf<Int> in
    var a = 0, b = 1
    return GeneratorOf {
        () -> Int? in
        let c = a + b
        a = b
        b = c
        return a
    }
}

for e in fib.Take(10) {
    print(" \(e)")
}
println()
01:~/tmp$ cat linq.swift take_test.swift | xcrun swift -
 1 1 2 3 5 8 13 21 34 55
01:~/tmp$  

7. SelectMany メソッド

列 (Ts 型) の要素 (T 型) に,列 (Us 型) を結果とする関数 (T->Us) を適用し,得られた各列 (Us 型) の要素 (U 型) を順につないだ列を返す SelectMany_func 関数は次のように定義できる。 この変換関数が生み出すジェネレータの動作は次のようなものである。 Us 型の列のジェネレータ ug が ug.next() で返した値 u を結果として返す。 もし ug.next() で nil が返されたならば,元の列 (Ts 型) のジェネレータ tg から tg.next() で次の T 型の値 t1 を得る。 t1 に関数引数 selector を適用して Us 型の列を得る。ただちにその列のジェネレータを generate メソッドで取得し,新しい ug として再試行する。 もし tg が尽きて tg.next() で nil が返されたならば,nil を結果として返して列を終結させる。

// source の各要素に selector を適用して得られた列を順につないだ列を返す。
func SelectMany_func<Ts:SequenceType, T, Us:SequenceType, U
where T == Ts.Generator.Element, U == Us.Generator.Element>
    (source: Ts, selector: T->Us) -> SequenceOf<U> {
    return transform(source) {
        (var tg: Ts.Generator) -> ()->U? in
        if let t = tg.next() {
            var ug = selector(t).generate()
            return {
                ()->U? in
                for ;; {
                    if let u = ug.next() {
                        return u
                    } else {
                        if let t1 = tg.next() {
                            ug = selector(t1).generate()
                        } else {
                            return nil
                        }
                    }
                }
            }
        } else {
            return { nil }
        }
    }
}

タプルの配列に対する使用例を示す。 それぞれのタプルから文字列配列の項を取り出して一つの列にする。

01:~/tmp$ cat selectMany_test.swift 
let owners = [
    ("Taro", ["Koro", "Pochi", "Tama"]),
    ("Jiro", ["Kuro", "Buchi", "Tora"])
]

let pets = owners.SelectMany{$0.1}
println(pets.ToArray())
01:~/tmp$ cat linq.swift selectMany_test.swift | xcrun swift -
[Koro, Pochi, Tama, Kuro, Buchi, Tora]
01:~/tmp$  
これを Go 言語の対応するや C# の類似する [microsoft.com] と比べてください。 同等以上に厳密な静的型検査のもとにありながら Swift の簡潔な表現はまるでいわゆるスクリプト言語のようです。:-)

8. Zip メソッド

T を要素型とする列 first (Ts 型) と,U を要素型とする列 second (Us 型) と,T 型と U 型から R 型の結果を返す関数引数 selector ((T, U)->R 型) から R 型の列を返す Zip_func 関数は次のように定義できる。 ここで Zip2 は,二つの列に対する SequenceOf 型に相当する型であり,SequenceOf と同じく標準で用意されている。 let source = Zip2(first, second) として二つの列の各要素をペアにした列 (source) を得た後の処理は,source のジェネレータ g が要素値のペア (e1, e2) を与えること以外は Select_func と同じである。

// first と second の要素を順に対にし selector に適用した結果からなる列を返す。
func Zip_func<Ts:SequenceType, T, Us:SequenceType, U, R
where T == Ts.Generator.Element, U == Us.Generator.Element>
    (first: Ts, second: Us, selector: (T, U)->R) -> SequenceOf<R> {
    let source = Zip2(first, second)
    return transform(source) {
        (var g: Zip2<Ts, Us>.Generator) -> ()->R? in {
            ()->R? in
            if let (e1, e2) = g.next() {
                return selector(e1, e2)
            } else {
                return nil
            }
        }
    }
}

範囲型に対する使用例を示す。

01:~/tmp$ cat zip_test.swift 
let ss = (1...5).Zip(101...200) { "\($0)-\($1)" }
for s in ss {
    print(" " + s)
}
println()
01:~/tmp$ cat linq.swift zip_test.swift | xcrun swift -
 1-101 2-102 3-103 4-104 5-105
01:~/tmp$  

9. おわりに

Swift による LINQ 実装の先行事例として 101 LINQ Samples in Swift [github.com] がある。 これは Swift が標準で備えている配列型の map 等のメソッドに加えて,いくつかのメソッドを swift-linq-examples/src/LinqExamples/extensions.swift [github.com] のように追加したものである。 しかし,残念ながら列を返すようなメソッドはそれぞれ map メソッドと同じく配列をただちに構築して結果としている。 つまり,遅延実行によりパイプライン的に動作する C# の LINQ to Objects の Select 等のメソッドと異なり,長さ n の入力に対する空間計算量が O(1) ではなく O(n) であり,計算を Take(1) などで打ち切ったときの時間計算量も O(1) ではなく O(n) である。

これに対し本稿で示した実装はおそらく世界で初めて Swift で C# の LINQ to Objects と同じ動作,同じ計算量を実現したものである。 C# の LINQ to Objects と同じようにパイプライン的に動作し,同じように小さな計算量におさめていることは実用上重要である。

その一方,この実装の過程で,プロトコルを直接ジェネリック化できないことによる <Ts:SequenceType, T where T == Ts.Generator.Element> のような回りくどい表現,プロトコルに直接 extension でメソッドを拡張できないことによる冗漫な定義の繰り返しをみて来た。 もしかしたら将来の Swift ではプロトコルをファーストクラスの型とすることで,これらの問題を解決するのかもしれない。 現在の Swift の公式仕様が奇妙にも SequenceType や GeneratorType の記述を避けているのは,それに伴う変更に備えているかのように見える。 Swift をより優れた言語とするため,また移行に伴う混乱を避けるため,そうした改訂が早期に行われることを期待したい。

仮にそうした言語改訂が行われたならば,ここで示した実装にも修正が必要になるだろう。 しかし,今回 SequenceOf, GeneratorOf, Zip2 など実装に必要な材料がすでにあらかたそろっていたことに注目したい。 今回の実装でしたことはほとんど最後の仕上げにすぎない。 あるいは LINQ to Objects に相当する機能が Swift に標準で用意されることを予想してよいのかもしれない。 C# で実現されず静的型検査の弱点となっていた nil (null) の静的な検査を組み込んだ新しい世代の言語である Swift の発展に期待したい。

2014-12-15 追記

言及すべき重要な先行事例が二つありました。 どちらも一般の「列」に対する関数としては LINQ to Objects のメソッドを定義していない点が残念ですが,同じように遅延実行を実現しています。 本稿で示した実装による下記の式をそれぞれのライブラリで書いた例を示しながら簡単に紹介します。

(1...5).Select({$0 * $0}).ToArray()  // => [1, 4, 9, 16, 25]

rrridges/swift-linq [github.com] は SequenceOf<T> の拡張メソッドとして,いくつかの LINQ メソッドを定義しています。 一般の列は SequenceOf のコンストラクタ引数として与えます。

SequenceOf(1...5).Select({$0 * $0}).ToArray()  // => [1, 4, 9, 16, 25]

SINQ - Swift Integrated Query [github.com] は SequenceType に適合する SinqSequence<T> クラスを定義し,多くの種類の LINQ メソッドを Swift の慣習的な命名則に従って与えています。 一般の列をじかに SinqSequence のコンストラクタ引数として与えることもできますが,見映えを良くするために from 関数を用意しています。 今ただちに LINQ to Objects を Swift で実用的に使いたいならば,この SINQ ライブラリこそが最良の選択かもしれません。

from(1...5).select({$0 * $0}).toArray()  // => [1, 4, 9, 16, 25]

なお,本稿では LINQ to Objects の動作を形容するために「遅延実行」(deferred execution) の語を使いました。 これを関数型言語 Miranda [miranda.org.uk], Haskell [haskell.org] の評価メカニズムや Scheme の delay/force にみられるような伝統的な意味での「遅延評価」(lazy evaluation) と区別して使っています。 日本語ではどちらも「遅延」で紛らわしいのですが,遅延実行は引数を必要になったとき何度でもその都度評価する (Algol 60 の) call by name に相当し,(伝統的な意味での) 遅延評価は引数を初めて必要になったとき一度だけ評価する call by need に相当します。 「フィボナッチ数の計算 2: Don't say "They are lazy"」 で議論したように遅延実行はしばしば lazy とは言えない振舞を示しますが,副作用のある操作と組み合わせたとき使いやすいとも言えます。


Copyright (c) 2014 OKI Software Co., Ltd.