Seznam čísel

Definujte rostoucí seznam přirozených čísel která jsou ve tvaru 2i3j5k pro libovolná přirozená i, j, k (včetně nul).

cisla :: [Integer]

Počet bodů je 2.4. Pokud se vám nelíbí generování nekonečného seznamu, omezená varianta je za 2 body.

cislaDoHodnoty :: Integer -> [Integer]

Složitost

Pozor: pro plný počet bodů musí složitost vygenerování prvních N čísel být O(N) (předpokládejte konstantní čas na základní aritmetické operace).

Rozhodně se nesnažte způsobem filter jeSpravne [1..] nebo cokoliv s asmyptoticky podobnou složitostí.

Příklady:

 >	take 20 cisla -- nebo: cislaDoHodnoty 38
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]


 >	cisla !! 100000
290237644800000000000000000000000000000

Řešení

cisla = 1 : merge3 (map (2*) cisla) (map (3*) cisla) (map (5*) cisla)

-- | sleje tři neklesající posloupnosti a maže duplikáty
merge3 (a:as) (b:bs) (c:cs)
	| a<b && a<c = a : merge3 as (b:bs) (c:cs)
	| b<a && b<c = b : merge3 (a:as) bs (c:cs)
	| c<a && c<b = c : merge3 (a:as) (b:bs) cs
	| a==b || a==c = merge3 as (b:bs) (c:cs)
	| b==c = merge3 (a:as) bs (c:cs)

Složitost: sdílená posloupnost cisla se líně generuje pomocí svého už vygenerovaného prefixu. Líné hodnoty se poprvé vyhodnotí až když jsou potřeba, ale nejvýše jednou (výsledek se zapamatuje). Každá hodnota do výsledku se vygeneruje nejvýše třikrát a pak projde mergem.