definindo sublistas com Foldl

Problema 1 : Dada uma lista xs, descreva a sublista de xs formada apenas por números pares:

pares ls = foldl fp [] ls
fp xs y = xs ++ (if mod y 2 == 0 then [y] else [])

Uma aplicação da função:

Main> pares [6, 5, 3, 512, 9, 308, 124]
[6,512,308,124]

observe que o elemento final é obtido pela construção de uma lista que usa a lista obtida na interação anterior e o resultado de operar o elemento da lista de entrada com um um valor interior, neste caso a constante 2.

Um trace da execução:

1) foldl fp [ ] [6, 5, 3, 512, 9, 308, 124]
2) foldl fp [ 6] [5, 3, 512, 9, 308, 124]
3) foldl fp [ 6] [5, 3, 512, 9, 308, 124]
4) foldl fp [ 6] [3, 512, 9, 308, 124]
5) foldl fp [ 6] [512, 9, 308, 124]
6) foldl fp [ 6, 512] [9, 308, 124]
7) foldl fp [ 6, 512] [308, 124]
8) foldl fp [ 6, 512, 308] [124]
9) foldl fp [ 6, 512, 308, 124] [ ]

Se aplicarmos a função pares a intervalos de números inteiros podemos obter a sublista de números pares pertencentes ao intervalo.

por exemplo,

Main> pares [1..10]
[2,4,6,8,10]

Problema 2 :Desejamos obter a sublista de xs formada pelos elementos de xs que são divisíveis por um dado valor v.

divisiveis v ls = foldl fd ( [], v) ls
fd (xs,v) y = (xs ++ (if mod v 2 == 0 then [y] else []), v)

Main> divisiveis 3 [1..20]
([3,6,9,12,15,18], 3)

A função define um par, com o resultado mesmo e um dado de entrada que foi incorporado.

Isto pode ser eleminado se o valor v for passado para a função auxiliar através do contexto, usando a cláusula where

Fica assim:

divisiveis' v ls = foldl fd [] ls
where
fd xs y = xs ++ (if mod y v == 0 then [y] else [])

e veja o que podemos obter:

Main> divisiveis' 3 [1..50]
[3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48]

Uma outra observação importante.

A função foldl, opera sobre todos elementos da lista, ainda que não estejamos interessados, ou seja, não temos como explicitar que desejamos interromper o processamento da lista ls, informada em foldl f x xs.

Vejamos um novo exemplo que ilustra a situação.

Problema 3: Desejamos descobrir o preço de um produto p em uma determinada lista de pares (produto, preço).

Ainda que saibamos que cada produto ocorre apenas uma vez na lista, não temos como descrever esta informação.

Assim, não temos como dizer diretamente que ao encontrar o produto na lista desejamos interromper a busca e retornar este valor. Da mesma forma, não temos como guardar este valor diretamente, apesar de podermos incorporar informação do elemento que é atualizado em um ciclo e que serve de entrada para o próximo.

Solução 1

pegapreco x xs = foldl app (0,x,True) xs
app (r,p,controle) (c,preco) = if controle
then if p == c then (preco, p, False)
else (r,p,controle)
else (r,p,controle)

Solução 2

--
-- solucao sem controle, usando lista
--

pegapreco' x xs = foldl app' ([],x) xs
app' (rs,p) (c,preco) = (rs ++ (if p == c then [preco] else []),p)

Main> pegapreco' "cafe" [ ("nada1",50),("nada2",85),("nada3",35),("cafe",5),("nada4",25),("nada5",15)]

([5],"cafe")

Main> pegapreco' "nada"
[ ("nada1",50),("nada2",85),("nada3",35),("cafe",5),("nada4",25),("nada5",15)]

([],"nada")

Main> pegapreco' "nada1" [ ("nada1",50),("nada2",85),("nada3",35),("cafe",5),("nada4",25),("nada1",15)]

([50,15],"nada1")

Números Feios - V

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.

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".

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, 372993 cells)
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 ⁴
células: 568.449.819 versus 3.717 um ganho da ordem de 10 ⁵
garbage: 577 versus 0

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.

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

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.

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:

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.

> primo'' 1048583
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)

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".

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:

Como podemos usar a função fprimos para verificar se um número é primo?