Dando continuidade ao artigo anterior, podemos abordar dois patterns interessantes: acumuladores e avaliação tardia. Usaremos como plataforma Racket, portanto você vai precisar instalá-lo.

Acumuladores

Acumulador é um pattern muito comum em programação funcional e lógica. Consistem em tirar proveito de tail-call optimisation (TCO) em recursões lineares ou binárias.

Vamos ao mesmo exemplo do artigo anterior, fatorial.

O passo do fatorial é definido como o próprio número vezes o fatorial de seu antecessor, enquanto a parada é o fatorial de zero, igual a um:

n! = n × (n - 1)!
0! = 1

Implementando isso em Racket fica:

(define factorial
  (λ (n)
    [if (zero? n)
        1
        (* n (factorial (- n 1)))]))

O corpo da função λ possui apenas a instrução 'if, que roda 'zero? para verificar a condição – para determinar se se trata do passo ou da parada.

Se for a parada (0!), retorna 1, caso contrário retorna o resultado dainstrução '*.

Portanto, a última instrução, que tirará proveito de TCO será a multiplicação. Porém quem efetua a recursão, promovendo o empilhamento de stacks de função, é 'factorial.

Assim, para aproveitar TCO na recursão, é necessário que a última instrução seja a chamada da recursão.

Pra que isso seja possível, é preciso carregar o resultado acumulado através dos stacks como parâmetro, para que seja retornado na parada. Esta carga de valor acumulado é chamada acumulador.

Então precisamos de uma função que receba o número para o qual se deseja calcular o fatorial e o valor acumulado – o acumulador. Chamaremos essa função de '*factorial*.

A função “provida”, 'factorial, deverá chamar '*factorial* passando o número para o qual o fatorial deve ser calculado e, como valor inicial do acumulador, o valor retornado na parada (1):

(define factorial
  (λ (n)
    *factorial* n 1))

Todo o trabalho pesado deve ser feito em '*factorial*. O algoritmo é quase idêntico ao da função original, apenas retornando o valor acumulado para a parada e, para o passo, retorna a chamada recursiva. A multiplicação será efetuada para calcular o próximo valor do acumulador, passado como parâmetro para o próximo passo:

(define *factorial*
  (λ (n acc)
    [if (zero? n)
        acc
        (*factorial* (- n 1) (* acc n))]))

Agora temos o cálculo fatorial tirando proveito de TCO, o que torna a função tão eficiente quando uma função reiterativa numa linguagem imperativa, mas usando uma abordagem recursiva, muito mais legível e inteligível.

Avaliação tardia ou preguiçosa (lazy evaluation)

As estratégias mais eficientes para lidar com grandes volumes de dados calculados – e até com quantidades infinitas – é a avaliação tardia ou call-by-need. Linguagens como Haskell resolvem os valores das funções sob demanda, ou seja, se uma função é chamada, mas seu resultado não é usado, o corpo da função não é executado – será apenas quando o retorno for necessário.

Isso dá ao programador recursos poderosos, como definir Fibonacci como uma uma função que retorna uma lista infinita:

fib :: [Integer]
fib = 1 : 1 : zipWith (+) fib (tail fib)

Aqui se declara fib como uma função que retorna uma lista de inteiros (Integer) e se define o retorno como 1 seguido de 1, seguido da soma de cada elemento retornado por fib com cada elemento retornado por fib exceto o primeiro (tail).

Isso só é possível porque cada elemento da lista retornada por fib só é avaliado quando necessário.

Para trazer os 10 primeiros elementos de Fibonacci, solicitamos a avaliação dos mesmos usando take:

ghci> take 10 fib
[1,1,2,3,5,8,13,21,34,55]
ghci>

Promises

O recurso de Lazy Racket para fazer avaliação tardia é chamado promise (promessa), que é totalmente diferente de promise em Node.js, mas muito similar à forma como Haskell lida com funções tardiamente.

Ao declarar um código como Lazy Racket com o hash bang #!lazy, ou importando o módulo ((require lazy)), isso sobrescreve muitas das funções por versões preguiçosas, que retornam uma promise em vez de avaliar imediatamente seu resultado.

Ainda introduz a função '!!, que força a resolução da promise.

Vamos então criar um módulo chamado fact.rkt que provê uma versão preguiçosa do cálculo do fatorial, que pode ser usado paralelamente e sob demanda. Repare que o corpo das funções é exatamente igual ao que fizemos acima:

#!lazy
;; fact.rkt

(provide factorial)

(define *factorial*
  (λ (n acc)
    [if (zero? n)
        acc
        (*factorial* (- n 1) (* acc n))]))

(define factorial
  (λ (n)
    *factorial* n 1))

Podemos validar no prompt do racket:

-> (require "fact.rkt")
-> (require lazy)
-> (!! [map (lambda (n) `(,n ,(factorial n))) '(0 1 2 3 4 5)])
'((0 1) (1 1) (2 2) (3 6) (4 24) (5 120))

O 'map gera uma promise que valida o lambda sob demanda para cada valor da lista '(0 1 2 3 4 5).