Sequências Infinitas?
Em um workshop com o pessoal do trabalho, iríamos começar mais uma implementação de Fibonacci.
Acabamos definindo uma API parecida com a abaixo:
public List<Integer> fibonacci();
Porém, para conseguir fazer algo do gênero, é necessária uma maneira de representar uma sequência infinita de valores.
No workshop, como precisávamos de foco, mudamos a API para receber um número e retornar o número de Fibonacci correspondente.
Só que há uma maneira de representar essa sequência infinita em um computador…
Fibonacci?
Só para lembrar, conforme está descrito na Wikipedia, a sequência de Fibonacci “é uma sequência de números naturais, na qual os primeiros dois termos são 0 e 1, e cada termo subsequente corresponde à soma dos dois precedentes”.
Lazy Evaluation
Na teoria de linguagens de programação, há o conceito de Lazy Evaluation, em que o runtime adia a avaliação de um trecho de código até quando esse código realmente precisar ser executado.
Esse conceito está presente principalmente em Programação Funcional, em linguagens como Haskell, Scheme ou Scala.
Em Scala
Com a linguagem de programação Scala, é possível criar uma uma função recursiva que calcula a sequência de Fibonacci em que não há condição de parada!
def fibonacciSequence : Stream[Long] = {
def fibonacciFrom(a: Long, b: Long) : Stream[Long] = a #:: fibonacciFrom(b, a+b)
fibonacciFrom(0, 1)
}
Mas como isso é possível? Como o código acima não entra em recursão infinita até gerar um StackOverflowError?
No código acima, é utilizada uma estrutura de dados chamada Stream, que é uma lista cuja avaliação da concatenação (o #::) é lazy. Por isso, a chamada recursiva só é feita quando realmente é necessária.
Se chamarmos diretamente a função fibonacciSequence a partir do REPL do Scala será retornado:
scala> fibonacciSequence
> res0: scala.collection.immutable.Stream[Long] = Stream(0, ?)
Observe que só o primeiro valor, que no caso é 0, será retornado. O resto da sequência ainda não foi avaliado, o que é representado como ?.
Se utilizarmos a função take para pegarmos os 5 primeiros valores dessa sequência, ainda assim apenas o primeiro valor é avaliado:
scala> fibonacciSequence take 5
> res1: scala.collection.immutable.Stream[Long] = Stream(0, ?)
Para realmente avaliar os valores, temos que utilizá-los, por exemplo, tranformando para uma lista que não é lazy com um toList ou percorrendo-os com um foreach:
scala> fibonacciSequence take 5 toList
> res2: List[Long] = List(0, 1, 1, 2, 3)
scala> fibonacciSequence take 5 foreach println
> 0
| 1
| 1
| 2
| 3
Em Java
Recentemente, o polêmico Uncle Bob tem escrito sobre como utilizar conceito de Programação Funcional em Java e tem recebido diversas críticas.
Em um de seus artigos, Uncle Bob mostrou como utilizar lazy evaluation em Java utilizando um Iterator. Há um exemplo mostrando o uso de Iterator para criar uma sequência infinita de inteiros elevados ao quadrado.
Na verdade, Neal Ford já havia mostrado como usar um Iterator para obter lazyness com Java. O exemplo utilizado foi o cálculo de números primos.
Com Iterator
Através da técnica do Iterator, é possível fazer um código bem simples para gerar uma sequância “infinita” com os números de Fibonacci:
public class FibonacciSequence implements Iterator<Long> {
private long n = 0;
private long a = 0;
private long b = 1;
public boolean hasNext() { return a + b > 0; }
public Long next() {
long fib;
if(n == 0 || n == 1) {
fib = n;
}
else {
fib = a + b;
a = b;
b = fib;
}
n++;
return fib;
}
public void remove() {}
}
As variáveis a e b armazenam os valores de Fibonacci dos números anteriores. O número atual é mantido na variável n.
Os dois primeiros valores da sequência 0 e 1, são retornados diretamente, sem atualizar as variáveis a e b.
O Fibonacci de um dado número n é a soma dos números de Fibonacci precedentes, portando é a + b. Para preparar a sequência para os próximos valores, as variáveis a e b são atualizadas com o número de Fibonacci anterior e o atual, respectivamente.
A implementação do método hasNext considera se a soma de a + b ainda é positiva, para evitar Integer Overflow, o que faria com que os números a e b ficassem com valores negativos.
Podemos utilizar o código acima, por exemplo, para pegar os 10 primeiros números na sequência:
FibonacciSequence fs = new FibonacciSequence();
for(int i = 0; i < 10 && fs.hasNext(); i++){
System.out.println(fs.next());
}
Podemos criar o objeto Taker criado por Uncle Bob para simular a função take do Scala:
public class Taker<T> {
public List<T> take(int n, Iterator<T> xs) {
List<T> taken = new ArrayList<T>();
for (int i = 0; xs.hasNext() && i < n; i++) {
taken.add(xs.next());
}
return taken;
}
}
Se utilizarmos o Taker para gerar a sequência dos 25 primeiros números de Fibonacci, teríamos o seguinte código:
List<Long> fibonacciUpto25 = new Taker<Long>().take(25, new FibonacciSequence());
Com Functional Java
A biblioteca Functional Java tem uma estrutura de dados Stream parecida com a do Scala, que permite lazy evaluation.
Baseados em um exemplo da documentação da biblioteca, poderíamos definir uma variável no nosso programa que contém a sequência de Fibonacci:
public static final Stream<Long> fibonacciSequence = new F2<Long, Long, Stream<Long>>() {
public Stream<Long> f(final Long a, final Long b) {
return Stream.cons(a, curry().f(b).lazy().f(a + b));
}
}.f(0L, 1L);
O método cons da classe Stream é correspondente ao #:: do Scala.
A classe Stream provê um método take. Assim, para obter nossa lista com os 25 primeiros números da sequência de Fibonacci:
List<Long> fibonacciUpto25 = fibonacciSequence.take(25).toList();
Com Totally Lazy
Já a biblioteca Totally Lazy tem uma função embutida na classe Numbers que gera a sequência de Fibonacci. Essa função é implementada da seguinte forma:
public static Sequence<Number> fibonacciSequence =
computation(Pair.<Number, Number> pair(0, 1), reduceLeftShift(sum)).map(first(Number.class));
Para obter nossos 25 primeiros números de Fibonacci:
List<Number> fibonacciUpto25 = fibonacciSequence.take(25).toList();
A abordagem do Totally Lazy é bem diferente das demais. Observe que a classe Number é utilizada, ao invés de Long.
Mente de Iniciante 