返り値がnilになるまでメソッドを再帰的に適用する

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

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

簡単な例

ごく簡単な例を設定する。ある文字列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", ""]