Ackumulatormönstret
Gör om till svansrekursion.
Ackumulatormönstret är en gratis lektion i Scala för backendutveckling och funktionell programmering på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Scala för backendutveckling och funktionell programmering, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Scala för backendutveckling och funktionell programmering innehåller totalt 4 lektioner.
Ackumulatormönstret
Ackumulatormönstret omvandlar en icke-svansrekursiv funktion till en svansrekursiv. Ni för med det partiella resultatet i en extra parameter (en ackumulator) i stället för att bygga upp det efter att anropet returnerat.
Grundidén
I stället för n + sum(n-1) (arbete efter anropet) beräknar Ni den nya delsumman före anropet: sum(n-1, acc + n). Nu är det rekursiva anropet den sista åtgärden.
Före: icke-svansrekursiv summa
Den här direkta versionen är inte svansrekursiv: additionen väntar på det rekursiva anropet.
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))
}
}Efter: svansrekursiv summa med ackumulator
Lägg till en parameter acc som innehåller den löpande summan. Det rekursiva anropet befinner sig nu i svansposition och kan optimeras.
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))
}
}Svansrekursiv fakultet
Tillämpa samma omvandling på fakultet: multiplicera in värdet i ackumulatorn före rekursionen.
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))
}
}Dölja ackumulatorn
Den extra parametern är en implementeringsdetalj. Omslut den svansrekursiva hjälpfunktionen i en ren offentlig funktion så att anroparna inte ser 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))
}
}Ackumulera en lista
Mönstret kan också bygga samlingar. En svansrekursiv reverse lägger varje huvud först i ackumulatorlistan.
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)))
}
}Ackumuleringsordning
Observera att en insättning först i ackumulatorn naturligt vänder ordningen. För en listbyggande funktion som bevarar ordningen bygger Ni ofta listan baklänges och vänder den i slutet, eller använder en effektiv struktur för tillägg.
Svansrekursiv map
Bygg en resultatlista med en ackumulator och vänd den sedan en gång i slutet för att återställa ordningen.
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))
}
}Relationen till foldLeft
Ackumulatormönstret är exakt det som foldLeft generaliserar: det för en ackumulator genom en samling på ett svansrekursivt sätt. Många manuella ackumulatorfunktioner kan skrivas om som ett enda foldLeft.
@main def run(): Unit = {
val total = List(1, 2, 3, 4).foldLeft(0)(_ + _)
println(total)
}När ska Ni använda det
Använd ackumulatormönstret när en rekursiv funktion bearbetar en stor linjär struktur och annars skulle orsaka stackspill. Ni byter då en något mindre uppenbar struktur mot garanterad stack-säkerhet.
Snabbtest
Testa om Ni behärskar ackumulatormönstret.
Sammanfattning
Ni har lärt Er ackumulatormönstret:
- För det partiella resultatet i en extra parameter.
- Beräkna det före rekursionen för att nå svanspositionen.
- Dölj ackumulatorn bakom en ren offentlig funktion.
- Det generaliseras av
foldLeft.
Lär dig Scala med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 39
- Lektioner
- 143
Vanliga frågor
Är lektionen ”Ackumulatormönstret” gratis?
Ja – hela texten till ”Ackumulatormönstret” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Scala för backendutveckling och funktionell programmering, kan Ni uppgradera till CoddyKit PRO. Kursen i Scala för backendutveckling och funktionell programmering innehåller totalt 4 lektioner.
Vad lär jag mig i ”Ackumulatormönstret”?
Gör om till svansrekursion. Ni övar på Scala för backendutveckling och funktionell programmering med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Scala för backendutveckling och funktionell programmering?
Du behöver inga förkunskaper. Utbildningen i Scala för backendutveckling och funktionell programmering på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.
Hur lång tid tar lektionen ”Ackumulatormönstret”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Scala för backendutveckling och funktionell programmering-lektionen?
Ja. Varje Scala för backendutveckling och funktionell programmering-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Grunderna i rekursion
- Annotationen tailrec
- Ackumulatormönstret
- Trampolining