Padrões de acumuladores
Transporte o estado pela recursão.
Padrões de acumuladores é uma aula grátis de Scala for Backend Engineering & Functional Programming no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Scala for Backend Engineering & Functional Programming, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Scala for Backend Engineering & Functional Programming inclui 4 aulas no total.
Por que usar acumuladores
A recursão simples constrói o resultado ao voltar pela pilha de chamadas, depois que a chamada recursiva retorna.
Um acumulador carrega um resultado parcial para dentro de cada chamada, de modo que a resposta esteja pronta quando o caso-base for alcançado.
Essa pequena mudança permite a recursão de cauda e o uso constante da pilha.
A função auxiliar
O padrão de acumulador usa uma função auxiliar interna que recebe um parâmetro adicional: o resultado obtido até o momento.
A função externa apenas a inicia com um valor inicial, geralmente 0 ou uma lista vazia.
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)
}Executando o acumulador
Aqui, o programa completo soma uma lista usando um acumulador.
Observe que o caso-base retorna acc diretamente, e não 0. O total foi construído à medida que descemos pela 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)
}
@main def run(): Unit =
println(sum(List(1, 2, 3, 4))) // 10Comparando as duas estruturas
Na recursão simples, a etapa de combinação (h + ...) espera pela chamada interna.
Na versão com acumulador, a combinação acontece antes da chamada, e a chamada é a última coisa que a função faz.
É essa propriedade de última chamada que torna a função recursiva de cauda.
// Plain: combine after the call
case h :: t => h + sum(t)
// Accumulator: combine before the call
case h :: t => loop(t, acc + h)Recursão de cauda
Uma chamada recursiva de cauda é aquela em que a chamada recursiva é a ação final da função, sem nada a fazer depois.
Scala pode otimizá-la como um laço, reutilizando um único quadro da pilha, para que ela nunca cause estouro, independentemente da profundidade.
import scala.annotation.tailrec
@tailrec
def countDown(n: Int): Unit =
if (n < 0) ()
else { println(n); countDown(n - 1) }A anotação @tailrec
Adicionar @tailrec solicita ao compilador que verifique se a função é realmente recursiva de cauda.
Se não for, a compilação falhará com um erro claro. Isso transforma uma armadilha silenciosa de desempenho em uma garantia no momento da compilação.
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))Acumulando uma lista
Os acumuladores não precisam armazenar números. Eles também podem construir coleções.
Essa função reverse adiciona cada cabeça no início do acumulador, invertendo naturalmente a ordem. Adicionar no início com :: é rápido, portanto essa abordagem é eficiente.
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 em ação
O acumulador começa vazio e cresce à medida que consumimos a entrada.
Como cada cabeça é colocada no início de acc, o primeiro elemento acaba por último, produzindo uma lista invertida com custo constante de pilha.
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)Vários acumuladores
Uma função auxiliar pode carregar vários acumuladores ao mesmo tempo.
Aqui, acompanhamos um produto parcial e uma contagem no mesmo laço, retornando ambos como uma tupla.
Cada um leva seu valor atualizado para a chamada seguinte.
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)
}Escolhendo o valor inicial
O acumulador inicial deve ser o elemento identidade da sua operação.
Para adição, use 0; para multiplicação, use 1; para construção de listas, use Nil; para união de strings, use a string vazia.
Uma semente incorreta produz respostas erradas silenciosamente.
// addition -> seed 0
// product -> seed 1
// list -> seed Nil
// string -> seed ""Ordem dos resultados
A recursão com acumulador processa os elementos da esquerda para a direita, mas um acumulador baseado em adicionar no início os inverte.
Se você precisar preservar a ordem ao construir uma lista, poderá invertê-la no final ou adicionar elementos ao final, embora essa última opção seja mais lenta. Adicionar no início e depois inverter é o padrão usual.
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)
}Verificação rápida
Escolha a afirmação correta sobre a recursão com acumulador.
Recapitulação
Um acumulador leva o resultado parcial ao longo das chamadas recursivas, permitindo que o caso-base o retorne diretamente.
Isso coloca a chamada recursiva na posição de cauda, habilitando a otimização de chamadas de cauda do Scala e a verificação de segurança de @tailrec.
Inicialize o acumulador com o valor identidade da operação e inverta o resultado no final quando a ordem for importante.
Perguntas Frequentes
A aula “Padrões de acumuladores” é grátis?
Sim — o texto completo de “Padrões de acumuladores” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Scala for Backend Engineering & Functional Programming, atualize para CoddyKit PRO. O curso de Scala for Backend Engineering & Functional Programming inclui 4 aulas no total.
O que vou aprender em “Padrões de acumuladores”?
Transporte o estado pela recursão. Você pratica Scala for Backend Engineering & Functional Programming com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Scala for Backend Engineering & Functional Programming?
Nenhuma experiência prévia é necessária. Scala for Backend Engineering & Functional Programming no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Padrões de acumuladores”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Scala for Backend Engineering & Functional Programming?
Sim. Cada aula de Scala for Backend Engineering & Functional Programming inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Pensando recursivamente
- Padrões de acumuladores
- foldLeft e foldRight
- reduce e agregação