Flusso delimitato dalla coda ricorsiva di coppie di interi (Scala)?

Question

Sono molto nuovo a Scala, quindi perdona la mia ignoranza! Sto cercando di ripetere le coppie di numeri interi che sono limitati da un massimo. Ad esempio, se il massimo è 5, allora l'iterazione dovrebbe restituire:

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

Ho scelto di cercare di coda ricorsivamente restituire questo come un flusso:

@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) 
    } 

Senza l'annotazione tailrec la codice funziona:

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)) 

Ma questo non è abbastanza buono per me. Il compilatore è correttamente sottolineando che l'ultima linea di _pairs non restituisce _pairs:

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

Così, ho alcune domande:

• affrontare direttamente l'attuazione sopra, come si fa ritorno una coda in modo ricorsivo Stream [(Int, Int)]?
• fare un passo indietro, qual è il modo più efficiente di memoria per iterare su sequenze limitate di numeri interi? Non voglio eseguire un'iterazione su Range perché Range extends IndexedSeq e non voglio che la sequenza esista interamente in memoria. O mi sbaglio? Se eseguo iterazioni su Range.view, evito che venga in memoria? (!)

In Python, tutto quello che voglio è:

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)] 

Grazie per il vostro aiuto! Se pensi che io abbia bisogno di leggere riferimenti/documenti API/qualsiasi altra cosa, ti prego di dirmelo, perché sono desideroso di imparare.

Answer 1

Questo non è tail-ricorsione

Supponiamo si stavano facendo un elenco invece di un torrente: (Lasciatemi usare una funzione più semplice per rendere il mio punto)

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

Nel caso generale in questa ricorsione, dopo foo(n - 1) restituisce la funzione deve fare qualcosa con la lista che restituisce - deve concatenare un altro elemento all'inizio della lista. Quindi la funzione non può essere ricorsiva in coda, perché qualcosa deve essere fatto alla lista dopo la ricorsione.

Senza ricorsione della coda, per un valore elevato di n, si esaurisce lo spazio di stack.

L'elenco solita soluzione

La soluzione usuale sarebbe passare un ListBuffer come secondo parametro, e riempire quella.

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]()) 
} 

Quello che stai facendo è conosciuto come "tail recursion modulo cons", e questa è un'ottimizzazione eseguita automaticamente dal compilatori LISP Prolog quando vedono il modulo ricorsione in coda cons modello, dal momento che è così comune. Il compilatore di Scala non lo ottimizza automaticamente.

Streams non hanno bisogno di ricorsione in coda

Streams non hanno bisogno ricorsione in coda per evitare di rimanere a corto di spazio dello stack - questo è becuase che usano un trucco intelligente per evitare di eseguire la chiamata ricorsiva per foo al punto in cui appare nel codice. La chiamata alla funzione viene racchiusa in un thunk e solo chiamata al punto in cui si tenta effettivamente di ottenere il valore dallo stream. È attiva una sola chiamata a foo alla volta, non è mai ricorsiva.

Ho scritto una risposta precedente che spiega how the #:: operator works qui su Stackoverflow. Ecco cosa succede quando chiami la seguente funzione di flusso ricorsivo. (È ricorsiva in senso matematico, ma non fa una chiamata di funzione all'interno di una funzione chiamata il modo in cui di solito si aspetta.)

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

Si chiama foo(10), restituisce un ruscello con un elemento già calcolato e la coda è un thunk che chiamerà foo(9) la prossima volta che avrai bisogno di un elemento dallo stream. foo(9) non è stato chiamato in questo momento, ma la chiamata è associata a uno lazy val all'interno dello stream e foo(10) restituisce immediatamente. Quando finalmente hai bisogno del secondo valore nel flusso, viene chiamato foo(9) e calcola un elemento e imposta la coda di hte stream come thunk che chiamerà foo(8). foo(9) restituisce immediatamente senza chiamare foo(8). E così via ...

Questo consente di creare flussi infiniti, senza esaurire la memoria, per esempio:

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

(Fare attenzione a quali operazioni si chiama in questo flusso Se si tenta di fare un. forEach o un map, potrai riempire il vostro intero mucchio, ma usando take è un buon modo per lavorare con un prefisso arbitrario del torrente.)

una soluzione più semplice del tutto

Invece di trattare con re cursion e stream, perché non usare solo il ciclo for di Scala?

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

Questa materializza l'intera collezione in memoria, e restituisce un IndexedSeq[(Int, Int)].

Se è necessario uno stream specifico, è possibile convertire il primo intervallo in Stream.

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

Questo restituirà un Stream[(Int, Int)]. Quando accedi a un certo punto della sequenza, questo verrà materializzato in memoria e rimarrà attivo finché avrai ancora un riferimento a qualsiasi punto nel flusso prima di quell'elemento.

È possibile ottenere un utilizzo della memoria ancora migliore convertendo entrambi gli intervalli in viste.

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

che restituisce un SeqView[(Int, Int),Seq[_]] che calcola ogni elemento ogni volta che ne avete bisogno, e non memorizza i risultati precalcolate.

È inoltre possibile ottenere un iteratore (che si può attraversare solo una volta) allo stesso modo

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

che restituisce Iterator[(Int, Int)].

Answer 2

Forse un Iterator è più adatto a te?

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