Scala for backendutvikling og funksjonell programmering · leksjon

Akkumulatormønsteret

Gjør om til halerekursjon

Leksjon 3 av 413 trinn

Akkumulatormønsteret er en gratis leksjon i Scala for backendutvikling og funksjonell programmering på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Scala for backendutvikling og funksjonell programmering, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Scala for backendutvikling og funksjonell programmering inneholder totalt 4 leksjoner.

Akkumulatormønsteret

Akkumulatormønsteret gjør en funksjon som ikke er halerekursiv, om til en halerekursiv funksjon. De fører delresultatet i en ekstra parameter ( akkumulatoren ) i stedet for å bygge det opp etter at kallet returnerer.

Grunntanken

I stedet for n + sum(n-1) (arbeid etter kallet) beregner De den nye delsummen før kallet: sum(n-1, acc + n). Nå er det rekursive kallet den siste handlingen.

Før: Sum som ikke er halerekursiv

Denne direkte versjonen er ikke halerekursiv: Addisjonen venter på det rekursive kallet.

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

Etter: Halerekursiv sum med akkumulator

Legg til en parameter acc som inneholder den løpende summen. Det rekursive kallet står nå i haleposisjon og kan optimaliseres.

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

Halerekursivt fakultet

Bruk den samme transformasjonen på fakultet: Multipliser inn i akkumulatoren før De kaller funksjonen rekursivt.

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

Skjule akkumulatoren

Den ekstra parameteren er en implementasjonsdetalj. Pakk den halerekursive hjelpefunksjonen inn i en ryddig offentlig funksjon, slik at kallere ikke 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))
  }
}

Akkumulering av en liste

Mønsteret kan også bygge samlinger. En halerekursiv reversering legger hvert hode først i akkumulatorlisten.

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

Rekkefølgen ved akkumulering

Merk at det å legge elementer først i akkumulatoren naturlig reverserer rekkefølgen. For en listebyggingsfunksjon som bevarer rekkefølgen, bygger De ofte listen reversert og reverserer den til slutt, eller bruker en effektiv struktur for å legge til elementer.

Halerekursiv map

Bygg en resultatliste med en akkumulator, og reverser den én gang til slutt for å gjenopprette rekkefølgen.

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

Forholdet til foldLeft

Akkumulatormønsteret er nøyaktig det foldLeft generaliserer: Det fører en akkumulator gjennom en samling på en halerekursiv måte. Mange manuelle akkumulatorfunksjoner kan skrives om til ett enkelt foldLeft.

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

Når bør De bruke det

Bruk akkumulatormønsteret når en rekursiv funksjon behandler en stor lineær struktur og ellers ville tømt stakken. Det gir en litt mindre åpenbar struktur, men garantert stakksikkerhet.

Kort kontroll

Test forståelsen Deres av akkumulatormønsteret.

Besvar den i den interaktive leksjonen

Oppsummering

De har lært om akkumulatormønsteret:

Før delresultatet i en ekstra parameter.
Beregn det før den rekursive kallet for å nå haleposisjonen.
Skjul akkumulatoren bak en ryddig offentlig funksjon.
Mønsteret generaliseres av foldLeft.

Gratis å komme i gang

Lær deg Scala med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 39
Leksjoner: 143

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Akkumulatormønsteret» gratis?

Ja – hele teksten i «Akkumulatormønsteret» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Scala for backendutvikling og funksjonell programmering-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Scala for backendutvikling og funksjonell programmering inneholder totalt 4 leksjoner.

Hva lærer jeg i «Akkumulatormønsteret»?

Gjør om til halerekursjon Du øver på Scala for backendutvikling og funksjonell programmering med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Scala for backendutvikling og funksjonell programmering?

Ingen tidligere erfaring er nødvendig. Scala for backendutvikling og funksjonell programmering på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.

Hvor lang tid tar leksjonen «Akkumulatormønsteret»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Scala for backendutvikling og funksjonell programmering-leksjonen?

Ja. Alle Scala for backendutvikling og funksjonell programmering-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til Scala for backendutvikling og funksjonell programmering