(1) へ   (3) へ   English

Go 言語による LINQ to Objects の試作 (2)

2014-01-14, 2014-01-20 (鈴)

1. はじめに

前回Go 言語 [golang.org] の関数型に対するメソッドとして C# の LINQ to Objects の メソッド群 [microsoft.com] のいくつかを実装した。 しかし,メソッド数は過少であり,panic 文による大域脱出など他言語からの引き写しで Go 言語らしくない面もあった。 また Each のような型名は必ずしも分かりやすいとは言えなかった。

ここでは Go 1.2 に対し,より実用的に LINQ to Objects を実現する試みを述べる。

Go 言語で LINQ to Objects に似たメソッドを実装する別のアプローチとして 2013 年に公開された Ahmet Alp Balkan: ahmetalpbalkan / go-linq [github.com] がある。 しかし,これはスライスによるオブジェクトの有限列をメソッド間で引き渡しており,潜在的に無限の列を 一定のサイズで処理できる本来の LINQ to Objects とは空間計算量と Take メソッド等による打ち切り時の時間計算量が異なる。 とりわけ,このアプローチでは .NET の Reactive Extensions [microsoft.com] のように無限の非同期イベントの列に対するリアクティブ・プログラミングをかなえることはできない。

一方,前回 (2012 年) と同じく今回ここで述べる実装の計算量は本来の LINQ to Objects と同じであり,LINQ のメソッド連鎖が事実上のループ融合を実現している。 無限の列に対応でき,リアクティブ・プログラミングへの応用も可能である。

2. Enumerate 型

C# の LINQ to Objects の各メソッドは IEnumerable [microsoft.com] インタフェースへの拡張メソッドとして定義されており,IEnumerable インタフェースは GetEnumerator() メソッドを規定している。 GetEnumerator() メソッドが返す IEnumerator [microsoft.com] オブジェクトはそのメソッドを通じて何らかの列の各要素を順に与える。

Go 言語でこれを実現するには,何らかの列の各要素を順に与えられる処理を引数としてとる関数を IEnumerable インタフェースのかわりにすればよい。

列の要素の型を Any とする。

type Any interface{}

何らかの列の各要素を順に与えられる処理を Operate とする。

type Operate func(Any) error

何らかの列の各要素を順に与えられる処理を引数にとる関数を Enumerate とする。

type Enumerate func(Operate) error

この Enumerate 型が C# の IEnumerable インタフェースのかわりとなる。 これに対して LINQ to Objects の各メソッドを定義する。 Enumerate 型の関数は典型的には内部にループをもつ。 error 型の戻り値が非 nil のとき,このループは途中でも終了する取り決めとする。

関数は (手続き型言語では) 動作を表しますから,ここでは関数型を動詞で命名しました。 一昨年 前回の§2 では Enumerate ではなく Each と命名しました。 Ruby の each メソッドに相当する関数を表すからです。 しかし,Go 言語の型名としては意味をとりづらく失敗でした。
前回の§3 の Take メソッドにみるように,前回はループの途中終了を (他言語の「例外」による大域脱出の引き写しで) panic 文により実現していました。 少しコードの字面がうるさくなるきらいがありますが, error 型の戻り値をもたせることにより,こうした panic 文を平常時の実行経路から無くすことができます。

例えば,整数引数 n に対して n, n+1, n+2, n+3, ... と無限の列を表す Enumerate 値を返す関数 IntsFrom(n int) は次のように定義できる。

func IntsFrom(n int) Enumerate {
    return func(yield Operate) error {
        for i := n; ; i++ {
            err := yield(i)
            if err != nil {
                return err
            }
        }
    }
}
IntsFrom(n) は元々の LINQ にないオリジナルの関数です。 integers from n と読んでください。

ling.go では IntsFrom のほか .NET LINQ to Objects と同じく Empty(), Range(start, count int), Repeat(element Any, count int) の各関数を定義した。 また,一般的な便宜のため chan Any, *list.List, string, および任意のスライスと配列から Enumerate 値を作る From(x interface{}) 関数を用意した。

