Grupo de Estudos em Haskell da UFABC > Introdução à Programação Funcional em Haskell > Avaliação Preguiçosa

Avaliação Preguiçosa

Playlists

1 Avaliação Preguiçosa

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:

“Lazy wheel sieves and spirals of primes”, de Colin Runciman (1997).
“The Genuine Sieve of Eratosthenes” de Melissa O’Neil (2009).

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.