Ruby: schemi di ricorsione standard

Question

Una delle cose che di solito vengo catturato in ruby ​​sono i pattern di ricorsione. Ad esempio, supponiamo di avere un array e che possa contenere array come elementi a una profondità illimitata. Così, per esempio:

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

mi piacerebbe creare un metodo che può appiattire l'array in [1, 2, 3, 4, 5, 6, 7].

Sono a conoscenza del fatto che lo .flatten farebbe il lavoro, ma questo problema è da intendersi come un esempio di problemi di ricorsività a cui mi imbatto regolarmente - e come tale sto cercando di trovare una soluzione più riutilizzabile.

In breve, immagino ci sia un modello standard per questo genere di cose, ma non riesco a trovare nulla di particolarmente elegante. Tutte le idee apprezzato

Answer 1

ricorsione è un metodo, non dipende dalla lingua. Si scrive l'algoritmo con due tipi di casi in mente: quelli che chiamano di nuovo la funzione (casi di ricorsione) e quelli che lo infrangono (casi base). Ad esempio, per eseguire un appiattimento ricorsivo in 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] 

Questo aiuto? in ogni caso, uno schema utile mostrato qui è che quando si utilizza la recusione su array, di solito è necessario flat_map (l'alternativa funzionale a each + concat/push).

Answer 2

Beh, se si conosce un po 'di C, è sufficiente visitare la documentazione e fare clic sulla funzione di rubino per ottenere il sorgente C ed è tutto lì ..

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

E per questo caso, ecco un'implementazione rubino

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

Ecco un esempio di un appiattimento che è scritto in uno stile ricorsivo della coda.

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] 

ruby

Anche se sembra rubino non è sempre ottimizzato per la ricorsione in coda: Does ruby perform tail call optimization?