Rubyのrepeat関数でフィボナッチ、トリボナッチ、テトラナッチ！

１または複数の初期値に任意の関数を繰り返し適用して、その結果のリストを返す汎用関数repeatを定義しよう。

def repeat(f, *args)
  Enumerator.new { |y| loop { y << (*args = f[*args]) } }
end

repeatは関数f¹とfの初期値となるargsを引数に取り、Enueratorオブジェクトを返す。

Enumeratorのブロックの中ではloopによってargsを関数fに適用した結果が、繰り返しyつまりEnumerable::Yielderオブジェクトに渡される。

次にフィボナッチだ。

def fib
  ->a,b{ [b, a+b] }
end

fib関数は数列上の並んだ2つの数a,bを取り、次の並びとしてその上位の数bとa,bの和の組を返す。

さあ、今作成した2つの関数repeatとfibを使って、フィボナッチ数列の第20位までを求めよう。

fibonacci = repeat(fib, 0, 1)
fibonacci.take(20).map(&:first) # => [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

もちろんfib関数は高階関数である必要はない。通常の関数でいい。

def fibm(a, b)
  [b, a+b]
end

ただしこの場合は関数をオブジェクト化して、repeat関数に渡す必要がある。

fibonacci = repeat(method(:fibm), 0, 1)
fibonacci.take(20).map(&:first) # => [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

次はトリボナッチだ。フィボナッチが前2項の和を取るのに対して、トリボナッチは前3項の和を取る。

def tribo
  ->a,b,c{ [b, c, a+b+c] }
end

これをrepeat関数に渡して結果を得よう。

tribonacci = repeat(tribo, 0, 0, 1)
tribonacci.take(20).map(&:first) # => [0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890]

そしてテトラナッチだ、テトラナッチは前4項の和を取る。

def tetra
  ->a,b,c,d{ [b, c, d, a+b+c+d] }
end

同じくrepeat関数に渡して結果を得よう。

tetranacci = repeat(tetra, 0, 0, 0, 1)
tetranacci.take(20).map(&:first) # => [0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648]

このように１つのrepeat関数を定義することで、フィボナッチ、トリボナッチ、テトラナッチの各数列を容易に導きだすことができた。

もちろん、repeat関数の応用範囲は数列の算出に留まらない。ニュートンラプソン法による平方根の算出は次のようになる。

def sqrt
  ->n,x{ (x + n/x) / 2.0 }.curry
end
sqrt3 = repeat(sqrt[3], 1.0).take(10).last # => 1.7320508075688772
sqrt5 = repeat(sqrt[5], 1.0).take(10).last # => 2.23606797749979
sqrt7 = repeat(sqrt[7], 1.0).take(10).last # => 2.6457513110645907

(追記:2011-7-1) さらに進んでEnumerable#repeatというのはどうだろうか

module Enumerable
  def repeat
    x = self
    Enumerator.new { |y| loop { y << (x = yield x) }}
  end
end

Enumerable#repeatはselfに初期値を与え、ブロックで繰り返し適用する関数を定義する。

このメソッドを使った先の演算は以下のようになる。

fibonacci = [0,1].repeat { |a, b|  [b, a+b] }
fibonacci.take(20).map(&:first) # => [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
tribonacci = [0,0,1].repeat { |a,b,c|  [b, c, a+b+c] }
tribonacci.take(20).map(&:first) # => [0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890]
tetranacci = [0,0,0,1].repeat { |a, b, c, d|  [b, c, d, a+b+c+d] }
tetranacci.take(20).map(&:first) # => [0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648]
sq5 = [5, 1.0].repeat { |n, x|  [n, (x + n/x) / 2.0] }
sq5.take(10).last.last # => 2.23606797749979

このほうがRubyっぽいかもしれない。

参考：トリボナッチ

正確には[]メソッドでcallされる手続きオブジェクト ↩

blog comments powered by Disqus

100円〜で好評発売中！
M'ELBORNE BOOKS