PythonでLINQライクなリスト処理ライブラリを実装する

問題

LINQはとても便利です。あまりにも便利すぎて、.NET Frameworkの外でも
「ここでLINQが使えたらな……」とついつい考えてしまいます。

しかし、LINQそのものの他言語への移植は、
本気で実装しようとするとLispのようなマクロが言語でサポートされていないと
かなり厳しいです。
とはいえ、LINQ to SQLやLINQ to XMLなどと違い、
LINQ to Objectsならばただのリスト処理ライブラリに過ぎませんから、
やろうと思えば実装は簡単にできるはずです。

今時の言語なら標準でリスト処理ライブラリのひとつやふたつは付いていますが、
大抵の場合、個々の機能に対する名前はライブラリ毎に異なっているため、
「LINQで言うところの Where はRubyだと何て名前だったっけ……」
と悩んだり混乱したりしがちです。
LINQライクなリスト処理ライブラリが使えるならばそれに越したことはありません。

という訳で、LINQライクなリスト処理ライブラリを実装してみましょう。
言語は何でも良いのですが、ここではPythonを使うことにします
(バージョンは2.5以降3.0未満です)。

なお、今回作成したPythonによるLINQライクなリスト処理ライブラリの実装はGitHubで公開中です。

方針

まずはリスト処理をどのようなスタイルで書くか決めましょう。
C#の場合、LINQ用の拡張構文を使って以下のように書くか:

var xs = from x in Enumerable.Range(0, 5)  // [0, 1, 2, 3, 4]
         where x % 2 == 0                  // [0, 2, 4]
         select x * x;                     // [0, 4, 16]

メソッドチェーンを利用して以下のように書きます:

var xs = Enumerable.Range(0, 5)   // [0, 1, 2, 3, 4]
         .Where(x => x % 2 == 0)  // [0, 2, 4]
         .Select(x => x * x);     // [0, 4, 16]

これは素のPythonならば以下のように書くところです:

xs = (x * x for x in range(5) if x % 2 == 0)

このような例ならばPythonの方が簡潔に書けますし、
コードも(英語として)読み易いのですが、
連鎖する処理が増えるとこの書き方ではモヤモヤしてきますし、
コード上で各処理がどういう順序で実行されるかも不明瞭です
(C#ならば概念的には各処理がコードに書かれた順に実行されると見做せます。
もちろん実際の実行過程は別物ですが)。

C#を真似るならば以下のように書くところでしょうか:

xs = (range(5)
      .where(lambda x: x % 2 == 0)
      .select(lambda x: x * x))

