Avaliação Preguiçosa


Playlists

1 Avaliação Preguiçosa

Figure 1: Quero evitar a fadiga…

Figure 1: Quero evitar a fadiga…

  • A avaliação preguiçosa (en: lazy evaluation) é a estratégia de avaliação padrão de várias linguagens funcionais.
  • Ela tem duas propriedades essenciais:
    • A avaliação de uma expressão é suspensa, ou atrasada (delayed) até que resultado seja necessário;
    • A partir do momento que o resultado tiver sido calculado ele é memoizado (en: memoized), i.e. cached, de modo que se ele for preciso novamente ele será reutilizado e não recomputado.

Vamos verificar como a avaliação preguiçosa funciona no Haskell.

  • Para isso utilizaremos a função sprint no ghci que mostra o estado atual da variável.
Prelude> :set -XMonomorphismRestriction
Prelude> x = 5 + 10
Prelude> :sprint x
x = _
Prelude> x = 5 + 10
Prelude> :sprint x
x = _
Prelude> x
15
Prelude> :sprint x
x = 15

O valor de x é computado apenas quando requisitamos seu valor!

Prelude> x = 1 + 1
Prelude> y = x * 3
Prelude> :sprint x
x = _
Prelude> :sprint y
y = _
Prelude> x = 1 + 1
Prelude> y = x * 3
Prelude> :sprint x
x = _
Prelude> :sprint y
y = _
Prelude> y
6
Prelude> :sprint x
x = 2

1.1 Eu quero agora!

A função seq recebe dois parâmetros, avalia o primeiro e retorna o segundo.

Prelude> x = 1 + 1
Prelude> y = 2 * 3
Prelude> :sprint x
x = _
Prelude> :sprint y
y = _
Prelude> seq x y
6
Prelude> :sprint x
x = 2

Alguns exemplos um pouco mais elaborados:

Prelude> let l = map (+1) [1..10] :: [Int]
Prelude> :sprint l
l = _
Prelude> seq l ()
Prelude> :sprint l
l = _ : _
Prelude> length l
Prelude> :sprint l
l = [_,_,_,_,_,_,_,_,_,_]
Prelude> sum l
Prelude> :sprint l
l = [2,3,4,5,6,7,8,9,10,11]

1.2 Exercício 1

O que terá sido avaliado em lista após a execução do seguinte código?

f x = 2*x
g x
 | even x = x + 1
 | otherwise = f x

lista  = [ (x, g x, f x) | x <- [1..], even x ]
lista' = map snd lista
sublista = take 4 lista'

print sublista

1.3 Exercício 1 - Resposta

[(2,3,_), (4,5,_), (6,7,_), (8,9,_)] : _

1.4 Weak Head Normal Form (WHNF)

Ao fazer:

> z = (2, 3)
> :sprint z
z = _
> z `seq` ()
()
> :sprint z
z = (_,_)

A função seq apenas forçou a avaliação da estrutura de tupla. Essa forma é conhecida como _ Weak Head Normal Form _.

1.5 Normal Form

Para avaliar uma expressão em sua forma normal , podemos usar a função force da biblioteca ** Control.DeepSeq **:

> import Control.DeepSeq
> z = (2,3)
> force z
> :sprint z
z = (2,3)

2 Streams

  • Streams são listas similares a listas comuns. Contudo a avaliação de cada célula é feita de maneira preguiçosa.
    • Em Haskell todas as listas são assim.
    • Em outras linguagens pode ser necessário fazer alguma ginástica para implementá-las.

Quando se fala em streams, normalmente falamos de listas infinitas ou cujo comprimento é desconhecido a priori.

[1..] -- todos os números inteiros positivos
[2,4..] -- todos os números pares positivos

3 Exemplo: Números primos

  • Queremos uma lista com todos os números primos
  • Aqui vamos fazer apenas uma versão simples…

Se quiser mergulhar na toca do coelho, neste link você encontra uma versão otimizada baseada em:

3.1 Primeiro exemplo - Função ePrimo

A função ePrimo.

ePrimo :: Int -> Bool
ePrimo x =
  all (\e -> x `rem` e /= 0) possiveisFatores
  where
    maxDiv = ((floor . sqrt) :: Double -> Int) $ fromIntegral x
    possiveisFatores = takeWhile (<= maxDiv) [2..]

E a lista de todos os primos ficaria:

primos = filter ePrimo [2..]

Dá pra melhorar!

  • Não precisamos testar todos os números \(\ge 2\). Basta testar aqueles da forma \(6k \pm 1\), \(k \ge 1\) exceto \(2\) e \(3\) é claro.

Além disso…

[[figuras/gatorrada.gif]]

  • Podemos usar a própria lista de primos que estamos gerando para verificar a primalidade!

3.2 Juntando tudo

primos :: [Int]
primos =
  2 : 3 : filter ePrimo candidatos
  where
    candidatos =  junta [5,11..] [7,13..]
    junta ~(a:as) ~(b:bs) = a : b : junta as bs

ePrimo :: Int -> Bool
ePrimo x =
  all (\e -> x `rem` e /= 0) possiveisFatores
  where
    maxDiv = ((floor . sqrt) :: Double -> Int) $ fromIntegral x
    possiveisFatores = takeWhile (<= maxDiv) primos

4 Exemplo: Sequência de Fibonacci

A famosa sequência de Fibonacci:

\[F_n = F_{n-1} + F_{n-2}\]

Com \(F_1 = F_2 = 1\), e, por convenção, \(F_0 = 0\).

Quero definir uma função que devolve a sequência completa.

4.1 Momento cultural

  • Momento cultural 1: Conforme \(n \rightarrow \infty\), a razão \(\frac{F_n}{F_{n-1}}\) tende a \(\phi\) (a razão áurea).

  • Momento cultural 2: A sequência de Fibonacci não é especial. Qualquer recorrência com essa forma e com valores iniciais arbitrários inteiros positivos serve. 😛

  • Momento cultural 3: Em 1910 o matemático Mark Barr passou a usar a letra grega \(\phi\) para denotar a razão áurea em homenagem ao escultor e arquiteto Fídias (em grego Φειδίας 480 a.C.—430 a.C.) que teria usado a razão áurea no projeto do Paternon.

  • Momento Cultural 4: Mais tarde, Barr revelou que achava improvável que Fídias tenha usado a razão áurea segundo a concepção moderna, mas já era tarde demais. O número já tinha sido batizado.

  • Note que a sequência tem a seguinte característica

         0  1  1  2  3  5  8  13  21 ...
    ​+       0  1  1  2  3  5   8  13 ...
    =    0  1  2  3  5  8  13  21 34 ...
    

De que isso adianta?

Podemos usar a própria lista na sua própria geração!

4.2 Lazy Fibonacci

fibos :: [Integer]
fibos = 0 : 1 : zipWith (+) fibos (tail fibos)

5 Experimente no Repl.it

Todo o código dessa seção pode ser utilizado no Repl.it abaixo:

Código no Repl.it

6 Disclaimer

Estes slides foram preparados para os cursos de Paradigmas de Programação e Desenvolvimento Orientado a Tipos na UFABC.

Este material pode ser usado livremente desde que sejam mantidos, além deste aviso, os créditos aos autores e instituições.