From 関数は 前回の§4 の Enumerable(x Any) 関数に相当します。 From という関数名は LINQ のクエリ式に由来します。 LINQ のための変換関数の名前としては Ahmet Alp Balkan: ahmetalpbalkan / go-linq [github.com] が初出ではないかと思います。

From 関数が前回の実装と異なる点は chan Any 型のチャネルを入力源とできるようにしてリアクティブ・プログラミングのための便宜を図ったことと,Go 言語の reflect パッケージを利用して任意の要素型のスライスと配列に対応したことである。 該当部を含む抜粋を示す。

func From(x interface{}) Enumerate {
    switch seq := x.(type) {
    case <-chan Any:
        return func(yield Operate) error {
            for {
                value, ok := <-seq
                if !ok {
                    return nil
                }
                err := yield(value)
                if err != nil {
                    return err
                }
            }
            return nil
        }
    case chan Any:
        return From((<-chan Any)(seq))
    default:
        v := reflect.ValueOf(x)
        k := v.Kind()
        if k == reflect.Slice || k == reflect.Array {
            return func(yield Operate) error {
                len := v.Len()
                for i := 0; i < len; i++ {
                    e := v.Index(i)
                    err := yield(e.Interface())
                    if err != nil {
                        return err
                    }
                }
                return nil
            }
        }
    }
    return func(yield Operate) error {
        return yield(x)
    }
}

3. LINQ メソッドの実装

主要な LINQ メソッドの実装を示す。

列の各要素に関数 f を適用して新しい列を構成する Enumerable.Select [microsoft.com] 相当のメソッドは次のように定義される。

func (forEach Enumerate) Select(f func(Any) Any) Enumerate {
    return func(yield Operate) error {
        return forEach(func(e Any) error {
            value := f(e)
            return yield(value)
        })
    }
}
Enumerate 型のメソッド・レシーバの名前を forEach としていることに注意してください。 典型的な Enumerate 値はこの名前が示すように列の各要素についてループする関数です。 前節の IntsFrom 関数や From 関数の定義を読み直してください。

列から述語 (predicate) を満たす要素だけを選び出す Enumerable.Where [microsoft.com] 相当のメソッドは次のように定義される。

func (forEach Enumerate) Where(predicate func(Any) bool) Enumerate {
    return func(yield Operate) error {
        return forEach(func(e Any) error {
            if predicate(e) {
                return yield(e)
            } else {
                return nil
            }
        })
    }
}

列からはじめの n 個の要素だけをとる Enumerable.Take [microsoft.com] 相当のメソッドは次のように定義される。

func (forEach Enumerate) Take(n int) Enumerate {
    token := errors.New("Take")
    return func(yield Operate) error {
        if n > 0 {
            i := 0
            err := forEach(func(e Any) error {
                i++
                er := yield(e)
                if er != nil {
                    return er
                } else if i >= n {
                    return token
                } else {
                    return nil
                }
            })
            if err != token {
                return err
            }
        }
        return nil
    }
}

Take メソッドによるループの中断のためのエラー値なのか調べるため,処理の終わりに err != tokenerr を判定していることに注意されたい。 token は実際には構造体のアドレスであり,インタフェースの比較演算では実行時型の一致も調べられるから,この判定は常に正しく働く。 Go 1.2 処理系の配布物に含まれる go/src/pkg/errors/erros.go から errors.New 関数の実装を下記に引用する。

func New(text string) error {
    return &errorString{text}
}
他のどんな error 値であれ,それが errorString 構造体へのアドレスという型をもち,さらにその値つまり構造体のアドレスが token と偶然に一致する,ということは妥当な Go 言語処理系のもとではあり得ません。

4. 実行例

添付のソースの Unix 類 (Mac OS X 10.8.5) での実行例を示す。

