module Sol_Exercise_2 where
import Test.QuickCheck
import Data.List

{- G1 -}

all_sums :: [Integer] -> [Integer] -> [Integer]
all_sums xs ys = [x + y | x <- xs, y <- ys]

evens :: [Integer] -> [Integer]
evens xs = [x | x <- xs, x `mod` 2 == 0]

n_lists :: [Integer] -> [[Integer]]
n_lists xs = [[1..x] | x <- xs]

all_even_sum_lists :: [Integer] -> [Integer] -> [[Integer]]
all_even_sum_lists xs ys = [[1..x+y] | x <- xs, y <- ys, (x + y) `mod` 2 == 0]


{- G2 -}
union :: [Integer] -> [Integer] -> [Integer]
union xs ys = xs ++ ys

intersection :: [Integer] -> [Integer] -> [Integer]
intersection xs ys = [x | x <- xs, y <- ys, x == y]

diff :: [Integer] -> [Integer] -> [Integer]
diff xs ys = [x | x <- xs, not (x `elem` ys)]

elem' :: Integer -> [Integer] -> Bool
elem' x xs = not (null [y | y <- xs, y == x])

union' :: [Integer] -> [Integer] -> [Integer]
union' xs ys = xs ++ diff ys xs


{- G3 -}
eq_frac :: (Integer,Integer) -> (Integer,Integer) -> Bool
eq_frac (a,b) (c,d) = a*d == c * b

intersection_frac :: [(Integer,Integer)] -> [(Integer,Integer)] -> [(Integer,Integer)]
intersection_frac xs ys = [x | x <- xs, y <- ys, x `eq_frac` y]


{- G4 -}

pow2_slow :: Integer -> Integer
pow2_slow 0 = 1
pow2_slow n | n > 0 = 2 * pow2_slow (n - 1)

pow2 :: Integer -> Integer
pow2 0 = 1
pow2 n | n < 0 = undefined
       | n `mod` 2 == 0 = k * k
       | otherwise = 2 * pow2 (n - 1)
     where k = pow2 (n `div` 2)

{- G5 -}

reachable :: [(Integer, Integer)] -> Integer -> [(Integer, Integer)]
reachable graph 0 = [(u, u) | u <- nub (concat [[fst p, snd p] | p <- graph])]
reachable graph 1 = graph
reachable graph n = [(fst p1, snd p2) | p1 <- graph, p2 <- reachable graph (n - 1), snd p1 == fst p2]


{- H1 -}

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

factorials :: [Integer] -> [Integer]
factorials ns = [factorial n | n <- ns, n >= 0]

prop_factorialsDistrib cs cs' =
  factorials (cs ++ cs') == factorials cs ++ factorials cs'
prop_factorialsOne n = factorials [n] == (if n < 0 then [] else [factorial n])
prop_factorialsNil = factorials [] == []

count :: [Char] -> Char -> Integer
count cs c = genericLength [c' | c' <- cs, c' == c]

count' :: [Char] -> Char -> Integer
count' cs c = sum [1 | c' <- cs, c' == c]


{- H2 -}

lookupTab :: [Integer] -> [(Integer, [Char])] -> [[[Char]]]
lookupTab keys tab = [[v | (k,v) <- tab, key == k] | key <- keys]


{- H3 -}

wordsOfLength :: [Char] -> Integer -> [[Char]]
wordsOfLength alphabet 0 = [[]]
wordsOfLength alphabet n = [[a] ++ s | a <- alphabet, s <- wordsOfLength alphabet (n - 1)]


{- H4 -}

{-WETT-}
perms :: [Char] -> [[Char]]
perms xs | xs == "" = [""]
         | otherwise =
             reverse (sort (nub ([ys ++ [y] |
               y <- xs, ys <- perms (delete y xs)])))
{-TTEW-}

{-WETT-}
perms' :: [Char] -> [[Char]]
perms' xs =
  max [""] [y : ys | y <- reverse $ sort $ nub xs, ys <- perms' $ delete y xs]
{-TTEW-}