C'è un modo elegante per piegarsi su un crescente scala.collections.mutable.Queue?

Question

Ho una funzione ricorsiva che sto cercando di rendere @tailrec facendo in modo che la parte interna ricorsiva (countR3) aggiunga elementi a una coda (agenda è un scala.collections.mutable.Queue). La mia idea è quella di far passare la parte esterna della funzione sull'agenda e riassumere i risultati.

NOTA: Questo era un problema di compiti a casa, quindi non voglio postare l'intero codice; tuttavia, l'implementazione della coda ricorsiva era non parte dei compiti.

Ecco la parte del codice relativo alla mia domanda:

import scala.collection.mutable.Queue 

val agenda: Queue[Tuple2[Int, List[Int]]] = Queue() 

@tailrec 
def countR3(y: Int, x: List[Int]): Int = { 
    if (y == 0) 1 
    else if (x.isEmpty) 0 
    else if … 
    else { 
    agenda.enqueue((y - x.head, x)) 
    countR3(y, x.tail) 
    } 
} 
⋮ 
agenda.enqueue((4, List(1, 2))) 
val count = agenda.foldLeft(0) { 
    (count, pair) => { 
    val mohr = countR3(pair._1, pair._2) 
    println("count=" + count + " countR3=" + mohr) 
    count + mohr 
    } 
} 
println(agenda.mkString(" + ")) 
count 

Questo quasi sembra funzionare ... Il problema è che non un'iterazione su tutti gli elementi aggiunti all'ordine del giorno, ancora processa alcuni di di loro. Si può vedere questo nell'output di seguito: [. Dei sei punti all'ordine del giorno finale, solo i primi tre sono stati elaborati]

count=0 countR3=0 
count=0 countR3=0 
count=0 countR3=0 
(4,List(1, 2)) + (3,List(1, 2)) + (2,List(2)) + (2,List(1, 2)) + (1,List(2)) + (0,List(2)) 

Sono generalmente ben consapevoli dei pericoli di mutanti una raccolta mentre stai iterando su di essa, per esempio, su Java. Ma una coda è una specie di cavallo di un colore diverso. Certo, capisco che potrei semplicemente scrivere un ciclo imperativo, in questo modo:

var count = 0 
while (!agenda.isEmpty) { 
    val pair = agenda.dequeue() 
    count += countR3(pair._1, pair._2) 
} 

Questo funziona perfettamente bene, ma essendo questo Scala, sto esplorando per vedere se c'è un funzionalmente elegante modo più.

Qualche suggerimento?

Answer 1

Anche se probabilmente non del tutto idiomatica, si potrebbe provare questo:

Stream.continually({ if (agenda.isEmpty) None else Some(agenda.dequeue()) }). 
    takeWhile(_.isDefined).flatten. 
    map({ case (x, y) => countR3(x, y) }). 
    toList.sum 

• Il Stream.continually({ if (agenda.isEmpty) None else Some(agenda.dequeue()) }) ti dà un flusso infinito di elementi della coda avvolta in Option[Tuple2[Int, List[Int]]].
• Quindi, takeWhile(_.isDefined) interrompe la sequenza non appena viene rilevato il primo elemento None, ad esempio quando la coda è esaurita.
• Poiché la chiamata precedente restituisce ancora una sequenza di Option s, è necessario scartarli con flatten.
• map({ case (x, y) => countR3(x, y) }) applica fondamentalmente la funzione a ciascun elemento.
• E infine, toList impone la valutazione di uno stream (è quello con cui stavamo lavorando) e quindi sum calcola la somma degli elementi della lista.

Credo che il problema con agenda.foldLeft (che elabora solo 'alcuni' oggetti accodate) è Direi che ci vuole una (probabilmente immutabile) elenco degli elementi attualmente accodate, e, pertanto, non è influenzato da oggetti che sono stati aggiunti durante il calcolo.