Tail-rekursive begrenzte Strom von Paaren von ganzen Zahlen (Scala)?

Question

Ich bin sehr neu in Scala, also vergib meine Unwissenheit! Ich versuche, Paare von Ganzzahlen zu durchlaufen, die durch ein Maximum begrenzt sind. Wenn beispielsweise die maximale 5 ist, dann sollte die Iteration zurück:

(0, 0), (0, 1), ..., (0, 5), (1, 0), ..., (5, 5) 

habe ich gewählt, um zu versuchen und Schwanz-rekursiv geben diese als Stream:

@tailrec 
    def _pairs(i: Int, j: Int, maximum: Int): Stream[(Int, Int)] = { 
     if (i == maximum && j == maximum) Stream.empty 
     else if (j == maximum) (i, j) #:: _pairs(i + 1, 0, maximum) 
     else (i, j) #:: _pairs(i, j + 1, maximum) 
    } 

Ohne die tailrec Anmerkung der Code funktioniert:

scala> _pairs(0, 0, 5).take(11) 
res16: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?) 

scala> _pairs(0, 0, 5).take(11).toList 
res17: List[(Int, Int)] = List((0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (1,0), (1,1), (1,2), (1,3), (1,4)) 

Aber das ist nicht gut genug für mich. Der Compiler wird unter Hinweis darauf, richtig, dass die letzte Zeile von _pairs ist _pairs nicht zurückkehren:

could not optimize @tailrec annotated method _pairs: it contains a recursive call not in tail position 
    else (i, j) #:: _pairs(i, j + 1, maximum) 
       ^

Also, ich einige Fragen:

• direkt die Umsetzung über Adressierung, wie funktioniert ein Schwanz-rekursiv Rückkehr Stream [(Int, Int)]?
• einen Schritt zurück, was ist die speichereffizienteste Möglichkeit, über begrenzte Folgen von ganzen Zahlen zu iterieren? Ich möchte nicht über Range iterieren, weil Range extends IndexedSeq, und ich möchte nicht, dass die Sequenz vollständig im Speicher vorhanden ist. Oder liege ich falsch? Wenn ich über Range.view iteriere, vermeide ich, dass es in den Speicher kommt? (!)

In Python, alles was ich will:

In [6]: def _pairs(maximum): 
    ...:  for i in xrange(maximum+1): 
    ...:   for j in xrange(maximum+1): 
    ...:    yield (i, j) 
    ...:    

In [7]: p = _pairs(5) 

In [8]: [p.next() for i in xrange(11)] 
Out[8]: 
[(0, 0), 
(0, 1), 
(0, 2), 
(0, 3), 
(0, 4), 
(0, 5), 
(1, 0), 
(1, 1), 
(1, 2), 
(1, 3), 
(1, 4)] 

Vielen Dank für Ihre Hilfe! Wenn Sie denken, dass ich Referenzen/API-Dokumente/irgendetwas anderes lesen muss, sagen Sie mir bitte, weil ich daran interessiert bin zu lernen.

Answer 1

Dies ist nicht Schwanz-Rekursion

Lassen Sie uns annehmen, Sie anstelle eines Baches eine Liste machten: (lassen Sie mich eine einfachere Funktion verwenden, um meinen Punkt zu machen)

def foo(n: Int): List[Int] = 
    if (n == 0) 
    0 :: Nil 
    else 
    n :: foo(n - 1) 

Im allgemeinen Fall in dieser Rekursion, nachdem foo(n - 1) zurückgibt die Funktion hat etwas mit der Liste zu tun, die es zurückgibt - es muss ein anderes Element an den Anfang der Liste verketten. Die Funktion kann also nicht tail rekursiv sein, da nach der Rekursion etwas an der Liste ausgeführt werden muss.

Ohne Tail-Rekursion, für einen großen Wert von n, haben Sie nicht mehr genügend Speicherplatz im Stack.

Die übliche Lösung Liste

Die übliche Lösung wäre ein ListBuffer als zweiter Parameter übergeben werden, und dass füllen.

def foo(n: Int) = { 
    def fooInternal(n: Int, list: ListBuffer[Int]) = { 
    if (n == 0) 
     list.toList 
    else { 
     list += n 
     fooInternal(n - 1, list) 
    } 
    } 
    fooInternal(n, new ListBuffer[Int]()) 
} 

Was Sie tun, als „tail recursion modulo cons“ bekannt ist, und dies ist eine Optimierung automatisch von LISP Prolog-Compiler ausgeführt wird, wenn sie die Endrekursion Modulo-cons Muster zu sehen, da es so üblich ist. Der Scala-Compiler optimiert dies nicht automatisch.

Streams nicht brauchen Endrekursion

Streams nicht Endrekursion vermeiden müssen genügend Stapelspeicherplatz ausgeführt wird - das ist becuase sie einen cleveren Trick, um nicht den rekursiven Aufruf zu foo bei der Ausführung Zeigen Sie, wo es im Code erscheint. Der Funktionsaufruf wird in einen Thunk gehüllt und nur an dem Punkt aufgerufen, an dem Sie tatsächlich versuchen, den Wert aus dem Stream zu erhalten. Nur ein Anruf zu foo ist zu einer Zeit aktiv - es ist nie rekursiv.

Ich habe eine vorherige Antwort geschrieben, die how the #:: operator works hier auf Stackoverflow erklärt. Folgendes geschieht, wenn Sie die folgende rekursive Stream-Funktion aufrufen. (Es ist rekursiv im mathematischen Sinn, aber es ist kein Funktionsaufruf innerhalb einer Funktion, die Art und Weise rufen Sie in der Regel erwarten.)

def foo(n: Int): Stream[Int] = 
    if (n == 0) 
    0 #:: Nil 
    else 
    n #:: foo(n - 1) 

Sie foo(10) aufrufen, gibt es einen Stream mit einem Element bereits berechnet , und der Schwanz ist ein Thunk, der foo(9) das nächste Mal aufrufen wird, wenn Sie ein Element aus dem Stream benötigen. foo(9) wird jetzt nicht aufgerufen - vielmehr ist der Anruf innerhalb des Streams an eine lazy val gebunden, und foo(10) kehrt sofort zurück. Wenn Sie schließlich den zweiten Wert im Stream benötigen, wird foo(9) aufgerufen, und es berechnet ein Element und legt das Ende des HTT-Streams als Thunk fest, der foo(8) aufruft. foo(9) kehrt sofort ohne Aufruf foo(8) zurück. Und so weiter ...

Dies ermöglicht Ihnen unendliche Ströme zu erzeugen, ohne aus dem Speicher ausgeführt wird, zum Beispiel:

def countUp(start: Int): Stream[Int] = start #::countUp(start + 1) 

(Sei vorsichtig, was Operationen, die Sie auf diesem Stream aufrufen Wenn Sie versuchen, eine zu tun. forEach oder ein map, werden füllen Sie Ihren ganzen Haufen, aber take ist eine gute Art und Weise mit einem beliebigen Präfix des Stroms zu arbeiten.)

eine einfachere Lösung insgesamt

Statt mit re Umgang Kursion und Ströme, warum nicht einfach Scalas for Schleife verwenden?

def pairs(maximum:Int) = 
    for (i <- 0 to maximum; 
     j <- 0 to maximum) 
    yield (i, j) 

Diese materialisiert die gesamte Sammlung im Speicher und gibt ein IndexedSeq[(Int, Int)]. Wenn Sie speziell einen Stream benötigen, können Sie den ersten Bereich in eine Stream konvertieren.

def pairs(maximum:Int) = 
    for (i <- 0 to maximum toStream; 
     j <- 0 to maximum) 
    yield (i, j) 

Dies wird eine Stream[(Int, Int)] zurückgeben. Wenn Sie auf einen bestimmten Punkt in der Sequenz zugreifen, wird dieser in den Speicher umgewandelt und verbleibt so lange, wie Sie noch einen Verweis auf einen Punkt im Stream vor diesem Element haben.

Sie können eine noch bessere Speichernutzung erzielen, indem Sie beide Bereiche in Ansichten konvertieren.

def pairs(maximum:Int) = 
    for (i <- 0 to maximum view; 
     j <- 0 to maximum view) 
    yield (i, j) 

dass ein SeqView[(Int, Int),Seq[_]] zurückgibt, die jedes Element jedes Mal, wenn Sie es brauchen berechnet und speichert keine vorberechneten Ergebnisse.

Sie können auch einen Iterator bekommen (die man nur einmal überqueren können) auf die gleiche Weise

def pairs(maximum:Int) = 
    for (i <- 0 to maximum iterator; 
     j <- 0 to maximum iterator) 
    yield (i, j) 

Das Iterator[(Int, Int)] zurückgibt.

Answer 2

Vielleicht ist ein Iterator besser für Sie geeignet?

class PairIterator (max: Int) extends Iterator [(Int, Int)] { 
    var count = -1 
    def hasNext = count <= max * max 
    def next() = { count += 1; (count/max, count % max) } 
} 

val pi = new PairIterator (5) 
pi.take (7).toList