import List   -- for sort

-- Some possible solutions for s2006

-- Question 1:

primes = sieve [2..]
sieve (x:xs) = x:sieve [y | y <- xs, y `mod` x > 0 ]

twinprimes = filter twin (zip primes (tail primes))
twin (a,b) = b == a+2



statistics [] = []
statistics (x:xs) = stats x 1 (sort xs)

stats x k (y:ys)
  | x == y    = stats x (k+1) ys
  | otherwise = (x,k):stats y 1 ys

stats x k [] = [(x,k)]



data TTree a = TLeaf a | TNode (TTree a) (TTree a) (TTree a)

depths t = statistics (depths' t 0 [])

depths' (TLeaf x) k l = k:l
depths' (TNode t1 t2 t3) k l = k:l3
  where
    k' = k+1
    l1 = depths' t1 k' l
    l2 = depths' t2 k' l1
    l3 = depths' t3 k' l2

-- Another (better - linear running time and works for infinite trees)
-- solution is one based on BFS instead (not done here)).

-- test trees

t1 = TLeaf 1
t2 = TNode t1 t1 t1
t3 = TNode t2 t1 t1
t4 = TNode t1 t2 t2
t5 = TNode t2 t3 t4



-- For question 3:

m f g [] = []
m f g (x:xs) = f x : m g f xs

-- For question 4:

sum1, sum2:: Num a => [a] -> a

sum1 []     = 0
sum1 (x:xs) = x + sum1 xs

sum2 = foldr' (+) 0

foldr' f e []     = e
foldr' f e (x:xs) = f x (foldr' f e xs)