しかしC#と違ってPythonに拡張メソッドはありませんから、
iteratableなオブジェクト(C#で言えば IEnumerable<T> なインスタンス)に対して
好き勝手メソッドを「追加」することはできません。
強いて対処するなら
以下のようにiteratableなオブジェクトをラップすることでしょうか:

xs = (from(range(5))
      .where(lambda x: x % 2 == 0)
      .select(lambda x: x * x))

しかし from はPythonの世界では予約語なので識別子には使用できません。
かといって from 以外でLINQを連想させるような良い名前も思い浮かびません。

という訳で、発想を変えて、iteratableなオブジェクトの方ではなく、
iteratableなオブジェクトに対する処理の方をラップしましょう:

xs = (range(5)
      | where(lambda x: x % 2 == 0)
      | select(lambda x: x * x))

先程までの例では処理の連鎖を表すために . を使っていましたが、
それだと右辺は左辺のオブジェクトのメソッドでなければなりません。
ですので他の演算子を使って処理の連鎖を表すことにしましょう。
演算子は何でも良いのですが、
iteratableなオブジェクトに対してまず定義されることはないだろう
ビットOR (|)を使うことにします。
Pythonでは a | b のような演算子式は、
a が演算子をオーバーロードしている場合は
a の対応するメソッドが呼ばれ、
a が演算子をオーバーロードしていない場合は
b の対応するメソッドが呼ばれます。
これを利用すればどうとでもできそうです。
この方針で進めましょう。

リスト処理のラップ

まずリスト処理をラップするクラスを作りましょう。
名前はLINQに倣って Query とします:

class Query:
  def __init__(self, ys_from_xs):
    self.ys_from_xs = ys_from_xs
    return

  def __ror__(self, xs):
    return self.ys_from_xs(xs)

これは以下のように使います:

def pow(xs):
  for x in xs:
    yield x * x

xs = range(10) | Query(pow)

これでリスト処理を | で連鎖するための基礎ができました。

でも Query そのものは実装の都合上の存在なので、
ライブラリのユーザーからは見えないようにしたいものです。
そこでちょっと工夫すると以下の形になります:

def select(y_from_x):
  def q(xs):
    for x in xs:
      yield y_from_x(x)
  return Query(q)

xs = range(10) | select(lambda x: x * x)

これならユーザーが書くコードに Query は現れなくなりますし、
ユーザーの書くコードは当初考えていた書き方と同じになりました。

しかし今度は select の実装が大変なことになっています。
select の要点は for ... in ... yield の2行だけなのですが、
Query でラップするための処理で埋もれています。
それに、他のLINQのメソッドを移植することを考えると、
このラッピングコードを何度も繰り返すことになってしまいます。
これでは移植作業が苦痛になってしまいます。

幸い、Pythonには
decorator
があるため、このようなラッピングは簡潔に記述ができます。
具体的には以下のようになります:

def queryize(original_query):
  def wrapped_query(*args, **kw):
    return Query(lambda xs: original_query(xs, *args, **kw))
  wrapped_query.__doc__ = original_query.__doc__
  return wrapped_query

@queryize
def select(xs, y_from_x):
  for x in xs:
    yield y_from_x(x)

xs = range(10) | select(lambda x: x * x)

これでLINQのメソッドの移植も簡単になりました。
やりましたね。

LINQの各メソッドの移植

前節でリスト処理をラップするための土台ができあがったので、
後はLINQの各メソッドを移植していくだけです。
きちんとテストも書きつつ進めていきましょう。

to_list / to_tuple

LINQでのリスト処理の結果は IEnumerable<T> になっており、
foreach で列挙できること以外は不明ということになっています。
大抵の場合、これで何も困らないのですが、
場合によっては配列などの型に変換する必要があります。
という訳で手始めにこの変換処理を実装しましょう
(というより、これを実装しないとテストが気楽に書けません)。
LINQに to_tuple 相当のものは存在しませんが、
Python的にはないと困るので合わせて実装しておきます。

@queryize
def to_list(xs):
  '''
  >>> range(10) | to_list()
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  '''
  return list(xs)

@queryize
def to_tuple(xs):
  '''
  >>> range(10) | to_tuple()
  (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
  '''
  return tuple(xs)

select / select_with_index

select (リストの各要素の変換)は以下のようになります:

@queryize
def select(xs, y_from_x):
  '''
  >>> range(10) | select(lambda x: x * x) | to_tuple()
  (0, 1, 4, 9, 16, 25, 36, 49, 64, 81)
  '''
  for x in xs:
    yield y_from_x(x)

また、LINQではインデックス付きのバージョンもあるので、
それも select_with_index という名前で実装します
(C#と違って引数の型でのオーバーロードは記述が煩雑なので
名前を変えて提供することにします):

@queryize
def select_with_index(xs, y_from_x_i):
  '''
  >>> [3, 2, 1] | select_with_index(lambda x, i: x * i) | to_tuple()
  (0, 2, 2)
  '''
  i = 0
  for x in xs:
    yield y_from_x_i(x, i)
    i += 1

where / where_with_index

where (リストの内容のフィルタリング)は以下のようになります:

@queryize
def where(xs, predicate):
  '''
  >>> range(10) | where(lambda x: x % 2 == 0) | to_tuple()
  (0, 2, 4, 6, 8)
  '''
  for x in xs:
    if predicate(x):
      yield x

select と同様にインデックス付きのバージョンもあるので、
where_with_index として実装しましょう:

@queryize
def where_with_index(xs, predicate_with_index):
  '''
  >>> [1, 3, 5, 7] | where_with_index(lambda x, i: i % 2 == 0) | to_tuple()
  (1, 5)
  '''
  i = 0
  for x in xs:
    if predicate_with_index(x, i):
      yield x
    i += 1

take / skip

take (リストの先頭から高々N個の要素を取り出す)は以下のようになります:

@queryize
def take(xs, n):
  '''
  >>> range(10) | take(5) | to_tuple()
  (0, 1, 2, 3, 4)
  '''
  i = 0
  for x in xs:
    if i < n:
      yield x
    else:
      return
    i += 1

skip (リストの先頭から高々N個の要素を除外する)は以下のようになります:

@queryize
def skip(xs, n):
  '''
  >>> range(10) | skip(5) | to_tuple()
  (5, 6, 7, 8, 9)
  '''
  i = 0
  for x in xs:
    if n <= i:
      yield x
    i += 1

その他

他にも挙げていくとキリがないので詳細は
今回実装したライブラリのソースコード
を参照してください。

遅延評価

例えば以下のPythonコードを実行するといつかはメモリーを食い潰して落ちます:

def yes():
  while True:
    yield 'y'

list(yes())

yes() は無限に 'y' を返し続けるシーケンスです。
これをリストに変換しているのですが、
無限シーケンスを変換し終えることはできないため、
メモリーを食い潰して落ちるという訳です。

ところでLINQのメソッドのほとんどが遅延評価されます。
つまり、リスト処理は逐次実行されるのではなく、
要素が本当に必要になった段階で実行されます。

今回実装したライブラリも実は遅延評価されます。
ですから以下のようなコードを書いてもメモリーを食い潰すことはありません。

# 結果は無限シーケンスだけれど要素を列挙しなければ大丈夫。
yes() | select(len)

# to_tuple()で要素を列挙するが、take(5)で切り捨てているので大丈夫。
yes() | take(5) | to_tuple()

補足

もちろん世の中にはPythonによるLINQライクなものの実装が既に色々とありますが、
今回はPythonの布教も兼ねて実装してみました。