fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fib 0 = 0
fib 1 = 1
fib x = fib (x-1) + fib (x-2)
fibs2 = map fib [0..]
fibs3 = map fst $ iterate (\(x,y) -> (y,x+y)) (0,1)
fibs4 = go 0 1
where go x y = x : go y (x+y)
merge [] ys = ys
merge xs [] = xs
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 1 = primes
--primepowers n = merge (map (^n) primes) (primepowers (n-1))
primepowers n = foldr merge [] [map (^i) primes | i <- [1..n]]
--primepowers = foldr merge [] [[p^i | p <- primes] | i <- [1..]]
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 _ _ = []
intersectAll :: (Ord t) => [[t]] -> [t]
--intersectAll (x:xs) = foldr intersect x xs
intersectAll [] = error "Empty list"
intersectAll xs = foldr1 intersect xs
--commonMultiples = [105,210..]
-- where x = intersectAll [[]]
--commonMultiples a b c = intersectAll [[x * i | i <- [1..]] | x <- [a,b,c]]
commonMultiples a b c = intersectAll [[a,a+a..], [b,b+b..], [c,c+c..]]
random :: Integer
random = 3
rand :: [Integer]
rand = iterate (\x -> (a*x + b) `mod` m) x0
where m = 2 ^ 16
a = 25173
b = 13849
x0 = 32
toCoin :: [Integer] -> [Bool]
--toCoin xs = map even xs
toCoin xs = map (> 2^15) xs
--id x = x
neumann (x:y:xs)
| x == y = neumann xs
| otherwise = x : neumann xs
--bias (True:True:xs) = True : bias xs
--bias (_:_:xs) = False : bias xs
bias (x:y:xs) = (x && y) : bias xs