problema: dadas duas listas xs e ys em ordem crescente, desejamos obter uma nova lista zs, ordenada crescente, formada por todos os elementos que compõem as duas listas de entrada.
solução: o importante na solução que apresentamos aqui, bem conhecida na literatura, é que é uma descrição recursiva com excelente desempenho, o melhor possível. A avaliação percorre uma única vez as listas de entrada, respeitando a ordem dos elementos para produzir a nova lista, automaticamente ordenada. Além disso, é uma definição apropriada para listas infinitas dado que não precisa percorrer as listas de entrada por completo para gerar a solução.
Podemos enunciar a solução da seguinte maneira.
A intercalação de duas listas xs e ys é igual a:
a) se o primeiro elemento de xs é menor que o primeiro elemento de ys, então a lista resultante é igual ao primeiro elemento de xs seguido da intercalação do resto de xs com a lista ys;
zs = (primeiro de xs) : intercalação (resto de xs) ys
b) se o primeiro elemento de ys é menor que o primeiro elemento de xs, então a lista resultante é igual ao primeiro elemento de ys seguido da intercalação do resto de ys com a lista xs;
zs = (primeiro de ys) : intercalação xs (resto de ys)
c) se os dois primeiros elementos são iguais, um deles é abandonado
zs = (primeiro de xs) : intercalação (resto de xs) (resto de ys)
E agora vamos à codificação, onde usamos o conceito de pattern para tornar o código mais legivel.
| merge [] ys | = | ys | |
| merge xs [] | = | xs | |
| merge (x:xs) (y:ys) | | x <> | y <> | x == y | = = = | x:(merge xs (y:ys)) y:(merge (x:xs) ys) x:(merge xs ys) |
E a seguir, dois exemplos de uso. O primeiro com listas finitas e o segundo com listas infinitas. Como se pode observar, para que a computação seja finita, usamos a função take para definir o tamanho que desejamos obter da lista resultante.
> merge [0,2..10][1,3..15]
[0,1,2,3,4,5,6,7,8,9,10,11,13,15]
(516 reductions, 859 cells)
> take 10 (merge [0,2..][1,3..])
[0,1,2,3,4,5,6,7,8,9]
(434 reductions, 666 cells)
Mas o que os números feios tem a ver com isso?
Vamos retomar a determinação do i-ésimo feio, como já fizemos antes, descrevendo a lista dos números feios. A versão anterior usava a abordagem "gerar e testar" e vimos que isto era muito oneroso pois, para obter o feio de ordem 1500 precisávamos processar cerca de 1 bilhão de números, dado que o feio desejado é 859.963.392.
Cabe perguntar: "há uma maneira de gerar diretamente os números feios".
E vejam, a resposta é afirmativa pois, "um número feio é sempre igual ao produto de um número feio por um dos 3 fatores (2, 3 ou 5)".
Com isso podemos ter algo do tipo feios = [1,2,3,5] : "próximo feio".
Resta resolver uma questão, como obter o próximo feio?
Nenhum comentário:
Postar um comentário