続編 (高速化) へ
続編 (Groovy 応用) へ

Ruby のための LINQ ライク・メソッドの使用例

2012-09-24, 2012-10-01 追補 (鈴)

1. はじめに

"Ruby 1.8.7 からの LINQ ライクな Enumerable メソッド" では,C# の LINQ と実質的に同じものである Ruby 2.0.0 開発版の Enumerator::Lazy と同等の機能を,Enumerable モジュールのメソッドとして従来の Ruby で実現できることを示し,それらを LINQ ライクなメソッドと表現した。 "解説: Ruby/mruby LINQ ライク・メソッド" では,それが Ruby のブロック付きメソッドの機構の簡単な応用であることを解説した。

具体的には Unix の exit(3) と _exit(2) の類推から,map メソッドに対する _map メソッド,take メソッドに対する _take メソッドなど,既存の Enumerable メソッドに対して名前の先頭に下線を付した LINQ ライク・メソッドを新しく定義した。 既存のメソッドと等価な動作は,対応する LINQ ライク・メソッドから簡単に組み立てることができるが,その逆はできない。

しかし,このような LINQ ライク・メソッドを Ruby プログラムの中で実際どのように使うのか今まで例を十分に示してこなかった。 本稿では三つの題材に四つのプログラムを与えて,この不足を補う。 とりわけ第4のプログラム (§5) は Ruby を高度に関数型言語らしくする例である。

2. FizzBuzz を n 個だけ表示する

1 から順に数えて行き,3 の倍数のとき Fizz を唱え,5 の倍数のとき Buzz を唱え, 両方の倍数のとき Fizz Buzz を唱え, それ以外のときは数をそのまま唱える Fizz Buzz 遊び [wikipedia.org] を Ruby で再現しよう。簡単のため,唱えさせる代わりにコマンド行引数として与えた数まで画面に表示させることにする。

まず,(1 .. 1.0/0) として 1 から無限大までの仮想的な列を作り,これに対して _map メソッドでシンボル :Fizz:Buzz への置き換えを仮想的に済ませた fizzbuzz を定義する。 次に,この仮想的な列 fizzbuzz に対して _take(n) で最初の n 個だけとり, each でそれぞれを print する。

#!/usr/bin/env ruby

require '_enum'

n = ARGV[0].to_i

fizzbuzz = (1 .. 1.0/0)._map {|i| 
  if i % 3 == 0 then
    if i % 5 == 0 then
      :FizzBuzz
    else
      :Fizz
    end
  elsif i % 5 == 0 then
    :Buzz
  else
    i
  end
}

fizzbuzz._take(n).each {|i|
  print i, " " 
}

puts

ここで take(n) ではなく LINQ ライクな _take(n) を使っていることに注意しよう。 これにより最初から最後までついに中間的な配列を作らずに済ませている。 コマンド行引数として 100 を与えて実行させた例を示す。

01:~/tmp$ ./fizzbuzz.rb 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$  

3. FizzBuzz で Fizz になる数を n 個挙げる

前節の fizzbuzz をそのまま使うという前提で,Fizz になるような数の列を n 個挙げることを考えてみよう。

列の中で FizzBuzz に置き換える前の元の数は Enumerable#each_with_index [ruby-lang.org] で与えられるインデックスに 1 を足せば得られる。 これを Ruby にはタプルがないから2要素の配列で代用して _select メソッドに渡し,Fizz を選別してから _take(n) ではじめの n 個だけとって each で表示すればよい。

#!/usr/bin/env ruby

require '_enum'

n = ARGV[0].to_i

fizzbuzz = (1 .. 1.0/0)._map {|i| 
  if i % 3 == 0 then
    if i % 5 == 0 then
      :FizzBuzz
    else
      :Fizz
    end
  elsif i % 5 == 0 then
    :Buzz
  else
    i
  end
}

fizzbuzz.each_with_index._map {|value, index|
  [value, index + 1]
}._select {|value, i|
  value == :Fizz
}._take(n).each {|value, i|
  print i, " "
}

puts

コマンド行引数として 100 を与えて実行させた例を示す。

01:~/tmp$ ./fizz_numbers.rb 100
3 6 9 12 18 21 24 27 33 36 39 42 48 51 54 57 63 66 69 72 78 81 84 87 93 96 99 10
2 108 111 114 117 123 126 129 132 138 141 144 147 153 156 159 162 168 171 174 17
7 183 186 189 192 198 201 204 207 213 216 219 222 228 231 234 237 243 246 249 25
2 258 261 264 267 273 276 279 282 288 291 294 297 303 306 309 312 318 321 324 32
7 333 336 339 342 348 351 354 357 363 366 369 372 
01:~/tmp$  

