オブジェクトを再帰的に辿る

グラフのノードを再帰的に辿るような繰り返し処理をいい感じに書くにはどうすればよいか。

簡単な例

ごく簡単な例を設定する。ある文字列sについて、s[1..-1]を繰り返し適用すると最後にはnilが返る。

"abcde"[1..-1] #=> "bcde"
"bcde"[1..-1]  #=> "cde"
"cde"[1..-1]   #=> "de"
"de"[1..-1]    #=> "e"
"e"[1..-1]     #=> ""
""[1..-1]      #=> nil

普通に書くとこんな感じだろう。

s = "abcde"
while _s = s[1..-1]
	puts _s
	s = _s
end

~~ブロック~~制御構造が嫌いならこんな感じか。

s = "abcde"
_s = nil
puts s = _s while _s = s[1..-1]

関数にする

任意の処理を再帰的に行う関数を作る。その1。

def recursive(obj)
	c = obj
	n = nil
	c = n while n = yield(c)
end

次のように使う。ブロックの最後の値に対して同じ処理を繰り返し行う。最終的にnilになるような処理じゃないと無限ループに陥るので注意。

recursive("abcde") do |s|
	_s = s[1..-1]
	puts _s
	_s
end

Enumeratorを使う

Enumeratorを使うパターン。

def recursive(obj)
	Enumerator.new do |y|
		c = obj
		n = nil
		y << c = n while n = yield(c)
	end
end

次のように使う。

s = "abcde"
recursive(s){|_s| _s[1..-1]}.to_a
=> ["bcde", "cde", "de", "e", ""]

モジュールにする

Moduleで定義してインスタンスメソッドとして使う。

module Recursive
	def recursive
		Enumerator.new do |y|
			c = self
			n = nil
			y << c = n while n = yield(c)
		end
	end
end

次のように使う。

class MyString < String
	include Recursive
end

s = MyString.new('abcde')
s.recursive{|_s| _s[1..-1]}.to_a
=> ["bcde", "cde", "de", "e", ""]

繋げて書く

obj.recursive.method みたいな書き方をしたい場合。

module Recursive
	def recursive
		Recursive::Deligator.new self
	end
end

class Recursive::Deligator
	def initialize(obj)
		@obj = obj
	end
	def method_missing(name, *args, &block)
		Enumerator.new do |y|
			c = @obj
			n = nil
			y << c = n while n = c.send(name, *args, &block)
		end
	end
end

次のように使う。

s = MyString.new("abcde")

s.recursive[1..-1].to_a
=> ["bcde", "cde", "de", "e", ""]

s.recursive.slice(1..-1).to_a
=> ["bcde", "cde", "de", "e", ""]

どちらの記法も使えるようにする

メソッドを続ける書き方はシンプルだが、直後のメソッドが「自分と同じクラスのインスタンスまたはnil」を返すメソッドでなければならない。ブロックを与える書き方とメソッドを続ける書き方の両方ができるような多態な関数にしておいた方が便利だろう。

module Recursive
	def recursive
		if block_given?
			Enumerator.new do |y|
				c = self
				n = nil
				y << c = n while n = yield(c)
			end
		else
			Recursive::Deligator.new self
		end
	end
end

これで、どちらの書き方もできるようになる。

s.recursive[1..-1].to_a
=> ["bcde", "cde", "de", "e", ""]

s.recursive{|_s| _s[1..-1]}.to_a
=> ["bcde", "cde", "de", "e", ""]