Vamos rever aqui a definição de números feios apresentada na postagem anterior, para pontuar alguns aspectos relevantes para a programação de um modo geral.
m2 = [x*2| x <- feios]
m3 = [x*3| x <- feios]
m5 = [x*5| x <- feios]
feios = 1: merge (merge m2 m3) m5
Em primeiro lugar, o problema de determinar o i-ésimo número feio foi resolvido a partir de uma generalização, ao invés de pensarmos na determinação de um elemento específico, abordamos o problema a solução a partir da definição do conceito de números feios. Esta definição, é não paramétrica e facilita seu uso em situações variadas ao invés de se prestar apenas à determinação de um dado elemento.
A definição foi estruturada com base na definição de 4 listas infinitas, usando recursão infinita. Pode-se observar ainda que aqui a definição como um todo se apóia em uma recursões mútuas. Para definir os feios precisamos dos números gerados pelo produto de cada número feio por 2, por 3 e por 5. Para definir cada uma dessas listas (m2, m3 e m5) precisamos dos feios. A avaliação é feita de uma maneira preguiçosa (lazzy evaluation), o que significa que a geração de cada lista avança de maneira paulatina, ou seja, cada elemento é produzido no momento em que precisamos operá-lo (just on time).
Existem várias referências à determinação desses números, também conhecidos como Hamming´s Number, devido a Richard Hamming, no contexto de programação procedural e de análise de algoritmos. A popularização deste problema se deve a Edsger Dijkstra.
domingo, 15 de julho de 2007
sábado, 14 de julho de 2007
Números feios - IV
Muito bem, sabemos que os números feios podem ser gerados diretamente, sem precisar usar o processo "gerar e testar", como acontece nos números primos.
qfeios = 1:[ x*y| x <- qfeios, y<-[2,3,5]]
e vejamos uma avaliação, acessando alguns feios:
>take 52 qfeios
[1,2,3,5,4,6,10,6,9,15,10,15,25,8,12,20,12,18,30,20,30,50,12,18,30,
18,27,45,30,45,75,20,30,50,30,45,75,50,75,125,16,24,40,24,36,60,40,
60,100,24,36,60]
(1584 reductions, 2636 cells)
Três aspectos desta lista merecem atenção:
a) ela é formada por sublista, cada uma associada com um dos fatores;
b) a lista possui elementos repetidos;
c) a lista está desordenada;
Os fatos b e c, inviabilizam a determinação do i-ésimo número feio. Entretanto o fato a no traz uma solução. Podemos gerar as três listas isoladamente.
m2 = [x*2| x <- feios]
m3 = [x*3| x <- feios]
m5 = [x*5| x <- feios]
e o truque final :
feios = 1: merge (merge m2 m3) m5
podemos agora, como em qualquer lista infinita, obter sublistas finitas.
> take 10 feios
[1,2,3,4,5,6,8,9,10,12]
> drop 90 (take 100 feios)
[1200,1215,1250,1280,1296,1350,1440,1458,1500,1536]
e agora voltemos a nossa questão inicial: Determinar o feio de ordem 1500.
> head (drop 1499(take 1500 feios))
859963392
(48017 reductions, 60032 cells)
bom, parece que esta descrição está um pouco difícil de entender. :-)
que tal essa:
> last(take 1500 feios)
859963392
(25534 reductions, 31551 cells)
mas essa parece melhor: o feio de ordem 1500 é o elemento de indíce 1499 na lista lfeios.
> feios!!1499
859963392
(28518 reductions, 36032 cells)
Nada impede que se tenha uma definição específica para determinar o feio de ordem k.
feio k = feios!!(k - 1)
e que assim possamos pedir a avaliação:
> feio 1500
859963392
(90641 reductions, 146337 cells)
Podemos voltar a falar sobre desempenho. Relembremos do que tinhamos antes usando "gerar e testar".
A diferença entre o número de reduções e a quantidade de células utilizadas pelas duas versões do descrição da função nos fornece um bom entendimento da diferença no desempenho do Interpretador na avaliação das duas. Vejamos o caso do feio de ordem 500.
reduções : 387.151.581 versus 21.802, um ganho da ordem de 10 4
células: 568.449.819 versus 3.717 um ganho da ordem de 10 5
garbage: 577 versus 0
qfeios = 1:[ x*y| x <- qfeios, y<-[2,3,5]]
e vejamos uma avaliação, acessando alguns feios:
>take 52 qfeios
[1,2,3,5,4,6,10,6,9,15,10,15,25,8,12,20,12,18,30,20,30,50,12,18,30,
18,27,45,30,45,75,20,30,50,30,45,75,50,75,125,16,24,40,24,36,60,40,
60,100,24,36,60]
(1584 reductions, 2636 cells)
Três aspectos desta lista merecem atenção:
a) ela é formada por sublista, cada uma associada com um dos fatores;
b) a lista possui elementos repetidos;
c) a lista está desordenada;
Os fatos b e c, inviabilizam a determinação do i-ésimo número feio. Entretanto o fato a no traz uma solução. Podemos gerar as três listas isoladamente.
m2 = [x*2| x <- feios]
m3 = [x*3| x <- feios]
m5 = [x*5| x <- feios]
e o truque final :
feios = 1: merge (merge m2 m3) m5
podemos agora, como em qualquer lista infinita, obter sublistas finitas.
> take 10 feios
[1,2,3,4,5,6,8,9,10,12]
> drop 90 (take 100 feios)
[1200,1215,1250,1280,1296,1350,1440,1458,1500,1536]
e agora voltemos a nossa questão inicial: Determinar o feio de ordem 1500.
> head (drop 1499(take 1500 feios))
859963392
(48017 reductions, 60032 cells)
bom, parece que esta descrição está um pouco difícil de entender. :-)
que tal essa:
> last(take 1500 feios)
859963392
(25534 reductions, 31551 cells)
mas essa parece melhor: o feio de ordem 1500 é o elemento de indíce 1499 na lista lfeios.
> feios!!1499
859963392
(28518 reductions, 36032 cells)
Nada impede que se tenha uma definição específica para determinar o feio de ordem k.
feio k = feios!!(k - 1)
e que assim possamos pedir a avaliação:
> feio 1500
859963392
(90641 reductions, 146337 cells)
Podemos voltar a falar sobre desempenho. Relembremos do que tinhamos antes usando "gerar e testar".
| ordem | resultado | gerar e testar | geração direta |
| 0 | 1 | (283 reductions, 525 cells) | (40 reductions, 60 cells) |
| 10 | 15 | (5582 reductions, 8081 cells) | (498 reductions, 776 cells) |
| 100 | 1.600 | (662585 reductions, 962977 cells) | (5122 reductions, 7970 cells) |
| 200 | 16.384 | (6168873 reductions, 8984262 cells, 9 garbage collections) | (7724 reductions, 11584 cells) |
| 500 | 944.784 | (387151581 reductions, 568449819 cells, 577 garbage collections) | (21802 reductions, 3717 cells) |
| 1.499 | 859 x 10 6 | | (71025 reductions, 111917 cells) |
| 14.999 | 123 x 10 18 | | (285018 reductions, |
| 30.000 | 32 x 10 24 | | (1916481 reductions, 3385960 cells, 5 garbage collections) |
A diferença entre o número de reduções e a quantidade de células utilizadas pelas duas versões do descrição da função nos fornece um bom entendimento da diferença no desempenho do Interpretador na avaliação das duas. Vejamos o caso do feio de ordem 500.
reduções : 387.151.581 versus 21.802, um ganho da ordem de 10 4
células: 568.449.819 versus 3.717 um ganho da ordem de 10 5
garbage: 577 versus 0
sexta-feira, 13 de julho de 2007
Números Feios - III
A nossa próxima versão de números feios explora um conceito importante em computação, a intercalação (merge) de listas ordenadas, sejam elas finitas ou infinitas.
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.
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?
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?
Números Primos - II
Vamos agora usar o conceito de listas infinitas para descrever a lista de números primos.
sem_divisor n [ ] = True
sem_divisor n (x:xs) = if (mod n x) == 0 then False else sem_divisor n xs
--
--
primos = 2:[x|x<-[3,5 ..],
sem_divisor x(takeWhile(<= truncate (sqrt( fromIntegral x)) )primos) ]
A elegância da descrição da lista de primos é o que há de mais importante, principalmente por usar a própria definição de primos. Temos aqui a descrição recursiva de uma lista infinita e, portanto, uma recursão infinita. Ou sejam, nossa lista de candidatos a primos são os números ímpares
e para estes verificamos a existência de divisores, usando para isto apenas um pedaço da lista de primos, ou seja, aqueles que são menores que a raiz quadrada do número considerado.
sem_divisor n [ ] = True
sem_divisor n (x:xs) = if (mod n x) == 0 then False else sem_divisor n xs
--
--
primos = 2:[x|x<-[3,5 ..],
sem_divisor x(takeWhile(<= truncate (sqrt( fromIntegral x)) )primos) ]
A elegância da descrição da lista de primos é o que há de mais importante, principalmente por usar a própria definição de primos. Temos aqui a descrição recursiva de uma lista infinita e, portanto, uma recursão infinita. Ou sejam, nossa lista de candidatos a primos são os números ímpares
x<-[3,5 ..]
e para estes verificamos a existência de divisores, usando para isto apenas um pedaço da lista de primos, ou seja, aqueles que são menores que a raiz quadrada do número considerado.
(takeWhile (<= truncate (sqrt (fromIntegral x)))primos)
Sabemos que a lista primos é infinita e que portanto não é conveniente a sua avaliação por completo, entretanto podemos desejar obter os n primeiros números primos o que pode ser obtido com o uso de take n.
> take 10 primos
[2,3,5,7,11,13,17,19,23,29]
(6948 reductions, 10214 cells)
> take 100 primos
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,
109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,
229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,
479,487,491,499,503,509,521,523,541]
(174196 reductions, 248654 cells)
> take 100 primos
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,
109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,
229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,
479,487,491,499,503,509,521,523,541]
(2437 reductions, 3620 cells)
É importante observar que na segunda vez que usamos > take 100 primos, o número de reduções é bem menor, em decorrência da abordagem que o interpretador dá à avaliação de uma expressão, guardando os resultados de expressões para usos posteriores.
Sabemos que a lista primos é infinita e que portanto não é conveniente a sua avaliação por completo, entretanto podemos desejar obter os n primeiros números primos o que pode ser obtido com o uso de take n.
> take 10 primos
[2,3,5,7,11,13,17,19,23,29]
(6948 reductions, 10214 cells)
> take 100 primos
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,
109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,
229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,
479,487,491,499,503,509,521,523,541]
(174196 reductions, 248654 cells)
> take 100 primos
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,
109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,
229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,
479,487,491,499,503,509,521,523,541]
(2437 reductions, 3620 cells)
É importante observar que na segunda vez que usamos > take 100 primos, o número de reduções é bem menor, em decorrência da abordagem que o interpretador dá à avaliação de uma expressão, guardando os resultados de expressões para usos posteriores.
quinta-feira, 12 de julho de 2007
Números Primos - I
Uma maneira simples de verificar se um número é primo, se baseia na própria definição:
"Um número n é primo quando seus únicos divisores são a unidade e o próprio n"
Assim, basta que um número n possua pelo menos um divisor diferente de 1 e dele mesmo para que não seja primo.
A lista de candidatos a divisores é formada por números maiores que 1 e menores que n, algo como:
Bom, isto parece animado! Que novas reduções podemos fazer na lista de candidatos?
A lista de candidatos a divisores é formada por números maiores que 1 e menores que n, algo como:
lcand n = [2..(n - 1)]
Podemos então construir uma função recursiva que verifica se um número é divisível por algum elemento de uma lista:
tem_divisor n [ ] = False
tem_divisor n (x:xs) = if (mod n x) == 0 then True else tem_divisor n xs
Agora estamos prontos para escrever a função que verifica se um número é primo:
primo n = not (tem_divisor n (lcand n))
Vejamos alguns exemplos de uso:
> primo 35
False
(372 reductions, 620 cells)
> primo 36
False
(116 reductions, 186 cells)
> primo 859963392
False
(116 reductions, 190 cells)
Um rápida reflexão nos levar a perceber que a lista de candidatos tem mais elementos que o necessário. Afinal, não precisamos buscar divisores nos números maiores que a matade de n, certo? Com isso podemos ter uma nova versão.
primo' n = not (tem_divisor n (lcand' n))
lcand' n = [2..(div n 2) - 1]
E podemos avaliar números com respeito à sua primalidade usando a nova versão:
> primo' 35
False
(427 reductions, 628 cells)
> primo' 36
False
(173 reductions, 267 cells)
> primo' 859963392
False
(173 reductions, 273 cells)
Agora vejamos algumas comparações entre as duas versões.
Primeiro, quando aplicamos as duas funções para números não primos, verifica-se um desempenho semelhante:
> primo 1048576
False
(116 reductions, 188 cells)
> primo' 1048576
False
(173 reductions, 270 cells)
Mas com números primos, já percebe-se uma boa diferença no desempenho:
> primo 1048583
True :: Bool
(84.935.121 reductions, 124751350 cells, 126 garbage collections)
> primo' 1048583
True :: Bool
(42.467.534 reductions, 62360646 cells, 63 garbage collections)
Isto nos anima a buscar novas reduções da lista de candidatos. Rapidamente podemos perceber que temos mais candidatos do que precisamos. Dos números pares, basta usar o 2. Assim, podemos trabalhar apenas com a lista formada pelo 2 e os números impares.
primo'' n = not (tem_divisor n (lcand'' n))
lcand'' n = [2] ++ [3,5..(div n 2) - 1]
E novamente, a avaliação, no leva a perceber ganhos.
tem_divisor n [ ] = False
tem_divisor n (x:xs) = if (mod n x) == 0 then True else tem_divisor n xs
Agora estamos prontos para escrever a função que verifica se um número é primo:
primo n = not (tem_divisor n (lcand n))
Vejamos alguns exemplos de uso:
> primo 35
False
(372 reductions, 620 cells)
> primo 36
False
(116 reductions, 186 cells)
> primo 859963392
False
(116 reductions, 190 cells)
Um rápida reflexão nos levar a perceber que a lista de candidatos tem mais elementos que o necessário. Afinal, não precisamos buscar divisores nos números maiores que a matade de n, certo? Com isso podemos ter uma nova versão.
primo' n = not (tem_divisor n (lcand' n))
lcand' n = [2..(div n 2) - 1]
E podemos avaliar números com respeito à sua primalidade usando a nova versão:
> primo' 35
False
(427 reductions, 628 cells)
> primo' 36
False
(173 reductions, 267 cells)
> primo' 859963392
False
(173 reductions, 273 cells)
Agora vejamos algumas comparações entre as duas versões.
Primeiro, quando aplicamos as duas funções para números não primos, verifica-se um desempenho semelhante:
> primo 1048576
False
(116 reductions, 188 cells)
> primo' 1048576
False
(173 reductions, 270 cells)
Mas com números primos, já percebe-se uma boa diferença no desempenho:
> primo 1048583
True :: Bool
(84.935.121 reductions, 124751350 cells, 126 garbage collections)
> primo' 1048583
True :: Bool
(42.467.534 reductions, 62360646 cells, 63 garbage collections)
Isto nos anima a buscar novas reduções da lista de candidatos. Rapidamente podemos perceber que temos mais candidatos do que precisamos. Dos números pares, basta usar o 2. Assim, podemos trabalhar apenas com a lista formada pelo 2 e os números impares.
primo'' n = not (tem_divisor n (lcand'' n))
lcand'' n = [2] ++ [3,5..(div n 2) - 1]
E novamente, a avaliação, no leva a perceber ganhos.
> primo'' 1048583
True
(21.233.886 reductions, 31180614 cells, 31 garbage collections)
True
(21.233.886 reductions, 31180614 cells, 31 garbage collections)
Bom, isto parece animado! Que novas reduções podemos fazer na lista de candidatos?
Vamos medir o tamanho das listas que temos usado para o número 1.048.583?
> length (lcand 1048583)
1.048.581
> length (lcand' 1048583)
524.289
> length (lcand'' 1048583)
262.145
Uma nova inspeção nos leva à conclusão que nossa lista de candidatos a divisores de n ainda pode ser menor. Na verdade, pode-se mostrar que a lista de candidatos tem como limite superior, a raiz quadrada de n.
Assim podemos escrever uma nova versão da lista de candidatos:
lcand''' n = [2] ++ [3,5..truncate(sqrt n)]
e determinar o tamanho desta lista para o nosso número exemplo:
> length (lcand''' 1048583)
512
E agora parece que temos uma excelente melhoria no desempenho.
Poderíamos agora ver o comportamento da nova versão para a função primo:
primo''' n = not (tem_divisor n (lcand''' n))
infelizmente a tentativa de usá-la, chegamos ao seguinte entrave:
> primo''' 1048583
ERROR - Unresolved overloading
*** Type : (Floating a, Integral a, RealFrac a) => Bool
*** Expression : primo''' 1048583
e nossa expectativa fica parcialmente frustada. Depois iremos conversar melhor sobre este tipo de problema, por enquanto vamos contornar de uma maneira simples, usando a avaliação direta da definição:
> not (tem_divisor 1048583 (lcand''' 1048583))
True :: Bool
(41.845 reductions, 59948 cells)
e, como esperado, temos um ganho de desempenho proporcional ao tamanho da nossa nova lista de candidatos.
Abaixo reapresentamos os resultados obtidos com a avaliação da primalidade do número 1.048.583.
primo 1048583 -(84.935.121 reductions, 124751350 cells, 126 garbage collections)
primo' 1048583 -(42.467.534 reductions, 62360646 cells, 63 garbage collections)
> length (lcand 1048583)
1.048.581
> length (lcand' 1048583)
524.289
> length (lcand'' 1048583)
262.145
Uma nova inspeção nos leva à conclusão que nossa lista de candidatos a divisores de n ainda pode ser menor. Na verdade, pode-se mostrar que a lista de candidatos tem como limite superior, a raiz quadrada de n.
Assim podemos escrever uma nova versão da lista de candidatos:
lcand''' n = [2] ++ [3,5..truncate(sqrt n)]
e determinar o tamanho desta lista para o nosso número exemplo:
> length (lcand''' 1048583)
512
E agora parece que temos uma excelente melhoria no desempenho.
Poderíamos agora ver o comportamento da nova versão para a função primo:
primo''' n = not (tem_divisor n (lcand''' n))
infelizmente a tentativa de usá-la, chegamos ao seguinte entrave:
> primo''' 1048583
ERROR - Unresolved overloading
*** Type : (Floating a, Integral a, RealFrac a) => Bool
*** Expression : primo''' 1048583
e nossa expectativa fica parcialmente frustada. Depois iremos conversar melhor sobre este tipo de problema, por enquanto vamos contornar de uma maneira simples, usando a avaliação direta da definição:
> not (tem_divisor 1048583 (lcand''' 1048583))
True :: Bool
(41.845 reductions, 59948 cells)
e, como esperado, temos um ganho de desempenho proporcional ao tamanho da nossa nova lista de candidatos.
Abaixo reapresentamos os resultados obtidos com a avaliação da primalidade do número 1.048.583.
primo 1048583 -(84.935.121 reductions, 124751350 cells, 126 garbage collections)
primo' 1048583 -(42.467.534 reductions, 62360646 cells, 63 garbage collections)
primo'' 1048583 -(21.233.886 reductions, 31180614 cells, 31 garbage collections)
primo'''1048583 -(41.845 reductions, 59948 cells)
Enquanto as reduções anteriores eram da ordem de n/2, neste caso obtivemos uma redução em torno de sqrt n * 10.
Será que ainda podemos reduzir esta lista de candidatos?
A pista é a seguinte: a lista de candidatos pode ser composta apenas por números primos, certo?
Encerramos esta postagem chamando atenção para uma certa similaridade entre a solução adotada no tratamento dos números feios e os números primos. Nos dois casos, geramos uma lista de candidatos que são testados.
Esta é uma estratégia geral para solução de problemas, quando desejamos determinar uma lista de elmentos que satisfazem uma determinada propriedade, conhecida como "generate and test", ou "gerar e testar".
Enquanto as reduções anteriores eram da ordem de n/2, neste caso obtivemos uma redução em torno de sqrt n * 10.
Será que ainda podemos reduzir esta lista de candidatos?
A pista é a seguinte: a lista de candidatos pode ser composta apenas por números primos, certo?
Encerramos esta postagem chamando atenção para uma certa similaridade entre a solução adotada no tratamento dos números feios e os números primos. Nos dois casos, geramos uma lista de candidatos que são testados.
Esta é uma estratégia geral para solução de problemas, quando desejamos determinar uma lista de elmentos que satisfazem uma determinada propriedade, conhecida como "generate and test", ou "gerar e testar".
domingo, 8 de julho de 2007
Números Feios - II
Por certo a expectativa é a obtenção mais conveniente para o problema dos números feios. Mas por enquanto, vamos retardar um pouco este desfecho. Vamos aproveitar a oportunidade para saborear um pouco uma estratégia muito interessante na resolução de problema. Segundo George Polya, após resolver um problema devemos buscar generalizações.
Me ocorreu portanto explorar esta estratégia a partir da função que verifica se um dado número satisfaz a propriedade de pertencer ao conjunto dos feios. Como vimos isto foi obtido com o apoio de uma outra função, reduz x n.
feio x = reduz (reduz (reduz x 2) 3) 5 == 1
reduz x n = if mod x n == 0
then reduz (div x n) n
else x
Pode-se observar aqui que verficar se x é feito foi realizado por verificar se a composição da aplicação de reduz x1 2, seguida de reduz x2 3, seguida de reduz x3 5, produz o valor 1.
Podemos generalizar então a função feio x para que possamos verificar se um número é redutível por uma lista qualquer de números. Vamos chamá-la de fprimos.
fprimos n [ ] = n
fprimos n (x:xs) = if n < x
then fprimos n xs else
fprimos (reduz n x) xs
Vejamos alguns exemplos de uso:
> fprimos 1000 [2,3,5]
1
> fprimos 10009 [2,3,5]
10009
> fprimos 100092 [2,3,5]
8341
> fprimos 944784 [2,3,5]
1
> fprimos 859963392 [2,3,5]
1
> fprimos 1048576 [2]
1
O último exemplo acima mostra um outro uso, a de verificar se um número é potência de um determinado fator primo. No caso, como se sabe, o número 1.048.576 é a potência 20 do fator 2.
COmo isso, podemos fazer uma nova versão da função feio, usando agora a função fprimos.
feio' x = fprimos x [2,3,5] == 1
E aqui temos alguns exemplos de uso.
> feio' 859963392
True
> feio' 1024
True
> feio' 1026
False
> feio' 859963392
True
> feio' 1985
False
> feio 1985 == feio' 1985
True
Nova questões sobre generalização podem surgir, tal como:
Me ocorreu portanto explorar esta estratégia a partir da função que verifica se um dado número satisfaz a propriedade de pertencer ao conjunto dos feios. Como vimos isto foi obtido com o apoio de uma outra função, reduz x n.
feio x = reduz (reduz (reduz x 2) 3) 5 == 1
reduz x n = if mod x n == 0
then reduz (div x n) n
else x
Pode-se observar aqui que verficar se x é feito foi realizado por verificar se a composição da aplicação de reduz x1 2, seguida de reduz x2 3, seguida de reduz x3 5, produz o valor 1.
Podemos generalizar então a função feio x para que possamos verificar se um número é redutível por uma lista qualquer de números. Vamos chamá-la de fprimos.
fprimos n [ ] = n
fprimos n (x:xs) = if n < x
then fprimos n xs else
fprimos (reduz n x) xs
Vejamos alguns exemplos de uso:
> fprimos 1000 [2,3,5]
1
> fprimos 10009 [2,3,5]
10009
> fprimos 100092 [2,3,5]
8341
> fprimos 944784 [2,3,5]
1
> fprimos 859963392 [2,3,5]
1
> fprimos 1048576 [2]
1
O último exemplo acima mostra um outro uso, a de verificar se um número é potência de um determinado fator primo. No caso, como se sabe, o número 1.048.576 é a potência 20 do fator 2.
COmo isso, podemos fazer uma nova versão da função feio, usando agora a função fprimos.
feio' x = fprimos x [2,3,5] == 1
E aqui temos alguns exemplos de uso.
> feio' 859963392
True
> feio' 1024
True
> feio' 1026
False
> feio' 859963392
True
> feio' 1985
False
> feio 1985 == feio' 1985
True
Nova questões sobre generalização podem surgir, tal como:
Como podemos usar a função fprimos para verificar se um número é primo?
segunda-feira, 2 de julho de 2007
Números Feios - I
Visitando o site de problemas da Universidad de Valladolid (UVA), encontrei um problema que me chamou atenção por dois aspecto. Inicialmente pelo nome, "Ugly Numbers". Pensei comigo, que propriedades teriam esses números para serem chamados de feios? Depois pela simplicidade da descrição. Pensei de novo, o que será que um problemas tão simples assim tem de atraente?
Vejamos a descrição do problema de no. 136 do site da UVA.
O que ocorre na verdade é que a solução ingênua é muito dispendiosa. Consome bastante tempo.
Bom, resolvi explorar um pouco sobre soluções em Haskell para o problema e vi que ele apresentava a oportunidade de fazermos um tour por algumas facilidades da linguagem.
A primeira versão, a bem ingênua, considera que os números feios formam uma lista, cujos elementos são oriundos da lista infinita [1.. ] e que satisfazem a propriedades de terem como únicos fatores primos os números 2, 3 e 5.
Assim, a primeira providência é definir a lista de números feios:
feios = [x | x<-[1..], feio x]
a segunda é definir o predicado feio x,
feio x = reduz (reduz (reduz x 2) 3) 5 == 1
Para tanto precisou-se construir uma função auxiliar, reduz x n, cuja finalidade é extrair de um número x as potências de um outro dado n.
reduz x n = if mod x n == 0 then reduz (div x n) n else x
agora, como temos uma lista como todos os feios, se desejamos conhecer o numero feio de ordem 1500, basta pedir ao sistema que determine, usando a operação de indexação (!!). O feio de ordem 1500 pode ser descrito por: feios!!1499, certo?
Podemos usar para outros feios também:
> feios!!0
1
(283 reductions, 525 cells)
> feios!!10
15
(5582 reductions, 8081 cells)
> feios!!100
1600
(662585 reductions, 962977 cells)
> feios!!200
16384
(6168873 reductions, 8984262 cells, 9 garbage collections)
>feios!!500
944784
(387151581 reductions, 568449819 cells, 577 garbage collections)
Veja que já começou a ficar complicado para o ambiente WinHugs. O esforço já está grande. Imagine se pedirmos feios!!1499.
Bom, disto podemos concluir que nossa solução ingênua não é muito boa.
Apesar disso, podemos aproveitar os ganhos que tivemos.
a) A função feio x, pode ser usada para verificar se um dado número é feio ou não, independente da função feios, o que ilustra bem o estilo da linguagem. Cada função pode ser usada independente.
> feio 944784
True
(1765 reductions, 2561 cells)
> feio 859963392
True
(2952 reductions, 4291 cells)
este último exemplo, é o feio de ordem 1500. Só para verificar se é feio ou não, até que o avaliador dá conta com facilidade.
b) A função feios, serve para obter não apenas o k-ésimo elemento, mas qualquer outro feio que desejarmos.
c) Podemos obter a lista do n primeiro feios. Na verdade, usando as funções take n e drop n podemos pegar qualquer pedaço da lista. Esta facilidade é possivel graças ao uso do conceito de lista infinita. Não precisamos saber antecipadamente quantos elementos iremos querer, isto é determinado em tempo de avaliação de uma expressão.
> take 10 feios
[1,2,3,4,5,6,8,9,10,12]
(278 reductions, 391 cells)
> take 10 (drop 10 feios) -- do 11 ao 20-éssimo
[15,16,18,20,24,25,27,30,32,36]
(451 reductions, 602 cells)
d) A função reduz, que nos serviu para para construir a feio x, serve na verdade para ser usada em outras situações. Como por exemplo, para verificar se um número é uma potência de outro.
> reduz 1024 3 == 1 -- 1024 é uma potência de 3?
False
(110 reductions, 152 cells)
> reduz 1024 2 == 1 -- 1024 é uma potência de 2?
True
(1189 reductions, 1697 cells)
Bom, podemos dar outros usos à função reduz, mas por enquanto ficamos assim.
Antes de terminar esta postagem, cabe ainda um comentário sobre a origem da inconveniência computacional introduzida pela especificação que foi aqui apresentada.
Podemos observar que para cada numero inteiro positivo precisamos verificar se ele satisfaz à condição de pertencer ou não aos feios. Assim, mesmo para aqueles que não são feio, precisamos fazer as reduções. A quantidade de feios é bem pequena em relação ao demais. No caso no número feio de 0rdem 1500, ele é o número 859.963.392 , quase 1 bilhão. Ou seja, para encontrar o número feio da ordem desejada foi necessário analisar cerca de 1 bilhão de números (10^9). Se para testar cada número gastarmos 0,001 seg precisaremos de 10^6 seg para encontrar o número desejado.
Vejamos a descrição do problema de no. 136 do site da UVA.
Ugly Numbers
Ugly numbers are numbers whose only prime factors are 2, 3 or 5.
The sequence: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 1500'th ugly number.
Input Output
There is no input to this program. Output should consist of a single line as shown below, with replaced by the number computed.
Sample output
The 1500'th ugly number is .
Chamou-me ainda atenção o alto número de submissões, atualmente 31872, versus o percentual de submissões aceitas: 25.7%, das quais apenas 69.5% tiveram sucesso. Afinal, a solução parece simples e direta.Ugly numbers are numbers whose only prime factors are 2, 3 or 5.
The sequence: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 1500'th ugly number.
Input Output
There is no input to this program. Output should consist of a single line as shown below, with replaced by the number computed.
Sample output
The 1500'th ugly number is .
O que ocorre na verdade é que a solução ingênua é muito dispendiosa. Consome bastante tempo.
Bom, resolvi explorar um pouco sobre soluções em Haskell para o problema e vi que ele apresentava a oportunidade de fazermos um tour por algumas facilidades da linguagem.
A primeira versão, a bem ingênua, considera que os números feios formam uma lista, cujos elementos são oriundos da lista infinita [1.. ] e que satisfazem a propriedades de terem como únicos fatores primos os números 2, 3 e 5.
Assim, a primeira providência é definir a lista de números feios:
feios = [x | x<-[1..], feio x]
a segunda é definir o predicado feio x,
feio x = reduz (reduz (reduz x 2) 3) 5 == 1
Para tanto precisou-se construir uma função auxiliar, reduz x n, cuja finalidade é extrair de um número x as potências de um outro dado n.
reduz x n = if mod x n == 0 then reduz (div x n) n else x
agora, como temos uma lista como todos os feios, se desejamos conhecer o numero feio de ordem 1500, basta pedir ao sistema que determine, usando a operação de indexação (!!). O feio de ordem 1500 pode ser descrito por: feios!!1499, certo?
Podemos usar para outros feios também:
> feios!!0
1
(283 reductions, 525 cells)
> feios!!10
15
(5582 reductions, 8081 cells)
> feios!!100
1600
(662585 reductions, 962977 cells)
> feios!!200
16384
(6168873 reductions, 8984262 cells, 9 garbage collections)
>feios!!500
944784
(387151581 reductions, 568449819 cells, 577 garbage collections)
Veja que já começou a ficar complicado para o ambiente WinHugs. O esforço já está grande. Imagine se pedirmos feios!!1499.
Bom, disto podemos concluir que nossa solução ingênua não é muito boa.
Apesar disso, podemos aproveitar os ganhos que tivemos.
a) A função feio x, pode ser usada para verificar se um dado número é feio ou não, independente da função feios, o que ilustra bem o estilo da linguagem. Cada função pode ser usada independente.
> feio 944784
True
(1765 reductions, 2561 cells)
> feio 859963392
True
(2952 reductions, 4291 cells)
este último exemplo, é o feio de ordem 1500. Só para verificar se é feio ou não, até que o avaliador dá conta com facilidade.
b) A função feios, serve para obter não apenas o k-ésimo elemento, mas qualquer outro feio que desejarmos.
c) Podemos obter a lista do n primeiro feios. Na verdade, usando as funções take n e drop n podemos pegar qualquer pedaço da lista. Esta facilidade é possivel graças ao uso do conceito de lista infinita. Não precisamos saber antecipadamente quantos elementos iremos querer, isto é determinado em tempo de avaliação de uma expressão.
> take 10 feios
[1,2,3,4,5,6,8,9,10,12]
(278 reductions, 391 cells)
> take 10 (drop 10 feios) -- do 11 ao 20-éssimo
[15,16,18,20,24,25,27,30,32,36]
(451 reductions, 602 cells)
d) A função reduz, que nos serviu para para construir a feio x, serve na verdade para ser usada em outras situações. Como por exemplo, para verificar se um número é uma potência de outro.
> reduz 1024 3 == 1 -- 1024 é uma potência de 3?
False
(110 reductions, 152 cells)
> reduz 1024 2 == 1 -- 1024 é uma potência de 2?
True
(1189 reductions, 1697 cells)
Bom, podemos dar outros usos à função reduz, mas por enquanto ficamos assim.
Antes de terminar esta postagem, cabe ainda um comentário sobre a origem da inconveniência computacional introduzida pela especificação que foi aqui apresentada.
Podemos observar que para cada numero inteiro positivo precisamos verificar se ele satisfaz à condição de pertencer ou não aos feios. Assim, mesmo para aqueles que não são feio, precisamos fazer as reduções. A quantidade de feios é bem pequena em relação ao demais. No caso no número feio de 0rdem 1500, ele é o número 859.963.392 , quase 1 bilhão. Ou seja, para encontrar o número feio da ordem desejada foi necessário analisar cerca de 1 bilhão de números (10^9). Se para testar cada número gastarmos 0,001 seg precisaremos de 10^6 seg para encontrar o número desejado.
sexta-feira, 22 de junho de 2007
Um outra forma de entender o operador Foldl
Considere o conceito teórico da aplicação recorrente de uma função g a um determinado valor v, que podemos representar por:
(g v)*
por exemplo, seja g v = v + 1, então (g 3)* => 3, 4, 5, 6, 7, 8, 9, 10 ...
a aplicação de g prossegue enquanto o valor resultante de uma aplicação for um valor válido como entrada de g. Assim, dependendo de g e do valor inicial, a aplicação recorrente pode ser infinita.
O valor v pode ser estruturado. Vamos considerar uma situação mais complexa.
problema: definir uma função g que compute o somatório dos elementos de uma lista xs.
podemos definir
g xs = (g1 (0, xs) ) *
onde g1 (v1, xs) = (v1 + head xs, tail xs)
assim, g [1,3,5,7,9] = g1 (0, [1, 3, 5, 7, 9]) *
cuja seqüência de computação seria:
(0+1, [3, 5, 7, 9]),
(1 + 3, [5, 7, 9]),
(4+5, [7, 9]),
(9+7, [9]),
(16+9, []),
(26, ?)
Podemos entender o foldl como uma função de segunda ordem que tem comportamento semelhante a este conceito teórico acima apresentado.
O foldl funciona como a aplicação recorrente de uma função f a um par, onde o primeiro elemento é um valor x qualquer e o segundo uma lista xs. A cada passo, o foldl aplica a função f ao valor corrente de x e ao primeiro elemento de xs, para obter um novo valor para x. Sobre xs é aplicada a função tail xs.
ou seja foldl = ( (f x head xs, tail xs) )*
Por exemplo, para determinar o somatório dos elementos de uma lista xs, podemos escrever:
Vejamos que não é necessário que os elementos de xs sejam considerados na computação.
Por exemplo, vejamos uma função para descrever uma Progessão Aritmética, com primeiro termo a1, razão r e n termos.
pa a1 r n = foldl f ( r, [a1]) [2..n]
where
f (r, ys) b = ( r, ys ++ [last ys + r])
Para explicitar um pouco mais a expressividade computacional, vejamos a aplicação de uma função f a uma tripla, onde para cada elemento da tripla é definida uma função fi.
h a1 a2 a3 n = foldl f (a1, a2, a3) [2..n]
where
f (a1, a2, a3) b = ( f1 a1, f2 a2, f3 a3)
f1 x = x + 1
f2 y = y + 2
f3 z = z + 3
a aplicação de g prossegue enquanto o valor resultante de uma aplicação for um valor válido como entrada de g. Assim, dependendo de g e do valor inicial, a aplicação recorrente pode ser infinita.
O valor v pode ser estruturado. Vamos considerar uma situação mais complexa.
problema: definir uma função g que compute o somatório dos elementos de uma lista xs.
podemos definir
g xs = (g1 (0, xs) ) *
onde g1 (v1, xs) = (v1 + head xs, tail xs)
assim, g [1,3,5,7,9] = g1 (0, [1, 3, 5, 7, 9]) *
cuja seqüência de computação seria:
(0+1, [3, 5, 7, 9]),
(1 + 3, [5, 7, 9]),
(4+5, [7, 9]),
(9+7, [9]),
(16+9, []),
(26, ?)
Podemos entender o foldl como uma função de segunda ordem que tem comportamento semelhante a este conceito teórico acima apresentado.
O foldl funciona como a aplicação recorrente de uma função f a um par, onde o primeiro elemento é um valor x qualquer e o segundo uma lista xs. A cada passo, o foldl aplica a função f ao valor corrente de x e ao primeiro elemento de xs, para obter um novo valor para x. Sobre xs é aplicada a função tail xs.
ou seja foldl = ( (f x head xs, tail xs) )*
Por exemplo, para determinar o somatório dos elementos de uma lista xs, podemos escrever:
somatorio xs = foldl (+) 0 xs
uma aplicação desta definição, à lista [3, 8, 25, 1, 10], geraria as seguintes computações:
( 0, [3, 8, 25, 1, 10] )
( 0 + 3, [8, 25, 1, 10] )
( 0 + 3 + 8, [25, 1, 10] )
( 0 + 3 + 8 + 25, [1, 10] )
( 0 + 3 + 8 + 25 + 1, [10] )
( 0 + 3 + 8 + 25 + 1 + 10, [] )
(47, ?)
( 0, [3, 8, 25, 1, 10] )
( 0 + 3, [8, 25, 1, 10] )
( 0 + 3 + 8, [25, 1, 10] )
( 0 + 3 + 8 + 25, [1, 10] )
( 0 + 3 + 8 + 25 + 1, [10] )
( 0 + 3 + 8 + 25 + 1 + 10, [] )
(47, ?)
Vejamos que não é necessário que os elementos de xs sejam considerados na computação.
Por exemplo, vejamos uma função para descrever uma Progessão Aritmética, com primeiro termo a1, razão r e n termos.
pa a1 r n = foldl f ( r, [a1]) [2..n]
where
f (r, ys) b = ( r, ys ++ [last ys + r])
Para explicitar um pouco mais a expressividade computacional, vejamos a aplicação de uma função f a uma tripla, onde para cada elemento da tripla é definida uma função fi.
h a1 a2 a3 n = foldl f (a1, a2, a3) [2..n]
where
f (a1, a2, a3) b = ( f1 a1, f2 a2, f3 a3)
f1 x = x + 1
f2 y = y + 2
f3 z = z + 3
quinta-feira, 21 de junho de 2007
Criando listas com foldl
Vários exemplos apresentados na literatura produzem, com o foldl, elementos simples, como um número. Mas também podemos produzir listas.
No exemplo a seguir, desejamos produzir, a partir de uma lista xs, uma lista com o quadrado de cada número de xs.
A função quadaux opera produzindo uma nova lista, acrescentando ao final da lista xs o quadrado do número x dado, usando a operação "++" para concatenar duas listas. Primeiro produzimos uma lista com o quadrado do número dado e depois concatenamos.
quadaux xs x= xs ++ [x * x]
A função lquad aplica a função quadaux a cada elemento da lista de entrada xs, tendo como elemento neutro a lista vazia.
lquad xs = foldl quadaux [ ] xs
Vejamos a aplicação da função usando o ambiente HUGS
>lquad [1..10]
[1,4,9,16,25,36,49,64,81,100]
> lquad []
[]
O operador foldl
O mecanismo foldl é usado para aplicar uma função f, de forma recorrente, a todos os elementos de uma lista.
1) 0 [1..10]
2) 1 [2..10]
3) 3 [3..10]
4) 6 [4..10]
5) 10 [5..10]
...
n) 55 [ ]
O elemento base é escolhido de modo a não interferir no resultado final. Neste caso usamos o elemento neutro da adição, o zero.
Exemplo 2: a expressão foldl (*) 1 [1..10] , descreve o produtório dos 10 primeiros números inteiros positivos. O elemento base aqui usado foi o número 1, o elemento neutro da multiplicação.
Exemplo 3: Descrever a pertinência (ocorrência) de um elemento e a uma lista xs.
Apresentaremos 3 soluções para ilustrar diferentes possibilidades. Todas terão como base a aplicação recorrente da comparação do elemento e com um elemento da lista. Podemos observar aqui que a função a ser aplicada recorrentemente precisa de 3 parâmetros, entretanto o operador foldl só dá suporte a 2 parâmetros.
Vamos primeiro construir uma solução preliminar, em que o elemento que desejamos verificar a ocorrência é um valor constante. Tomemos 5 como este elemento constante.
Solução 0:
ocorre xs = foldl ocorreaux False xs
ocorreaux a b = a || (b==5)
a avaliação da função ocorre resultará em True se pelo menos um dos elementos da lista xs for igual a 5.
Usando a definição:
Main> ocorre [1..10]
True
Main> ocorre [50..100]
False
Main> ocorre []
False
Voltando à situação inicial, precisamos generalizar, usando um valor e ao invés da constante 5.
as soluções apresentadas a seguir apresentam diferentes maneiras de introduzir o terceiro parametro para a função ocorreaux.
Solução 1: usando uma definição local para ocorreaux.
ocorre' e xs = foldl ocorreaux False xs
where
ocorreaux a b = a || (b==e)
aqui o elemento e é usado diretamente da entrada pois sendo ocorreaux é definida localmente, sua definição compartilha as variáveis da interface de ocorre'.
Aplicando ocorre' obtemos:
Main> ocorre' 5 [1..20]
True
Main> ocorre' 5 [10..20]
False
Main> ocorre' 5 []
False
Solução 2: usando uma definição global para ocorreaux, com 3 parâmetros, combinado com a aplicação de ocorreaux ao primeiro parâmetro para obter uma função com apenas dois parametros a ser utilizada pelo foldl.
ocorre'' e xs = foldl (ocorreaux' e) False xs
ocorreaux' x a b = a || (b==x)
neste caso, a função f é realizada pela função (ocorreaux' e). Relembramos aqui que a aplicação de uma função a um valor, descreve uma nova função.
Aplicando ocorre'' obtemos:
Main> ocorre'' 5 [1..20]
True
Main> ocorre'' 5 [10..20]
False
Main> ocorre'' 5 []
False
Solução 3: Usando uma definição anônima para a função f através do operador lambda.
ocorre''' e xs = foldl (\a b -> a || (b==e)) False xs
relembramos que uma definição lambda representado por "->" tem duas partes, a introdução das variáveis, à esquerda de "->" e o corpo da função à sua direita.
Aplicando ocorre''' obtemos:
Main> ocorre''' 5 [1..20]
True
Main> ocorre''' 5 [10..20]
False
Main> ocorre''' 5 []
False
foldl função base lista
A função f tem necessariamente dois paramentos de entrada. O primeiro é do tipo do resultado que desejamos obter e o segundo do tipo dos elementos que constituem a lista.
Exemplo 1: a expressão foldl (+) 0 [1..10] , descreve o somatório dos 10 primeiros números inteiros positivos.
1) 0 [1..10]
2) 1 [2..10]
3) 3 [3..10]
4) 6 [4..10]
5) 10 [5..10]
...
n) 55 [ ]
O elemento base é escolhido de modo a não interferir no resultado final. Neste caso usamos o elemento neutro da adição, o zero.
Exemplo 2: a expressão foldl (*) 1 [1..10] , descreve o produtório dos 10 primeiros números inteiros positivos. O elemento base aqui usado foi o número 1, o elemento neutro da multiplicação.
Exemplo 3: Descrever a pertinência (ocorrência) de um elemento e a uma lista xs.
Apresentaremos 3 soluções para ilustrar diferentes possibilidades. Todas terão como base a aplicação recorrente da comparação do elemento e com um elemento da lista. Podemos observar aqui que a função a ser aplicada recorrentemente precisa de 3 parâmetros, entretanto o operador foldl só dá suporte a 2 parâmetros.
Vamos primeiro construir uma solução preliminar, em que o elemento que desejamos verificar a ocorrência é um valor constante. Tomemos 5 como este elemento constante.
Solução 0:
ocorre xs = foldl ocorreaux False xs
ocorreaux a b = a || (b==5)
a avaliação da função ocorre resultará em True se pelo menos um dos elementos da lista xs for igual a 5.
Usando a definição:
Main> ocorre [1..10]
True
Main> ocorre [50..100]
False
Main> ocorre []
False
Voltando à situação inicial, precisamos generalizar, usando um valor e ao invés da constante 5.
as soluções apresentadas a seguir apresentam diferentes maneiras de introduzir o terceiro parametro para a função ocorreaux.
Solução 1: usando uma definição local para ocorreaux.
ocorre' e xs = foldl ocorreaux False xs
where
ocorreaux a b = a || (b==e)
aqui o elemento e é usado diretamente da entrada pois sendo ocorreaux é definida localmente, sua definição compartilha as variáveis da interface de ocorre'.
Aplicando ocorre' obtemos:
Main> ocorre' 5 [1..20]
True
Main> ocorre' 5 [10..20]
False
Main> ocorre' 5 []
False
Solução 2: usando uma definição global para ocorreaux, com 3 parâmetros, combinado com a aplicação de ocorreaux ao primeiro parâmetro para obter uma função com apenas dois parametros a ser utilizada pelo foldl.
ocorre'' e xs = foldl (ocorreaux' e) False xs
ocorreaux' x a b = a || (b==x)
neste caso, a função f é realizada pela função (ocorreaux' e). Relembramos aqui que a aplicação de uma função a um valor, descreve uma nova função.
Aplicando ocorre'' obtemos:
Main> ocorre'' 5 [1..20]
True
Main> ocorre'' 5 [10..20]
False
Main> ocorre'' 5 []
False
Solução 3: Usando uma definição anônima para a função f através do operador lambda.
ocorre''' e xs = foldl (\a b -> a || (b==e)) False xs
relembramos que uma definição lambda representado por "->" tem duas partes, a introdução das variáveis, à esquerda de "->" e o corpo da função à sua direita.
Aplicando ocorre''' obtemos:
Main> ocorre''' 5 [1..20]
True
Main> ocorre''' 5 [10..20]
False
Main> ocorre''' 5 []
False
terça-feira, 19 de junho de 2007
Ordenação de Dados - II
O que resultaria da tentativa de usar a definição apresentada em "Ordenação de Dados - I" para uma lista com repetição?
> ordena [3,5, 4,2,6,5]
[2,3,4,5,
Program error: pattern match failure: head []
como o valor 5 se repete, e sua segunda ocorrência é desconsiderada, o elemento de índice 4 da lista ordenada não existe e assim, a lista de elementos para i igual a 4 é vazia e portanto a apliação de head [ ] falha.
Há como contornar a situação? A definição anterior pode ser estendida para contemplar a repetição?
Podemos voltar à definição apresentada na postagem anterior e verificar que na se deixarmos de usar a a operação head xs, na definição de "elempos i xs", teriamos como resultado uma lista de listas.
menores y xs = [x | x<-xs, x <>
qmen y xs = length (menores y xs)
elempos i xs = [ x | x <-xs, qmen x xs == i]
ordena xs = [ elempos i xs | i <- [0..length xs -1]]
> ordena [8, 7, 5 , 9, 20, 4, 2]
[[2],[4],[5],[7],[8],[9],[20]]
e agora, aplicando a definição para uma lista com repetição, obtemos:
> ordena [3,5, 3, 4,2,6,5, 3]
[[2],[3,3,3],[],[],[4],[5,5],[],[6]]
podemos observar que no caso de repetição, surgem n-1 listas vazias, correspondendo ao elementos que por serem repetidos se associam no índice anterior.
Estamos a um passo da solução. Podemos concatenar todas as listas e assim obtermos o resultado desejado.
ordena xs = concat [ elempos i xs | i <- [0..length xs -1]]
> ordena [3,5, 3, 4,2,6,5, 3]
[2,3,3,3,4,5,5,6]
> ordena [8, 7, 5 , 9, 20, 4, 2]
[2,4,5,7,8,9,20]
Como podemos agora refrasear a nossa descrição informal da solução?
> ordena [3,5, 4,2,6,5]
[2,3,4,5,
Program error: pattern match failure: head []
como o valor 5 se repete, e sua segunda ocorrência é desconsiderada, o elemento de índice 4 da lista ordenada não existe e assim, a lista de elementos para i igual a 4 é vazia e portanto a apliação de head [ ] falha.
Há como contornar a situação? A definição anterior pode ser estendida para contemplar a repetição?
Podemos voltar à definição apresentada na postagem anterior e verificar que na se deixarmos de usar a a operação head xs, na definição de "elempos i xs", teriamos como resultado uma lista de listas.
menores y xs = [x | x<-xs, x <>
qmen y xs = length (menores y xs)
elempos i xs = [ x | x <-xs, qmen x xs == i]
ordena xs = [ elempos i xs | i <- [0..length xs -1]]
> ordena [8, 7, 5 , 9, 20, 4, 2]
[[2],[4],[5],[7],[8],[9],[20]]
e agora, aplicando a definição para uma lista com repetição, obtemos:
> ordena [3,5, 3, 4,2,6,5, 3]
[[2],[3,3,3],[],[],[4],[5,5],[],[6]]
podemos observar que no caso de repetição, surgem n-1 listas vazias, correspondendo ao elementos que por serem repetidos se associam no índice anterior.
Estamos a um passo da solução. Podemos concatenar todas as listas e assim obtermos o resultado desejado.
ordena xs = concat [ elempos i xs | i <- [0..length xs -1]]
> ordena [3,5, 3, 4,2,6,5, 3]
[2,3,3,3,4,5,5,6]
> ordena [8, 7, 5 , 9, 20, 4, 2]
[2,4,5,7,8,9,20]
Como podemos agora refrasear a nossa descrição informal da solução?
segunda-feira, 18 de junho de 2007
Ordenação de Dados - I
Estamos interessados em descrever a ordenação de uma lista usando o mecanismo de List Comprehension.
Para principiantes, esta é uma atividade que traz bastante dificuldades. Há uma forte inclinação em descrever como ordenar uma lista, em detrimento da preocupação com a descrição do que é uma lista ordenada.
Vamos primeiro restringir nosso problema de ordenação: comecemos pela ordenação crescente de uma lista de números inteiros distintos.
No primeiro passo, a descrição informal, devemos encontrar uma propriedade de lista ordenada crescente de números inteiros distintos, que seja aderente ao mecanismo List Comprehension.
Descrevendo Informalmente:
Formalizando:
--
-- a ordenação de xs é uma lista formada por elempos i xs, tal que i pertence ao intervalo de
-- indexação de xs
--
ordena xs = [ elempos i xs | i <- [0..length xs - 1]]
--
-- o elemento de xs que tem posição i é o cabeça da lista dos elementos x pertencentes xs tal
-- que a quantidade de menores que x em xs é igual a i
--
elempos i xs = head [ x | x <-xs, qmen x xs == i]
--
-- a quantidade de menores que x em xs é o tamanho da lista de menores
--
qmen y xs = length (menores y xs)
--
-- a lista de elementos de xs menores que y é formada pelos elementos de xs que satisfazem a
-- propriedade: y <>
--
menores y xs = [x | x<-xs, x <>
vejamos alguns exemplos de uso, rodando em HUGS para windows:
Testando a Solução
> ordena [7, 3, 5, 2, 9, 4, 6, 1, 10, 0]
[0,1,2,3,4,5,6,7,9,10]
> ordena [100]
[100]
> ordena []
[]
> ordena [10,9..0]
[0,1,2,3,4,5,6,7,8,9,10]
Alguns possíveis prosseguimentos:
Para principiantes, esta é uma atividade que traz bastante dificuldades. Há uma forte inclinação em descrever como ordenar uma lista, em detrimento da preocupação com a descrição do que é uma lista ordenada.
Vamos primeiro restringir nosso problema de ordenação: comecemos pela ordenação crescente de uma lista de números inteiros distintos.
No primeiro passo, a descrição informal, devemos encontrar uma propriedade de lista ordenada crescente de números inteiros distintos, que seja aderente ao mecanismo List Comprehension.
Descrevendo Informalmente:
- em uma lista ordenada crescente de números distintos, o índice de um elemento é igual à quantidade de elementos menores que ele na referida lista;
- que pode ser reescrita como: para cada índice i, de uma lista ordenada, o i-ésimo elemento é aquele que possui exatamente i elementos menores que ele na lista.
Formalizando:
--
-- a ordenação de xs é uma lista formada por elempos i xs, tal que i pertence ao intervalo de
-- indexação de xs
--
ordena xs = [ elempos i xs | i <- [0..length xs - 1]]
--
-- o elemento de xs que tem posição i é o cabeça da lista dos elementos x pertencentes xs tal
-- que a quantidade de menores que x em xs é igual a i
--
elempos i xs = head [ x | x <-xs, qmen x xs == i]
--
-- a quantidade de menores que x em xs é o tamanho da lista de menores
--
qmen y xs = length (menores y xs)
--
-- a lista de elementos de xs menores que y é formada pelos elementos de xs que satisfazem a
-- propriedade: y <>
--
menores y xs = [x | x<-xs, x <>
vejamos alguns exemplos de uso, rodando em HUGS para windows:
Testando a Solução
> ordena [7, 3, 5, 2, 9, 4, 6, 1, 10, 0]
[0,1,2,3,4,5,6,7,9,10]
> ordena [100]
[100]
> ordena []
[]
> ordena [10,9..0]
[0,1,2,3,4,5,6,7,8,9,10]
Alguns possíveis prosseguimentos:
- e se a a lista possui elementos repetidos?
- e se a ordem desejada for decrescente?
- e se a lista for formada por elementos de outro tipo?
Assinar:
Postagens (Atom)
