Vamos lembrar da interface Enumerador do laboratório 6:
public interface Enumerador {
int proximo(); // próximo elemento
boolean fim(); // acabaram os elementos?
}Imagine que temos a seguinte interface Lista para listas de inteiros:
public interface Lista {
int quantos(); // quantos elementos a lista tem
int soma(); // soma dos elementos da lista
Enumerador enumerador(); // um enumerador para essa lista
}1. Implemente a classe ListaVazia, que implementa Lista e representa uma lista sem elementos. Você vai
precisar de uma implementação para Enumerador, experimente usar tanto a própria classe
ListaVazia quanto uma classe auxiliar. O enumerador de uma lista vazia já começa com fim() retornando
true.
2. Implemente a classe ListaCons, que também implementa Lista. Essa classe deve ter dois campos:
o campo primeiro, de tipo int, que é o primeiro elemento da lista, e o campo resto, de tipo Lista,
que é o resto da lista. Novamente, você também vai precisar implementar Enumerador. O enumerador
de uma ListaCons produz o primeiro elemento, depois “vira” o enumerador do resto da lista (passa
a delegar proximo() e fim() para esse enumerador).
Não é estritamente necessário dar nome para uma nova classe para implementar o enumerador de ListaCons,
você pode usar uma classe anônima:
public Enumerador enumerador() {
return new Enumerador() {
// campos
public int proximo() {
// implementação de proximo
}
public boolean fim() {
// implementação de fim
}
};
}Um exemplo de uso de ListaCons e ListaVazia, para representar a lista 1, 3, 5:
Lista l = new ListaCons(1, new ListaCons(3, new ListaCons(5, new ListaVazia())));
System.out.println(l.soma()); // 9
System.out.println(l.quantos()); // 3
Enumerador e = l.enumerador();
System.out.println(e.fim()) // false
System.out.println(e.proximo()); // 1
System.out.println(e.fim()) // false
System.out.println(e.proximo()); // 3
System.out.println(e.fim()) // false
System.out.println(e.proximo()); // 5
System.out.println(e.fim()) // true3. Implemente a classe ListaConcat, que também implementa Lista, e possui dois campos, lista1
e lista2, ambos do tipo Lista. ListaConcat representa a concatenação dessas duas listas. Pense
em como implementar um enumerador para essa lista.
Lista l1 = new ListaCons(1, new ListaCons(3, new ListaCons(5, new ListaVazia())));
Lista l2 = new ListaCons(2, new ListaCons(4, new ListaCons(6, new ListaVazia())));
Lista l3 = new ListaConcat(l1, l2);
System.out.println(l3.quantos()); // 6
System.out.println(l3.soma()); // 21
Enumerador e3 = l3.enumerador();
while(!e3.fim()) System.out.println(e3.proximo()); // 1 3 5 2 4 64. Implemente a classe ListaPG, que também implementa Lista e representa uma progressão geométrica.
ListaPG tem três campos, a0, do tipo int, que é o elemento inicial, q, a razão da progressão, e n, também
do tipo int, o número de termos. Novamente, também implemente um enumerador
para essa lista.
Lista l1 = new ListaPG(2,4,5);
System.out.println(l1.quantos()); // 5
System.out.println(l1.soma()); // 682
Enumerador e1 = l1.enumerador();
while(!e1.fim()) System.out.println(e1.proximo()); // 2 8 32 128 5125. Um fold à direita (right fold) é uma construção em que pegamos uma operação binária op, uma lista
de elementos l1, l2, …, ln, e um elemento zero z e fazemos o seguinte:
l1 op l2 op ... ln op z Associamos op à direita, ou seja, fazemos primeiro ln op z e depois caminhamos da direita para a
esquerda. Se a operação é soma e a lista é 1, 2, 4, 6, 8 e o zero é 0 o fold à direita é 1 + (2 + (4 + (6 + (8 + 0)))).
Suponha que temos a seguinte interface para operações binárias com inteiros:
public interface OpBin {
int op(int a, int b); // faz a operação binária
}Adicione o método int foldr(OpBin op, int z) à interface Lista. Esse método deve fazer um fold à direita
na lista, usando op como a operação e z como o zero. Implemente foldr nas classes que você implementou
que implementam Lista. Dica: o fold à direita de ListaCons e ListaConcat são facilmente descritos
através do fold de suas sublistas; para o fold à direita de ListaPG faz mais sentido caminhar na lista “de trás para frente”,
começando pelo último elemento.
OpBin soma = new OpBin() { public int op(int a, int b) { return a + b; } };
OpBin prod = new OpBin() { public int op(int a, int b) { return a * b; } };
Lista l1 = new ListaCons(1, new ListaCons(3, new ListaCons(5, new ListaVazia())));
System.out.println(l1.foldr(soma, 0)) // 9
System.out.println(l1.foldr(prod, 1)) // 15
Lista l2 = new ListaCons(2, new ListaCons(4, new ListaCons(6, new ListaVazia())));
System.out.println(l2.foldr(soma, 0)) // 12
System.out.println(l2.foldr(prod, 1)) // 48
Lista l3 = new ListaConcat(l1, l2);
System.out.println(l3.foldr(soma, 0)) // 21
System.out.println(l3.foldr(prod, 1)) // 720
Lista l4 = new ListaPG(2,4,5);
System.out.println(l4.foldr(soma, 0)) // 682
System.out.println(l4.foldr(prod, 1)) // 33554432Use o formulário abaixo para enviar o Laboratório 7. O prazo para envio é segunda-feira, dia 14/01/2013.
Última Atualização: 2016-05-18 10:58