Swift 2.1 の SequenceType への LINQ ライクな拡張
2015-12-17 (鈴)- linq.swift: Linq モジュール・ソース
- swift-linq-27-12-16.tar.bz2: linq.swift と fib_test.swift (§4) の詰め合わせ: 2281 バイト, md5: 93a68bbe7b7e1fe4349504a7d6eefb67
1. はじめに
前回「Swift 2.0 による LINQ to Objects の試作」で与えた Swift に対する LINQ to Object (以下，単に LINQ) の実装は，その第４節で簡単に議論したように標準ライブラリに含まれる構造体 LazySequence (より正確にはそのプロトコル LazySequenceType) と Select, Where メソッドの機能が重複していた。
そこで，今回は LazySequenceType の存在を前提として Swift 2.1 の SequenceType の自然な拡張となるように小改訂した LINQ 実装を与える。 Swift 処理系として OS X 10.10.5 上の Xcode 7.2 に付属する Swift 2.1.1 を使う。
以下，前回の記述順序に準じて今回の実装を説明する。
2. Linq モジュールの構成
Linq モジュールを linq.swift ファイルで構成する。 linq.swift ファイルは抽象的な列を表す標準プロトコル SequenceType を下記のように拡張する。
public extension SequenceType { private typealias E = Generator.Element .... }
SequenceType に随伴する Generator 型の要素型 Generator.Element が列の要素型となる。 簡単のため typealias を使って E の１語で要素型を参照できるようにする。
ターミナル上で Linq モジュールを作成するときは swiftc コマンドに下記のように -emit-library と -emit-module オプションを与えてモジュール・ファイルと共有ライブラリを作らせればよい。 -O オプションは C コンパイラと同じく最適化を指示する。 -module-name オプションで構築するモジュールの名前 (ここでは Linq) を指定する。 -sdk オプションでコンパイル対象の SDK のパスを与える。
01:~/tmp$ swiftc linq.swift -O -module-name Linq -sdk `xcrun --show-sdk-path` \ > -emit-library -emit-module 01:~/tmp$ ls -l *Linq* -rw-r--r-- 1 suzuki staff 2292 Dec 16 12:36 Linq.swiftdoc -rw-r--r-- 1 suzuki staff 11772 Dec 16 12:36 Linq.swiftmodule -rwxr-xr-x 1 suzuki staff 28760 Dec 16 12:36 libLinq.dylib* 01:~/tmp$
swift に対し -I オプションでモジュール・ファイルに，-L オプションで共有ライブラリにそれぞれパスを通し，-lLinq で libLinq ライブラリをリンクして起動する。
01:~/tmp$ swift -I. -L. -lLinq Welcome to Apple Swift version 2.1.1 (swiftlang-700.1.101.15 clang-700.1.81). Ty pe :help for assistance. 1>
このとき swift から Linq モジュールを import して LINQ メソッドを実行できる。
1> import Linq 2>
以下，linq.swift の各 LINQ メソッドの実装を説明する。
3. LINQ メソッドの実装
3.1 toArray メソッド
Array 型は init 引数として SequenceType を取ることができる。 これを使えば LINQ の ToArray メソッドはごく簡単に実装できる。 次のように SequenceType を拡張すればよい。
/// 列の各要素からなる配列を新しく作って返す。
func toArray() -> Array<E> {
return Array(self)
}
Swift の命名法にしたがってメソッド名を大文字ではなく小文字で始める。 以下，3.2 節以降のメソッドも同様である。
SequenceType に適合する任意の型で toArray() を使うことができる。
2> (1...10).toArray() $R0: [Int] = 10 values { [0] = 1 [1] = 2 [2] = 3 [3] = 4 [4] = 5 [5] = 6 [6] = 7 [7] = 8 [8] = 9 [9] = 10 } 3>
3> for i in [7, 8, 9, 2].lazy.map({$0 * 100}) { print(i) } 700 800 900 200 4>どこがどう遅延しているのかよく分かりませんから print をさしはさんでみます。
4> for i in [7, 8, 9, 2].lazy.map({x->Int in print(x); return x * 100}) { 5. print(i) } 7 700 8 800 9 900 2 200 6>これを lazy 無しの場合と比べてください。
6> for i in [7, 8, 9, 2].map({x->Int in print(x); return x * 100}) { 7. print(i) } 7 8 9 2 700 800 900 200 8>こちらはループ本体に入る前に map メソッドが関数引数をすっかり呼び出し終わっています。
8> for i in [7, 8, 9, 2].lazy.filter({$0 % 2 == 0}) { print(i) } 8 2 9>これもどこがどう遅延しているのかよく分かりませんから print をさしはさんで lazy 有りと無しで比べてみます。
9> for i in [7, 8, 9, 2].lazy.filter({x->Bool in print("- \(x)"); 10. return x % 2 == 0}) { print(i) } - 7 - 8 8 - 9 - 2 2 11> for i in [7, 8, 9, 2].filter({x->Bool in print("- \(x)"); 12. return x % 2 == 0}) { print(i) } - 7 - 8 - 9 - 2 8 2 13>
3.2 takeWhile メソッド
列の要素を述語関数に適用して false になったら打ち切る takeWhile メソッドは次のように定義できる。 打ち切りは，新しい列の next メソッドが nil を返すことで行う。
/// 先頭からの要素を predicate が真である限りの間だけ返す。
func takeWhile(predicate: E->Bool) -> AnySequence<E> {
return AnySequence { () -> AnyGenerator<E> in
var g = self.generate()
return anyGenerator { () -> E? in
if let e = g.next() {
if predicate(e) {
return e
} else {
return nil
}
} else {
return nil
}
}
}
}
関数引数 predicate の型が E throws -> Bool ではないことに注意されたい。 エラーを送出する関数を引数として与えることはできない。 これについては本稿の最後，4.1節で議論する。
takeWhile メソッドの使用例を示す。この例では 9 以上の要素が出現したらループを打ち切る。
13> for i in [7, 8, 9, 2].takeWhile({$0 < 9}) { print(i) } 7 8 14>
14> for i in [7, 8, 9, 2].takeWhile({x->Bool in print("- \(x)"); return x < 9} 15. ) { print(i) } - 7 7 - 8 8 - 9 16>このように毎回のループごとに１要素ずつ打ち切るかどうかを判定しています。
3.3 skipWhile メソッド
列の要素を述語関数に適用して false になったところから始める skipWhile メソッドは次のように定義できる。 いったん false になって先頭要素が得られたらもう述語関数は使われない。 この切り替えをフラグ変数 first を使って実現する。
/// 先頭からの要素を predicate が真である限りの間だけ除いて返す。
func skipWhile(predicate: E->Bool) -> AnySequence<E> {
return AnySequence { () -> AnyGenerator<E> in
var g = self.generate()
var first = true
return anyGenerator { () -> E? in
if first {
first = false
for ;; {
if let e = g.next() {
if !predicate(e) {
return e
}
} else {
return nil
}
}
}
if let e = g.next() {
return e
} else {
return nil
}
}
}
}
使用例を示す。この例では 9 以上の要素が出現したら列挙を開始する。
16> for i in [7, 8, 9, 2].skipWhile({$0 < 9}) { print(i) } 9 2 17>
17> for i in [7, 8, 9, 2].lazy.map({x->Int in print("- \(x)"); return x} 18. ).skipWhile({$0 < 9}) { print(i) } - 7 - 8 - 9 9 - 2 2 19>確かに毎回のループごとに列の要素を取得していることが分かります。 特に実行例は示しませんが，3.4 節以降のメソッドも同様にして動作を確かめられます。
3.4 take メソッド
列の要素を先頭から指定個数だけ採る take メソッドは次のように定義できる。 変数 i を使って指定個数までカウントする。
/// 列の最初の count 個の要素からなる列を返す。
func take(count: Int) -> AnySequence<E> {
return AnySequence { () -> AnyGenerator<E> in
var g = self.generate()
var i = 0
return anyGenerator { () -> E? in
if i < count {
if let e = g.next() {
i++
return e
}
}
return nil
}
}
}
使用例を示す。
19> for i in [7, 8, 9, 2].take(3) { print(i) } 7 8 9 20> for i in (1...10).take(3) { print(i) } 1 2 3 21>
3.5 skip メソッド
列の要素を先頭から指定個数だけ除く skip メソッドは次のように定義できる。 指定個数だけ除いた先頭要素を返すまでの処理と，それ以降の処理をフラグ変数 first で切り替える。
/// 列の最初の count 個の要素を除いた列を返す。
func skip(count: Int) -> AnySequence<E> {
return AnySequence { () -> AnyGenerator<E> in
var g = self.generate()
var first = true
return anyGenerator { () -> E? in
if first {
first = false
for var i = 0; i < count; i++ {
if g.next() == nil {
return nil
}
}
}
if let e = g.next() {
return e
} else {
return nil
}
}
}
}
使用例を示す。
21> for i in (1...10).skip(3) { print(i) } 4 5 6 7 8 9 10 22>
22> let owners = [("太郎", ["コロ", "ポチ"]), ("次郎", ["クロ", "ブチ"])] owners: [(String, [String])] = 2 values { [0] = { 0 = "太郎" 1 = 2 values { [0] = "コロ" [1] = "ポチ" } } [1] = { 0 = "次郎" 1 = 2 values { [0] = "クロ" [1] = "ブチ" } } } 23> for s in owners.lazy.flatMap({$0.1}) { print(s) } コロ ポチ クロ ブチ 24>
3.6 concat メソッド
二つの列を連接した新しい列を作る concat メソッドは次のように定義できる。 二つの列 self と other は，それぞれの要素の型 E と S.Generator.Element は等しいが，ジェネレータの型が等しいとは限らない。 型の整合性を満たすため，ここでは単純に二つのジェネレータ変数 g1 と g2 を設ける。
/// 列と列をつなげた列を返す。
func concat<S: SequenceType where S.Generator.Element == E>
(other: S) -> AnySequence<E> {
return AnySequence { () -> AnyGenerator<E> in
var g1 = self.generate()
var g2: S.Generator? = nil
return anyGenerator { () -> E? in
if g2 == nil {
if let e = g1.next() {
return e
} else {
g2 = other.generate()
}
}
if let e = g2!.next() {
return e
} else {
return nil
}
}
}
}
使用例を示す。
24> for i in (1...3).concat(101...103) { print(i) } 1 2 3 101 102 103 25>
25> for s in zip((1...5), ["a", "b", "c"]).lazy.map({"\($0)-\($1)"}) { 26. print(i) } 1-a 2-b 3-c 27>ちなみに LINQ の Aggregate メソッドは SequenceType の reduce メソッドで代用できます。 例を示します。
27> (1...10).reduce(0, combine: {$0 + $1}) $R0: Int = 55 28> (1...10).lazy.reduce(0, combine: {$0 + $1}) $R1: Int = 55 29>reduce メソッドは列の要素を次々と消費して結果を算出しますから，遅延的かどうかは reduce の動作には関係しないことに注意してください。
4. おわりに
前回，前々回の試みと同じく今回の LINQ 実装も C# のオリジナル版と同じ計算量を実現する。 例えば，下記のプログラムは途中で配列を作ることなくループ１回につき１要素だけ算出して遂行される。
import Linq // フィボナッチ数列 let fib = AnySequence { () -> AnyGenerator<Int> in var a = 0, b = 1 return anyGenerator { () -> Int? in (a, b) = (b, a + b) print("- \(a)") // 途中経過を - 付きで印字する。 return a } } // 500 未満を印字する。 for e in fib.takeWhile({$0 < 500}) { print(e) }
実行例を示す。
01:~/tmp$ swift -I. -L. -lLinq fib_test.swift - 1 1 - 1 1 - 2 2 - 3 3 - 5 5 - 8 8 - 13 13 - 21 21 - 34 34 - 55 55 - 89 89 - 144 144 - 233 233 - 377 377 - 610 01:~/tmp$
4.1 未解決の課題
未解決の課題はエラーを引き起こし得る関数引数の扱いである。
現行の Swift では関数型に throws を付けることによって，その関数がエラーを送出し得ることを示すことができる。 SequenceType の非遅延版 map メソッドや filter メソッドは throws 付きの関数引数を受理し，かつメソッドそれ自身も rethrows 付きと宣言されている。 メソッドを評価したとき，実行結果として配列が得られるか，それともメソッド内部で関数引数の呼び出しが引き起こしたエラーの再送出 (rethrow) に終わるか，どちらかである。
その一方，LazySequenceType の map メソッドや filter メソッドは throws 付きの関数引数を受理しない。 これらのメソッドの評価結果はいわば遅延列 (lazy sequence) であり，関数引数の呼び出しは，この遅延列が作り出すジェネレータの next メソッドの実行時に行われる。 しかし，現行の Swift の GeneratorType の next メソッドの型は () -> Self.Element? であって () throws -> Self.Element? ではないから，ここでエラーを送出することはできない。 LazySequenceType の map メソッド等が throws 付きの関数引数を受理しないのはこのためである。
同様の理由により，今回与えた takeWhile, skipWhile 両メソッドでも throws 付きの関数引数 predicate: E throws -> Bool を無理なく受理させるようには定義できない。
これらのメソッドが throws 付きの関数引数を受理できるようにするためには，正攻法で考えれば Swift の GeneratorType の next メソッドの改訂が必要である。 それに伴って for-in 文の意味論と実装の改訂も必要である。 今や Swift はオープンソース化されているから，こうした改造は決して不可能ではない。 しかし，そのようにして言語自体を改訂するだけの有用性があるかどうか自明ではない。 エラーの扱いは未解決の課題である。