Scala for Backend Engineering & Functional Programming · Lezione

Pattern dell'accumulatore

Convertire in ricorsione terminale

Pattern dell'accumulatore è una lezione Scala for Backend Engineering & Functional Programming gratuita su CoddyKit. Questa è la lezione 3 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.

Lo schema dell'accumulatore

Lo schema dell'accumulatore trasforma una funzione non ricorsiva in coda in una funzione ricorsiva in coda. Il risultato parziale viene passato in un parametro aggiuntivo (l'accumulatore) invece di essere costruito dopo il ritorno della chiamata.

L'idea fondamentale

Anziché usare n + sum(n-1) (lavoro da eseguire dopo la chiamata), si calcola il nuovo totale parziale prima della chiamata: sum(n-1, acc + n). In questo modo la chiamata ricorsiva è l'ultima azione.

Prima: somma non ricorsiva in coda

Questa versione diretta non è ricorsiva in coda: l'addizione attende il ritorno della chiamata ricorsiva.

object Main {
  def sum(n: Int): Int =
    if (n == 0) 0 else n + sum(n - 1)

  def main(args: Array[String]): Unit = {
    println(sum(50))
  }
}

Dopo: somma in coda con accumulatore

Aggiunga un parametro acc che contenga il totale corrente. Ora la chiamata ricorsiva è in posizione di coda e può essere ottimizzata.

import scala.annotation.tailrec

object Main {
  @tailrec
  def sum(n: Int, acc: Int = 0): Int =
    if (n == 0) acc else sum(n - 1, acc + n)

  def main(args: Array[String]): Unit = {
    println(sum(50))
  }
}

Fattoriale ricorsivo in coda

Applichi la stessa trasformazione al fattoriale: moltiplichi il valore nell'accumulatore prima di ricorrere.

import scala.annotation.tailrec

object Main {
  @tailrec
  def factorial(n: Int, acc: Long = 1): Long =
    if (n <= 1) acc else factorial(n - 1, acc * n)

  def main(args: Array[String]): Unit = {
    println(factorial(10))
  }
}

Nascondere l'accumulatore

Il parametro aggiuntivo è un dettaglio d'implementazione. Racchiuda la funzione ausiliaria ricorsiva in coda in una funzione pubblica pulita, così chi la utilizza non vede acc.

import scala.annotation.tailrec

object Main {
  def factorial(n: Int): Long = {
    @tailrec
    def loop(m: Int, acc: Long): Long =
      if (m <= 1) acc else loop(m - 1, acc * m)
    loop(n, 1)
  }

  def main(args: Array[String]): Unit = {
    println(factorial(6))
  }
}

Accumulo di una lista

Lo schema consente anche di costruire collezioni. Un reverse ricorsivo in coda antepone ogni testa alla lista accumulatore.

import scala.annotation.tailrec

object Main {
  def reverse[A](xs: List[A]): List[A] = {
    @tailrec
    def loop(rem: List[A], acc: List[A]): List[A] = rem match {
      case Nil    => acc
      case h :: t => loop(t, h :: acc)
    }
    loop(xs, Nil)
  }

  def main(args: Array[String]): Unit = {
    println(reverse(List(1, 2, 3, 4)))
  }
}

Ordine dell'accumulo

Si noti che anteporre elementi all'accumulatore inverte naturalmente l'ordine. Per una funzione che costruisce una lista mantenendo l'ordine, spesso si costruisce prima la lista invertita e la si inverte alla fine, oppure si utilizza una struttura efficiente per l'accodamento.

map ricorsivo in coda

Costruisca una lista risultato con un accumulatore, quindi la inverta una sola volta alla fine per ripristinare l'ordine.

import scala.annotation.tailrec

object Main {
  def mapTail[A, B](xs: List[A])(f: A => B): List[B] = {
    @tailrec
    def loop(rem: List[A], acc: List[B]): List[B] = rem match {
      case Nil    => acc.reverse
      case h :: t => loop(t, f(h) :: acc)
    }
    loop(xs, Nil)
  }

  def main(args: Array[String]): Unit = {
    println(mapTail(List(1, 2, 3))(_ * 10))
  }
}

Relazione con foldLeft

Lo schema dell'accumulatore è esattamente ciò che generalizza foldLeft: l'accumulatore viene fatto passare attraverso una collezione in modo ricorsivo e sicuro rispetto allo stack. Molte funzioni manuali che usano un accumulatore possono essere riscritte come una singola foldLeft.

@main def run(): Unit = {
  val total = List(1, 2, 3, 4).foldLeft(0)(_ + _)
  println(total)
}

Quando utilizzarlo

Si ricorra allo schema dell'accumulatore quando una funzione ricorsiva elabora una struttura lineare di grandi dimensioni e altrimenti causerebbe un overflow dello stack. Si sacrifica una forma leggermente meno intuitiva in cambio della sicurezza garantita rispetto allo stack.

Verifica rapida

Verifichi la Sua comprensione dello schema dell'accumulatore.

Riepilogo

Ha imparato lo schema dell'accumulatore:

Si passa il risultato parziale in un parametro aggiuntivo.
Lo si calcola prima della ricorsione per raggiungere la posizione di coda.
Si nasconde l'accumulatore dietro una funzione pubblica pulita.
Lo schema si generalizza in foldLeft.

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»?

Convertire in ricorsione terminale 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 3 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

← Torna a Scala for Backend Engineering & Functional Programming