この例では Ruby 1.8.7 以降のブロック無し each_with_index メソッドを連鎖の中間で利用している。 LINQ ライク・メソッドは従来の Ruby の自然な拡張であり,このように既存のメソッドと矛盾なくメソッド連鎖させることができる。

クイズ: Fizz になるような数の列の出力は,本当は前節の fizzbuzz を使わず,ただ単に 3 で割れて 5 で割れない数を列挙すればもっと簡単にできます。 どう書けばよいでしょうか?

3.1 Ruby 1.9 に対する注意

fizz_numbers.rb プログラムは ruby 1.8.7 では問題なく動作するが ruby 1.9.3 では次のようなエラーに終わる。

01:~/tmp$ ruby1.9 -I. fizz_numbers.rb 100
fizz_numbers.rb:22:in `block in <main>': undefined method `+' for nil:NilClass (
NoMethodError)
	from /home/suzuki/work/ruby~/_enum.rb:31:in `block (2 levels) in _collec
t'
	from /home/suzuki/work/ruby~/_enum.rb:18:in `[]'
	from /home/suzuki/work/ruby~/_enum.rb:18:in `<<'
	from /home/suzuki/work/ruby~/_enum.rb:31:in `block (2 levels) in _collec
t'
	from /home/suzuki/work/ruby~/_enum.rb:30:in `each'
	from /home/suzuki/work/ruby~/_enum.rb:30:in `block in _collect'
	from /home/suzuki/work/ruby~/_enum.rb:13:in `[]'
	from /home/suzuki/work/ruby~/_enum.rb:13:in `each'
	from /home/suzuki/work/ruby~/_enum.rb:30:in `each_with_index'
	from /home/suzuki/work/ruby~/_enum.rb:30:in `each'
	from /home/suzuki/work/ruby~/_enum.rb:30:in `block in _collect'
	from /home/suzuki/work/ruby~/_enum.rb:13:in `[]'
	from /home/suzuki/work/ruby~/_enum.rb:13:in `each'
	from /home/suzuki/work/ruby~/_enum.rb:79:in `block in _find_all'
	from /home/suzuki/work/ruby~/_enum.rb:13:in `[]'
	from /home/suzuki/work/ruby~/_enum.rb:13:in `each'
	from /home/suzuki/work/ruby~/_enum.rb:114:in `block in _take'
	from /home/suzuki/work/ruby~/_enum.rb:13:in `[]'
	from /home/suzuki/work/ruby~/_enum.rb:13:in `each'
	from fizz_numbers.rb:21:in `<main>'
11:~/tmp$  

これは新しい Ruby で引数の受け渡し方法が変更されたことによる。 each_with_index で作られてブロックに第2引数として渡されるはずのインデックスが実際には渡されずに nil がセットされるため,+ メソッドが未定義である (つまり nil にどうやって加算演算をすればよいか分からない) というエラーになる。 下記にこの不整合をより端的に示す。

01:~/tmp$ ruby -r ./_enum.rb -e 'p ("a".."d").each_with_index._map{|e, i| [e, i]
}.to_a'
[["a", 0], ["b", 1], ["c", 2], ["d", 3]]
01:~/tmp$ ruby1.9 -r ./_enum.rb -e 'p ("a".."d").each_with_index._map{|e, i| [e,
 i]}.to_a'
[["a", nil], ["b", nil], ["c", nil], ["d", nil]]
01:~/tmp$  

ruby 1.9.3 で動作させるには _enum.rb を次のように改造すればよい。 エラーを起こしている _map_collect の別名である。 改造後も ruby 1.9.3 だけでなく ruby 1.8.7 でも動作する。

--- _enum.rb.orig	2012-07-09 14:26:20.000000000 +0900
+++ _enum.rb	2012-10-01 12:21:25.000000000 +0900
@@ -27,7 +27,8 @@
 
   def _collect
     return enum_for(:_collect) unless block_given?
