Scala for Backend Engineering & Functional Programming · Lekcja

Wzorzec akumulatora

Przekształcanie w rekurencję ogonową

Wzorzec akumulatora to bezpłatna lekcja Scala for Backend Engineering & Functional Programming na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Scala for Backend Engineering & Functional Programming, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Scala for Backend Engineering & Functional Programming zawiera 4 lekcji w sumie.

Wzorzec akumulatora

Wzorzec akumulatora przekształca funkcję bez rekurencji ogonowej w funkcję rekurencyjną ogonowo. Częściowy wynik jest przechowywany w dodatkowym parametrze (akumulatorze) zamiast budowania go po powrocie z wywołania.

Główna idea

Zamiast n + sum(n-1) (pracy wykonywanej po wywołaniu) obliczają Państwo nową sumę częściową przed wywołaniem: sum(n-1, acc + n). Wywołanie rekurencyjne jest teraz ostatnią czynnością.

Przedtem: suma bez rekurencji ogonowej

Ta bezpośrednia wersja nie jest rekurencyjna ogonowo: dodawanie czeka na wynik wywołania rekurencyjnego.

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

Potem: suma ogonowa z akumulatorem

Należy dodać parametr acc przechowujący bieżącą sumę. Wywołanie rekurencyjne znajduje się teraz w pozycji ogonowej i może zostać zoptymalizowane.

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

Silnia rekurencyjna ogonowo

Ten sam sposób przekształcenia można zastosować do silni: przed rekurencją należy pomnożyć wartość przez akumulator.

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

Ukrywanie akumulatora

Dodatkowy parametr jest szczegółem implementacyjnym. Należy opakować funkcję pomocniczą rekurencyjną ogonowo w przejrzystą funkcję publiczną, aby wywołujący nie widzieli 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))
  }
}

Akumulowanie listy

Ten wzorzec pozwala również budować kolekcje. Rekurencyjne ogonowo odwracanie listy dodaje każdą głowę na początku listy akumulatora.

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

Kolejność akumulowania

Należy zauważyć, że dodawanie elementów na początku akumulatora naturalnie odwraca kolejność. W funkcji budującej listę i zachowującej kolejność często buduje się listę odwróconą, a na końcu ponownie ją odwraca, albo korzysta z wydajnej struktury dołączania.

map rekurencyjne ogonowo

Należy zbudować listę wynikową za pomocą akumulatora, a następnie raz odwrócić ją na końcu, aby przywrócić kolejność.

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

Związek z foldLeft

Wzorzec akumulatora jest dokładnie tym, co uogólnia foldLeft: przekazuje akumulator przez kolekcję w sposób rekurencyjny ogonowo. Wiele ręcznie napisanych funkcji z akumulatorem można przepisać jako pojedyncze foldLeft.

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

Kiedy go stosować

Po wzorzec akumulatora warto sięgnąć, gdy funkcja rekurencyjna przetwarza dużą strukturę liniową i w przeciwnym razie doprowadziłaby do przepełnienia stosu. W zamian za gwarantowane bezpieczeństwo stosu otrzymują Państwo nieco mniej oczywistą strukturę kodu.

Szybki test

Proszę sprawdzić swoje rozumienie wzorca akumulatora.

Podsumowanie

Poznali Państwo wzorzec akumulatora:

Częściowy wynik jest przechowywany w dodatkowym parametrze.
Należy obliczać go przed rekurencją, aby osiągnąć pozycję ogonową.
Akumulator należy ukryć za przejrzystą funkcją publiczną.
Wzorzec ten uogólnia się do foldLeft.

Często zadawane pytania

Czy lekcja „Wzorzec akumulatora” jest bezpłatna?

Tak — pełny tekst „Wzorzec akumulatora” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Scala for Backend Engineering & Functional Programming, przejdź na CoddyKit PRO. Kurs Scala for Backend Engineering & Functional Programming zawiera 4 lekcji w sumie.

Co nauczysz się w „Wzorzec akumulatora”?

Przekształcanie w rekurencję ogonową Ćwiczysz Scala for Backend Engineering & Functional Programming z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Scala for Backend Engineering & Functional Programming?

Nie wymagamy żadnego doświadczenia. Scala for Backend Engineering & Functional Programming w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Wzorzec akumulatora”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Scala for Backend Engineering & Functional Programming?

Tak. Każda lekcja Scala for Backend Engineering & Functional Programming zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do Scala for Backend Engineering & Functional Programming