enumerabler.rb: Enumerable の遅延評価版メソッドライブラリ

たとえば整数の配列から、条件に合う要素のうち、最初に現れる 10 個だけ拾いたいとき、どうしますか？

ary.select {|x| x.even? }.take(10)

↑これは非常に明瞭なプログラムです。しかし select は、最初の 10 個だけでなく全要素をチェックしてしまうため、ary が大きいと無駄にループします。また、select の戻り値となる中間配列も無駄です。

ret = []
ary.each do |x|
  ret << x if x.even?
  break if ret.size == 10
end

↑これなら 10 個見つかった時点で終了してくれるし、無駄な配列確保もありません。しかし非常に強引で原始的で煩雑なプログラムであり、Ruby 1.9 の時代を迎えた新人類である我々には、可読性やメンテナンス性に問題があると言わざるを得ない。一言で言うと品がないのです。

「Ruby 1.9 には Enumerator と to_enum があるから何とかなる？」

発想はいいですが、残念なお知らせです。

(1..50).to_enum(:select) {|x| x.even? }.take(10)
  #=> [1,2,3,4,5,6,7,8,9,10] # 全然 select できていない

なんでこれでうまくいかないかは、説明が難しいので自分で考えてください。to_enum は難しいんですよね。
結論だけ言うと、Enumerable#select をどんな風に to_enum しても、目標の挙動は達成できません。できないはずです。たぶん。
どうすればいいかというと、以下のように Enumerable#select を使わず Enumerable.new で書けばいい (書くしかない) です。

module Enumerable
  def selector(&blk)
    Enumerator.new do |e|
      each do |x|
        e << x if blk[x]
      end
    end
  end
end

しかし、いちいちこんなのを定義するのは面倒ですよね。

enumerabler.rb

そこで、上記のような定義を集めたライブラリ enumerabler.rb を作りました。

require "enumerabler"

ary.selector {|x| x.even? }.take(10)

select の代わりに selector と書きます。select は配列を返しますが、selector はそれに相当する Enumerator を返します。Enumerator なので、評価が遅延されています。上のプログラムでは、10 個見つかった時点で評価が止まります。
enumerabler.rb は、Enumrable に grepper 、finder_all (all_finder 、selector) 、rejecter 、collector (mapper) 、flat_mapper (concat_collector) 、zipper 、taker 、taker_while 、dropper 、dropper_while を追加します *1 。どれも、-er のないメソッドが返す配列に相当する Enumerator を返します。
個人的には「-er を付けると Enumerator を返す」という convension が気に入っています。(自分で言うな)

「Fiber を使うから遅いんじゃないの？」

いいえ、enumerabler.rb を使うだけでは、Fiber の生成や呼び出しは一切起こりません。なぜだか気になる人は Ruby のソースを読んでください。
ただし、Proc の呼び出しが多数発生するので、遅いことは確かです。でも、中間配列の分の消費メモリ量は減ります。

活用例

p ary.selector {|x| x.even? }.taker(100).take_while {|x| x >= 0 }

↑最初に現れる 100 個の偶数 (ただし負の値があったら 100 個行かなくても打ち切る) という抽出操作を、無駄な列挙や中間配列生成なしに行う。

require "enumerabler"

def sieve(e, &blk)
  yield n = e.first
  sieve(e.rejecter {|x| x % n == 0 }, &blk)
end

sieve(2..(1.0/0.0)) {|x| p x } #=> 2, 3, 5, 7, 11, 13, 17, 19, 23, ...

↑エラトステネスの篩。rejecter を使っています。

require "enumerabler"

def fibonacci
  Enumerator.new do |e|
    e << 1
    e << 1
    fibonacci.zip(fibonacci.dropper(1)) {|x, y| e << x + y }
  end
end

fibonacci.each {|x| p x } #=> 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

↑フィボナッチ数列。dropper を使うことで無限列を drop できます。ただし、call-by-name なのと、zip は中で Fiber を呼ぶので、スピードはとても遅いです。

インストール方法とソース

$ gem install enumerabler

http://github.com/mame/enumerabler

*1:余談ですが、-er と -or の使い分けがわからない。