Ruby：標準的な再帰パターン

Question

私が一般的にルビで使っているのは、再帰パターンです。たとえば、配列を持っていて、配列が無制限の深さの要素として含まれているとします。したがって、たとえば：

my_array = [1, [2, 3, [4, 5, [6, 7]]]] 

私は[1, 2, 3, 4, 5, 6, 7]に、配列を平らにすることができますメソッドを作成したいと思います。

私は.flattenがその仕事をしていることに気付いていますが、この問題は私が定期的に実行する再帰問題の例として意味されています。したがって、私は再利用可能な解決策を探しています。

簡潔に言えば、このような標準パターンがあると思いますが、特にエレガントなものはありません。すべてのアイデアは、あなたがCのビットを知っていればよく、

http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-flatten 

そしてのため..あなただけのドキュメントを訪問し、Cソースを取得するにはルビーの機能をクリックする必要があり、それはすべてそこにある

Answer 1

再帰はメソッドであり、言語に依存しません。あなたは、関数をもう一度呼び出すもの（再帰の場合）と、それを壊すもの（基本の場合）の2つのケースを念頭にアルゴリズムを記述します。たとえば、Rubyで再帰フラットを行うには：

class Array 
    def deep_flatten 
    flat_map do |item| 
     if item.is_a?(Array) 
     item.deep_flatten 
     else 
     [item] 
     end 
    end 
    end 
end 

[[[1]], [2, 3], [4, 5, [[6]], 7]].deep_flatten 
#=> [1, 2, 3, 4, 5, 6, 7] 

これは役に立ちますか？とにかく、有用なパターンは、配列の再結合を使用しているときは、通常flat_map（each + concat/pushの機能的な代替）が必要であるということです。

Answer 2

を高く評価しましたこの場合、Rubyの実装です

def flatten values, level=-1 
    flat = [] 
    values.each do |value| 
    if level != 0 && value.kind_of?(Array) 
     flat.concat(flatten(value, level-1)) 
    else 
     flat << value 
    end 
    end 
    flat 
end 

p flatten [1, [2, 3, [4, 5, [6, 7]]]] 
#=> [1, 2, 3, 4, 5, 6, 7] 

Answer 3

ここでは、末尾の再帰的スタイルで記述されたフラットネスの例を示します。

ruby

それはルビーは常に末尾再帰のために最適化されていないように見えますが

class Array 

    # Monkeypatching the flatten class 
    def flatten(new_arr = []) 
    self.each do |el| 
     if el.is_a?(Array) 
     el.flatten(new_arr) 
     else 
     new_arr << el 
     end 
    end 

    new_arr 
    end 
end 

p flatten [1, [2, 3, [4, 5, [6, 7]]]] 
#=> [1, 2, 3, 4, 5, 6, 7] 

： Does ruby perform tail call optimization?