-    iterator {|y| each {|e|
+    iterator {|y| each {|*e|
+        e = e[0] if e.length == 1
         y << (yield e)
       }}
   end

一般に _collect だけでなく,すべての LINQ ライク・メソッドに同様の改造を施す必要があるが,性能に対する悪影響を避けるために複数引数を処理する特別な LINQ ライク・メソッドを一つだけ設けて使うことが妥当であろう。

具体的な案については続編で示します。

なお,本稿の他のプログラムは無改造のままで ruby 1.9.3 でも ruby 1.8.7 でも動作する。

4. n 以下の Happy number を挙げる

ある自然数を初項とし,項の十進表現での各桁の二乗を足した結果を次の項とするような数列を考えたとき,その列に 1 が出現するならば,その自然数を Happy number [wikipedia.org] と呼ぶ。 例えば 7 は

7, (72 =) 49, (42 + 92 = 16 + 81 =) 97, (92 + 72 = 81 + 49 =) 130, (12 + 32 + 02 = 1 + 9 + 0 =) 10, (12 + 02 = 1 + 0 =) 1

だから Happy number である。 数列に 4 が出現することと初項が Happy number でないことは等価であることが知られている。 したがって,与えられた数 n 以下の Happy number は次のスクリプトで求めることができる。

#!/usr/bin/env ruby

require '_enum'

# digits_of(31416).to_a => [6, 1, 4, 1, 3]
def digits_of(n)
  Enumerable::iterator {|y|
    while n > 0 do
      y << n % 10
      n = n / 10
    end
  }
end

def is_happy(n)
  loop {
    n = digits_of(n)._map {|i| i * i}.inject {|x, y| x + y}
    return true if n == 1
    return false if n == 4
  }
end

n = ARGV[0].to_i
(1..n)._select {|i| is_happy(i)}.each {|i| print i, " "}
puts

digits_of(n)n の十進表現での各桁を1の桁から順に仮想的な列として与える。 ._map {|i| i * i} は各桁の二乗を求める。 ._inject {|x, y| x + y} はそれを足し合わせる。 これらの処理はパイプライン的に行われ,配列のような中間的なデータ構造は作られない。

500 以下の Happy number を求めた例を示す。

01:~/tmp$ ./happy_numbers.rb 500
1 7 10 13 19 23 28 31 32 44 49 68 70 79 82 86 91 94 97 100 103 109 129 130 133 1
39 167 176 188 190 192 193 203 208 219 226 230 236 239 262 263 280 291 293 301 3
02 310 313 319 320 326 329 331 338 356 362 365 367 368 376 379 383 386 391 392 3
97 404 409 440 446 464 469 478 487 490 496 
01:~/tmp$  

5. _iterate と単一代入で Happy number を挙げる

前節で示したコードは十分に簡明だが,while 文や loop イテレータを使い,破壊的な代入で数列の次の項へと進んでいる点に手続き型プログラミングの特徴が出ている。 簡単なメソッドの追加でこれを無くすことができる。 ここではそれを考えてみよう。

ここでの主題は破壊的代入 (destructive assignment) をいかに回避するかです。 破壊的代入とは,変数の今までの値を書き換えるような代入です (C++ でいう初期化ではない代入演算のことです)。 なぜ,薮から棒にこれを無くしたいのか? それは,(乱暴に言えば) これこそがプログラムの良い性質を損なう邪悪の根源として,主に関数型プログラミングの世界で撲滅の対象となっているからです。 ここではさしあたり,ひとつのパズルとして本節を読んでください。

はじめに,任意のオブジェクト a0 を初項とし,任意の1引数関数 f による漸化式 (recurrence relation)

an + 1 = f(an)

で定められる仮想的な無限列を実現するメソッド

a0._iterate {|a| f(a) }

を考えよう。

メソッド名 _iterate は,漸化式と初項で無限の遅延リストを作る Haskell の標準関数 iterate にちなんだものです。 下線を付けたのは,それが広い意味での LINQ ライク・メソッドだからです。

これは次のように定義できる。このファイルを iterate.rb とする。

require '_enum'

class Object
  # "a"._iterate {|s| s + s}.take(3) => ["a", "aa", "aaaa"]
  def _iterate
    Enumerable::iterator {|y|
      a = self
      loop {
        y << a
        a = (yield a)
      }
    }
  end

  # "a".iterate {|s| break if s.length > 5; p s; s + s} => nil
  #                        (ただし "a" "aa" "aaaa" を印字する)
  def iterate(&block)
    _iterate(&block).each {}
  end
end

ここでは _iterate に対応する非 LINQ ライク・メソッドとして iterate も定義する。 こちらはループ制御変数をブロックの最後の式で次々と変化させる無限ループの制御構造として使うことができる。

非 LINQ ライク・メソッド iterate はそのままでは無限ループになりますから,その戻り値を決定するのは事実上 break です。 それまで計算した列の各項は捨てられます。 ですから,はじめから無駄にならないように iterate メソッドの本体では .to_a ではなく .each {} で計算を駆動します。

使用例を示す。

01:~/tmp$ irb -r iterate.rb
>> "a"._iterate {|s| s + s}.take(3)
=> ["a", "aa", "aaaa"]
>> "a"._iterate {|s| s + s}.take(5)
=> ["a", "aa", "aaaa", "aaaaaaaa", "aaaaaaaaaaaaaaaa"]
>> "a"._iterate {|s| s.succ}.take(10)
=> ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
>> 2._iterate {|i| i + 2}.take(10)
=> [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
>> 2.iterate {|i| break if i > 10; p i; i + 2}
2
4
6
8
10
=> nil
>> 2.iterate {|i| break i if i > 10; p i; i + 2}
2
4
6
8
10
=> 12
>>  

この iterate.rb を使えば,コマンド行で与えられた数以下の Happy number を求めるスクリプトは次のように書ける。 もともと数列で定義されていた Happy number の判定に,定義どおりの (仮想的な) 数列 seq をそのまま使っている点に注意しよう。 もちろん,今回もやはり,中間的な配列などは実際には作っていない。

#!/usr/bin/env ruby

require 'iterate'

# digits_of(31416).to_a => [6, 1, 4, 1, 3]
def digits_of(k)
  Enumerable::iterator {|y|
    k.iterate {|n|
      break unless n > 0
      y << n % 10
      n / 10
    }
  }
end

def is_happy(k)
  seq = k._iterate {|n|
    digits_of(n)._map {|i| i * i}.inject {|x, y| x + y}
  }
  seq.each {|n|
    return true if n == 1
    return false if n == 4
  }
end

n = ARGV[0].to_i
(1..n)._select {|i| is_happy(i)}.each {|i| print i, " "}
puts

変数への代入はどれも初期値設定だけの単一代入であり,破壊的代入は一掃されている。

y << n % 10 のあたりに異論がありそうですが……。

実行例を示す。

01:~/tmp$ ./happy_numbers2.rb 500
1 7 10 13 19 23 28 31 32 44 49 68 70 79 82 86 91 94 97 100 103 109 129 130 133 1
39 167 176 188 190 192 193 203 208 219 226 230 236 239 262 263 280 291 293 301 3
02 310 313 319 320 326 329 331 338 356 362 365 367 368 376 379 383 386 391 392 3
97 404 409 440 446 464 469 478 487 490 496 
01:~/tmp$  

6. おわりに

本稿で説明した例はどれも潜在的に長大なデータを扱いながら (§3 での二項タプルの代用としての2要素配列を除いて) 配列のような集合体データを全く作っていない。 従来からの手続き型プログラミングでこのように中間的なデータ構築を避けようとしたとき, 手続き間の引数受け渡しの制約によりしばしば大域的な変数にたよるか,あるいは大きな一枚岩のコードにせざるを得なかった。 それに対し LINQ ライクなメソッドは中間的なデータの構築を避けつつ問題を概念的に自然であるようなブロックへと小さく分割することを可能にする。 この違いは,ある程度以上の規模の問題を実用的な意味で解決できるかどうか決定する要因の一つとなる。

§3 の問題は "fizzになる数字をn個挙げる"をGroovyで無限リストと遅延評価を駆使して - No Programming, No Life [hatenablog.jp] にヒントを得た。 §4 の問題は Happy number - コードの恵み [hatena.ne.jp] にヒントを得た。 この二つの記事ではどちらも実装言語として Groovy を使っており,その実装方法は互いに大きく違っているが,アプローチとしてはどちらも外部イテレータを基礎としている。 これに対し,本稿のアプローチは Ruby の自然な拡張として内部イテレータを基礎としている。 同じアプローチに基づく Groovy のメソッドも実装している。 興味があれば参照し,比較されたい。

§5_iterateiterate の両メソッドは Feature #6758: Object#sequence - ruby-trunk [ruby-lang.org] の議論にヒントを得た。 §5 のように仮想的な列を表現する _iterate と制御構造を表現する iterate の二つを用意することが,対称性と既存メソッド群とのバランスの点でおそらく最もエレガントであろう。

§3 のクイズ 解答例 (要点だけ示します): (1 .. 1.0/0)._select {|i| i % 3 == 0 && i % 5 != 0}._take(n).each {|i| print i, " "}

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