01:~/tmp$ tar xvf ../Downloads/go-linq-26-01-20.tar.bz2
x src/
x src/linq/
x src/linq/linq.go
x src/linq/linq_test.go
x linq_test1.go
x linq_test2.go
x linq_test3.go
01:~/tmp$ GOPATH=`pwd` go test linq
ok      linq    0.022s
01:~/tmp$ GOPATH=`pwd` go run linq_test1.go
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-
[3 13 23]
<nil>
01:~/tmp$ GOPATH=`pwd` go run linq_test2.go
[]linq.Any{2, 7}
[]linq.Any{2, 7}
[]linq.Any{"2", "7"}
[]linq.Any{50, 55}
[]linq.Any{2, 7}
01:~/tmp$ GOPATH=`pwd` go run linq_test3.go 100
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fiz
z 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz
 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 Fi
zzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz
 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 
98 Fizz Buzz 
01:~/tmp$  

linq_test1.go, linq_test2.go, linq_test3.go前回からの引き継ぎとして用意した。 実行例としては目立たないが実際には包括的なテストが

  GOPATH=`pwd` go test linq

によって実施されている。 その出力 "ok linq 0.022s" は src/linq/ling_test.go のテストに 0.022 秒かかり,"Output:" コメントとして記述された模範出力と実際の実行による出力がすべて無事に一致したことを意味する。

そのテスト・コードと模範出力は godoc によるドキュメント内の "Example" として Web ブラウザから見ることもできる。 下記のように godoc を実行して Web ブラウザで 6060 番ポートを閲覧すればよい。

01:~/tmp$ GOPATH=`pwd` godoc -http=:6060 &
[1] 1987
01:~/tmp$  

godoc はソース・ファイル linq.go と linq_test.go の内容からその場で上図のようなドキュメントを自動生成します。

linq.go の該当部分を示します。 コメント,関数名とパラメタ,結果の宣言がドキュメントとして自動的に取り出されます。

// SelectMany creates an Enumerate which applies f to each of subsequences
// and concatenates them to a single flat sequence.
func (forEach Enumerate) SelectMany(f func(Any) Enumerate) Enumerate {
    return func(yield Operate) error {
        return forEach(func(e Any) error {
            forEach2 := f(e)
            return forEach2(func(e2 Any) error {
                return yield(e2)
            })
        })
    }
}

linq_test.go の該当部分を示します。 関数本体がテスト・コードの実行とドキュメントのコード例の両方に自動的に使われます。 "Output:" コメントがテスト結果の検証とドキュメントの出力例の両方に自動的に使われます。

func ExampleEnumerate_SelectMany() {
    type PetOwner struct {
        Name string
        Pets []string
    }
    owners := []PetOwner{
        PetOwner{"Taro", []string{"Koro", "Pochi", "Tama"}},
        PetOwner{"Jiro", []string{"Kuro", "Buchi", "Tora"}},
    }

    x, err := From(owners).SelectMany(func(e Any) Enumerate {
        return From(e.(PetOwner).Pets)
    }).ToSlice()
    Printf("%v, %v\n", x, err)
    // Output:
    // [Koro Pochi Tama Kuro Buchi Tora], <nil>
}

上記を Enumerable.SelectMany [microsoft.com] の例と比較してください。

5. おわりに

今回の試みでは一昨年の Go 言語による LINQ to Objects の実装を洗練させ,実地での応用により堪えるものとした。 とりわけ,今はまだ下記のような linq_test.go での簡単なテスト・コードでしか動かしていないが,LINQ の入力源としてのチャネルの利用は Go 言語ならではのコンカレント性を活かした有用な用法があるのではないかと期待される。

    p := func(e Any) error {
        Printf(" %#v", e)
        return nil
    }

    ch := make(chan Any)
    go func() {
        ch <- "Funa"
        ch <- "1-hachi"
        ch <- "2-hachi"
        close(ch)
    }()
    From(ch)(p) // chan Any
    Println()
    // Output:
    //  "Funa" "1-hachi" "2-hachi"

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