Ruby: Standard Rekursionsmuster

Question

Eines der Dinge, an denen ich mich in Ruby häufig festbeiße, sind Rekursionsmuster. Nehmen wir zum Beispiel an, ich habe ein Array, das möglicherweise Arrays als Elemente in unbegrenzter Tiefe enthalten kann. Also zum Beispiel:

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

Ich möchte eine Methode erstellen, die das Array in [1, 2, 3, 4, 5, 6, 7] aufgeflacht.

Ich bin mir bewusst, dass .flatten die Arbeit erledigen würde, aber dieses Problem ist als Beispiel für die Rekursionsprobleme gedacht, mit denen ich regelmäßig konfrontiert werde - und ich versuche daher, eine wiederverwendbare Lösung zu finden.

Kurz gesagt - Ich vermute, es gibt ein Standardmuster für diese Art von Dingen, aber mir fällt nichts besonders Elegantens ein. Jegliche Ideen sind willkommen

Answer 1

Rekursion ist eine Methode, die nicht von der Sprache abhängt. Sie schreiben den Algorithmus mit zwei Arten von Fällen im Kopf: diejenigen, die die Funktion erneut aufrufen (Rekursionsfälle) und diejenigen, die sie beenden (Basisklassen). Zum Beispiel, um ein rekursives Flachlegen in Ruby zu machen:

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]

Hilft das? Jedenfalls, ein nützliches Muster, das hier gezeigt wird, ist, dass wenn Sie Rekursion auf Arrays verwenden, brauchen Sie in der Regel flat_map (die funktionale Alternative zu each + concat/push).

Answer 2

Gut, wenn Sie ein wenig C kennen, müssen Sie nur die Dokumentation besuchen und auf die Ruby-Funktion klicken, um den C-Quellcode zu erhalten, und alles ist da.

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

Und für diesen Fall, hier ist eine Ruby-Implementierung

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

Hier ist ein Beispiel für eine Flatten-Funktion, die in einem schwanzrekursiven Stil geschrieben ist.

class Array

  # Monkeypatching der Flatten-Klasse
  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

Auch wenn es so aussieht, als wäre Ruby nicht immer optimiert für Schwanzrekursionen: Führt Ruby Tail Call Optimierungen durch?