Pattern dell'accumulatore
Trasporti lo stato attraverso la ricorsione.
Pattern dell'accumulatore è una lezione Scala for Backend Engineering & Functional Programming gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Scala for Backend Engineering & Functional Programming, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Scala for Backend Engineering & Functional Programming include 4 lezioni in totale.
Perché usare gli accumulatori
La ricorsione semplice costruisce il risultato durante la risalita dello stack delle chiamate, dopo la restituzione della chiamata ricorsiva.
Un accumulatore porta invece un risultato parziale in ogni chiamata, così la risposta è pronta quando si raggiunge il caso base.
Questo piccolo cambiamento permette di usare la ricorsione terminale e un utilizzo costante dello stack.
La funzione ausiliaria
Il modello dell'accumulatore usa una funzione ausiliaria interna che accetta un parametro aggiuntivo: il risultato calcolato finora.
La funzione esterna si limita ad avviarla con un valore iniziale, spesso 0 o una lista vuota.
def sum(xs: List[Int]): Int = {
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}Eseguire l'accumulatore
Qui il programma completo somma una lista usando un accumulatore.
Noti che il caso base restituisce direttamente acc, non 0. Il totale è stato costruito mentre si percorreva la lista verso il basso.
def sum(xs: List[Int]): Int = {
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}
@main def run(): Unit =
println(sum(List(1, 2, 3, 4))) // 10Confrontare le due strutture
Nella ricorsione semplice, il passaggio di combinazione (h + ...) attende la chiamata interna.
Nella versione con accumulatore, la combinazione avviene prima della chiamata, che è l'ultima operazione eseguita dalla funzione.
È proprio questa proprietà dell'ultima chiamata a rendere la funzione ricorsiva terminale.
// Plain: combine after the call
case h :: t => h + sum(t)
// Accumulator: combine before the call
case h :: t => loop(t, acc + h)Ricorsione terminale
Una chiamata ricorsiva terminale è una chiamata in cui la chiamata ricorsiva costituisce l'ultima operazione della funzione, senza altre operazioni successive.
Scala può ottimizzarla trasformandola in un ciclo e riutilizzando un solo frame dello stack, così lo stack non va mai in overflow, indipendentemente dalla profondità.
import scala.annotation.tailrec
@tailrec
def countDown(n: Int): Unit =
if (n < 0) ()
else { println(n); countDown(n - 1) }L'annotazione @tailrec
L'aggiunta di @tailrec chiede al compilatore di verificare che la funzione sia davvero ricorsiva terminale.
In caso contrario, la compilazione fallisce con un errore chiaro. In questo modo un problema di prestazioni potenzialmente silenzioso diventa una garanzia verificata in fase di compilazione.
import scala.annotation.tailrec
def sum(xs: List[Int]): Int = {
@tailrec
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}
@main def run(): Unit = println(sum((1 to 100000).toList))Accumulatione di una lista
Gli accumulatori non devono contenere necessariamente numeri. Possono anche costruire raccolte.
Questa funzione reverse antepone ogni testa all'accumulatore, invertendo naturalmente l'ordine. L'inserimento in testa con :: è rapido, quindi questa soluzione è efficiente.
def reverse[A](xs: List[A]): List[A] = {
def loop(rest: List[A], acc: List[A]): List[A] = rest match {
case Nil => acc
case h :: t => loop(t, h :: acc)
}
loop(xs, Nil)
}Reverse in azione
L'accumulatore parte vuoto e cresce man mano che consumiamo l'input.
Poiché ogni testa viene inserita davanti ad acc, il primo elemento finisce per ultimo, producendo una lista invertita con un costo costante in termini di stack.
def reverse[A](xs: List[A]): List[A] = {
def loop(rest: List[A], acc: List[A]): List[A] = rest match {
case Nil => acc
case h :: t => loop(t, h :: acc)
}
loop(xs, Nil)
}
@main def run(): Unit =
println(reverse(List(1, 2, 3))) // List(3, 2, 1)Più accumulatori
Una funzione ausiliaria può gestire contemporaneamente diversi accumulatori.
Qui teniamo traccia del prodotto parziale e del conteggio nello stesso ciclo, restituendoli entrambi come tupla.
Ognuno trasmette il proprio valore aggiornato alla chiamata successiva.
def stats(xs: List[Int]): (Int, Int) = {
def loop(rest: List[Int], prod: Int, count: Int): (Int, Int) =
rest match {
case Nil => (prod, count)
case h :: t => loop(t, prod * h, count + 1)
}
loop(xs, 1, 0)
}Scegliere il valore iniziale
L'accumulatore iniziale deve essere l'elemento neutro dell'operazione.
Per l'addizione usi 0, per la moltiplicazione 1, per la costruzione di liste Nil e per la concatenazione di stringhe la stringa vuota.
Un valore iniziale errato produce silenziosamente risultati sbagliati.
// addition -> seed 0
// product -> seed 1
// list -> seed Nil
// string -> seed ""Ordine dei risultati
La ricorsione con accumulatore elabora gli elementi da sinistra a destra, ma un accumulatore basato sull'inserimento in testa li inverte.
Se deve preservare l'ordine durante la costruzione di una lista, può invertirla alla fine oppure aggiungere gli elementi in coda, anche se quest'ultima operazione è più lenta. Inserire in testa e poi invertire è l'idioma consueto.
def mapInc(xs: List[Int]): List[Int] = {
def loop(rest: List[Int], acc: List[Int]): List[Int] = rest match {
case Nil => acc.reverse
case h :: t => loop(t, (h + 1) :: acc)
}
loop(xs, Nil)
}Verifica rapida
Scelga l'affermazione corretta sulla ricorsione con accumulatore.
Riepilogo
Un accumulatore trasmette il risultato parziale attraverso le chiamate ricorsive, così il caso base può restituirlo direttamente.
In questo modo la chiamata ricorsiva si trova in posizione terminale, abilitando l'ottimizzazione delle chiamate terminali di Scala e il controllo di sicurezza di @tailrec.
Inizializzi l'accumulatore con l'elemento neutro dell'operazione e, quando l'ordine è importante, inverta il risultato alla fine.
Domande Frequenti
La lezione «Pattern dell'accumulatore» è gratuita?
Sì — il testo completo di «Pattern dell'accumulatore» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Scala for Backend Engineering & Functional Programming, passa a CoddyKit PRO. Il corso Scala for Backend Engineering & Functional Programming include 4 lezioni in totale.
Cosa imparerò in «Pattern dell'accumulatore»?
Trasporti lo stato attraverso la ricorsione. Eserciti Scala for Backend Engineering & Functional Programming con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Scala for Backend Engineering & Functional Programming?
Non è richiesta alcuna esperienza precedente. Scala for Backend Engineering & Functional Programming su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Pattern dell'accumulatore»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Scala for Backend Engineering & Functional Programming?
Sì. Ogni lezione Scala for Backend Engineering & Functional Programming include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Pensare in modo ricorsivo
- Pattern dell'accumulatore
- foldLeft e foldRight
- reduce e aggregate