import Prelude hiding (iterate)
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib x = fib (x-1) + fib (x-2)
fibs2 :: [Integer]
fibs2 = [fib x | x <- [0..]]
fibs3 = map fib [0..]
fibs4 :: [Integer]
fibs4 = [0,1]++fibHelp 0 1
where fibHelp x y = (x+y) : fibHelp y (x+y)
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
| x < y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
primes :: [Integer]
primes = sieve [2..]
sieve :: [Integer] -> [Integer]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]
primepowers :: Integer -> [Integer]
primepowers 1 = primes
primepowers n = map (^n) primes `merge` primepowers (n-1)
--sum [] = 0
--sum (x:xs) = x + sum xs
--sum xs = foldr (+) xs
primepowers2 n = foldr merge [] [map (^i) primes | i <- [1..n]]
intersect :: (Ord t) => [t] -> [t] -> [t]
intersect (x:xs) (y:ys)
| x == y = x : intersect xs ys
| x < y = intersect xs (y:ys)
| otherwise = intersect (x:xs) ys
intersect xs ys = []
intersectAll :: (Ord t) => [[t]] -> [t]
--intersectAll (x:xs) = foldr intersect x xs
intersectAll xs = foldr1 intersect xs
--commonMultiples = [45,90..]
-- where x = intersectAll ["foo"]
commonMultiples a b c = intersectAll [[a,2*a..],[b,2*b..],[c,2*c..]]
iterate f x0 = x0 : iterate f (f x0)
rand :: [Integer]
rand = iterate (\x -> (a * x + b) `mod` m) 32
where m = 2 ^ 16
a = 25173
b = 13849
x_0 = 32
toCoin :: [Integer] -> [Bool]
toCoin = map (>= 2^15)
neumann :: [Bool] -> [Bool]
neumann (x:y:xs)
| x == y = neumann xs
| otherwise = x : neumann xs
bias :: [Bool] -> [Bool]
bias (x:y:xs) = (x && y) : bias xs