Scala för backendutveckling och funktionell programmering · Lektion

Ackumulatormönster

För vidare tillstånd genom rekursionen.

Lektion 2 av 413 steg

Ackumulatormönster är en gratis lektion i Scala för backendutveckling och funktionell programmering på CoddyKit. Detta är lektion 2 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.

Varför ackumulatorer

Vanlig rekursion bygger upp resultatet på vägen tillbaka genom anropsstacken, efter att det rekursiva anropet har returnerat.

En ackumulator tar i stället med sig ett löpande resultat ned till varje anrop, så att svaret är klart när basfallet nås.

Denna lilla förändring möjliggör svansrekursion och konstant stackanvändning.

Hjälpfunktionen

Ackumulatormönstret använder en inre hjälpfunktion som tar en extra parameter: resultatet hittills.

Den yttre funktionen startar den bara med ett startvärde, ofta 0 eller en tom lista.

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

Köra ackumulatorn

Här summerar hela programmet en lista med hjälp av en ackumulator.

Observera att basfallet returnerar acc direkt, inte 0. Totalen har byggts upp medan vi gick ned genom listan.

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

Jämföra de två formerna

I vanlig rekursion väntar kombineringssteget (h + ...) på det inre anropet.

I ackumulatorversionen sker kombinationen före anropet, och anropet är det allra sista funktionen gör.

Det är egenskapen att anropet sker sist som gör den svansrekursiv.

// Plain: combine after the call
case h :: t => h + sum(t)

// Accumulator: combine before the call
case h :: t => loop(t, acc + h)

Svansrekursion

Ett svansrekursivt anrop är ett anrop där det rekursiva anropet är funktionens sista åtgärd och inget återstår att göra efteråt.

Scala kan optimera detta till en loop som återanvänder en enda stackram, så stacken svämmar aldrig över, oavsett hur djupt anropen går.

import scala.annotation.tailrec

@tailrec
def countDown(n: Int): Unit =
  if (n < 0) ()
  else { println(n); countDown(n - 1) }

Annoteringen @tailrec

Genom att lägga till @tailrec ber ni kompilatorn verifiera att funktionen verkligen är svansrekursiv.

Om den inte är det misslyckas kompileringen med ett tydligt fel. Det omvandlar en dold prestandafälla till en garanti vid byggtillfället.

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

Bygga en lista

Ackumulatorer behöver inte innehålla tal. De kan även bygga samlingar.

Denna reverse-funktion lägger varje huvud först i ackumulatorn, vilket naturligt vänder ordningen. Att lägga till först med :: går snabbt, så detta är effektivt.

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 i praktiken

Ackumulatorn börjar tom och växer medan vi förbrukar indata.

Eftersom varje huvud läggs längst fram i acc hamnar det första elementet sist, vilket ger en omvänd lista med konstant stackkostnad.

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)

Flera ackumulatorer

En hjälpfunktion kan bära flera ackumulatorer samtidigt.

Här följer vi en löpande produkt och ett antal i samma loop och returnerar båda som en tupel.

Var och en för sitt uppdaterade värde vidare till nästa anrop.

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

Välja startvärdet

Den initiala ackumulatorn måste vara identitetselementet för er operation.

För addition använder ni 0, för multiplikation 1, för listbyggande Nil och för strängsammanslagning den tomma strängen.

Ett felaktigt startvärde ger i tysthet fel svar.

// addition  -> seed 0
// product   -> seed 1
// list      -> seed Nil
// string    -> seed ""

Resultatens ordning

Ackumulatorrekursion bearbetar element från vänster till höger, men en ackumulator som lägger till först vänder på dem.

Om ni behöver bevara ordningen när ni bygger en lista kan ni antingen vända den i slutet eller lägga till sist, även om det senare är långsammare. Lägg till först och vänd sedan är det vanliga idiomet.

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

Snabbtest

Välj det korrekta påståendet om ackumulatorrekursion.

Besvara frågan i den interaktiva lektionen

Sammanfattning

En ackumulator för det löpande resultatet vidare genom de rekursiva anropen, så att basfallet kan returnera det direkt.

Detta placerar det rekursiva anropet i svansposition och möjliggör både Scalas optimering av svansanrop och säkerhetskontrollen med @tailrec.

Initiera ackumulatorn med operationens identitetselement och vänd resultatet i slutet när ordningen är viktig.

Gratis att börja

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

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Ackumulatormönster” gratis?

Ja – hela texten till ”Ackumulatormönster” 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önster”?

För vidare tillstånd genom rekursionen. 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 2 av 4.

Hur lång tid tar lektionen ”Ackumulatormönster”?

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

← Tillbaka till Scala för backendutveckling och funktionell programmering