Wzorce akumulatora
Przeniesie Pan/Pani stan przez rekurencję.
Wzorce akumulatora to bezpłatna lekcja Scala for Backend Engineering & Functional Programming na CoddyKit. To lekcja 2 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.
Po co akumulatory
Zwykła rekurencja buduje wynik podczas powrotu w górę stosu wywołań, po zakończeniu wywołania rekurencyjnego.
Akumulator przekazuje bieżący wynik w dół, do kolejnych wywołań, dzięki czemu odpowiedź jest gotowa po osiągnięciu przypadku bazowego.
Ta niewielka zmiana umożliwia rekurencję ogonową i stałe zużycie stosu.
Funkcja pomocnicza
Wzorzec akumulatora wykorzystuje wewnętrzną funkcję pomocniczą, która przyjmuje dodatkowy parametr: dotychczasowy wynik.
Funkcja zewnętrzna tylko ją uruchamia, przekazując wartość początkową, często 0 lub pustą listę.
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)
}Działanie akumulatora
Pełny program przedstawiony tutaj sumuje listę za pomocą akumulatora.
Proszę zauważyć, że przypadek bazowy zwraca bezpośrednio acc, a nie 0. Suma została zgromadzona podczas przechodzenia w dół listy.
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))) // 10Porównanie obu struktur
W zwykłej rekurencji krok łączenia (h + ...) czeka na zakończenie wewnętrznego wywołania.
W wersji z akumulatorem łączenie następuje przed wywołaniem, a wywołanie jest ostatnią czynnością funkcji.
Właśnie ta właściwość ostatniego wywołania sprawia, że funkcja jest rekurencyjna ogonowo.
// Plain: combine after the call
case h :: t => h + sum(t)
// Accumulator: combine before the call
case h :: t => loop(t, acc + h)Rekurencja ogonowa
Wywołanie rekurencyjne jest ogonowe, gdy stanowi ostatnią czynność funkcji i po nim nie pozostaje już nic do wykonania.
Scala może zoptymalizować je do postaci pętli, ponownie wykorzystując jedną ramkę stosu, dzięki czemu stos nie przepełni się nawet przy bardzo głębokiej rekurencji.
import scala.annotation.tailrec
@tailrec
def countDown(n: Int): Unit =
if (n < 0) ()
else { println(n); countDown(n - 1) }Adnotacja @tailrec
Dodanie @tailrec prosi kompilator o sprawdzenie, czy funkcja rzeczywiście jest rekurencyjna ogonowo.
Jeśli nie jest, kompilacja kończy się jasnym błędem. Cichy problem z wydajnością zostaje w ten sposób zamieniony w gwarancję sprawdzaną podczas budowania.
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))Budowanie listy
Akumulatory nie muszą przechowywać liczb. Mogą także budować kolekcje.
Ta funkcja reverse dodaje każdą głowę na początku akumulatora, co naturalnie odwraca kolejność. Dodawanie na początku za pomocą :: jest szybkie, więc rozwiązanie jest wydajne.
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)
}Działanie reverse
Akumulator zaczyna jako pusty i rośnie w miarę przetwarzania danych wejściowych.
Ponieważ każda głowa jest umieszczana na początku acc, pierwszy element trafia na koniec, tworząc odwróconą listę przy stałym koszcie stosu.
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)Wiele akumulatorów
Funkcja pomocnicza może jednocześnie przenosić kilka akumulatorów.
W tym przypadku w tej samej pętli śledzimy bieżący iloczyn i licznik, a następnie zwracamy oba jako krotkę.
Każdy akumulator przekazuje zaktualizowaną wartość do następnego wywołania.
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)
}Wybór wartości początkowej
Początkowy akumulator musi być elementem neutralnym dla danej operacji.
Dla dodawania użyj 0, dla mnożenia 1, dla budowania listy Nil, a dla łączenia napisów pustego napisu.
Nieprawidłowa wartość początkowa po cichu prowadzi do błędnych wyników.
// addition -> seed 0
// product -> seed 1
// list -> seed Nil
// string -> seed ""Kolejność wyników
Rekurencja z akumulatorem przetwarza elementy od lewej do prawej, ale akumulator oparty na dodawaniu na początku odwraca ich kolejność.
Jeśli podczas budowania listy trzeba zachować kolejność, można odwrócić listę na końcu albo dodawać elementy na końcu, choć ta druga metoda jest wolniejsza. Najczęściej stosuje się dodawanie na początku, a następnie odwrócenie listy.
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)
}Szybkie sprawdzenie
Wybierz prawdziwe stwierdzenie dotyczące rekurencji z akumulatorem.
Podsumowanie
Akumulator przekazuje bieżący wynik przez kolejne wywołania rekurencyjne, dzięki czemu przypadek bazowy może zwrócić go bezpośrednio.
Wywołanie rekurencyjne znajduje się wtedy na pozycji ogonowej, co umożliwia optymalizację wywołań ogonowych w Scali oraz sprawdzanie bezpieczeństwa za pomocą @tailrec.
Akumulator należy zainicjować elementem neutralnym operacji, a gdy kolejność ma znaczenie, na końcu odwrócić wynik.
Często zadawane pytania
Czy lekcja „Wzorce akumulatora” jest bezpłatna?
Tak — pełny tekst „Wzorce 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 „Wzorce akumulatora”?
Przeniesie Pan/Pani stan przez rekurencję. Ć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 2 z 4.
Ile czasu zajmuje lekcja „Wzorce 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
- Myślenie rekurencyjne
- Wzorce akumulatora
- foldLeft i foldRight
- reduce i agregowanie