module Exercise_2 where
import Test.QuickCheck
import Data.List

{---------------------------------------------------------------------}
{- Aufgabe G2.1 -}
all_sums :: [Integer] -> [Integer] -> [Integer]
all_sums xs ys = [x + y | x <- xs, y <- ys]


evens :: [Integer] -> [Integer]
evens xs = [x | x <- xs, even x]


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, even (x+y)]



{---------------------------------------------------------------------}
{- Aufgabe G2.2 -}
union'' :: [Integer] -> [Integer] -> [Integer]
union'' xs ys = xs ++ ys


intersection :: [Integer] -> [Integer] -> [Integer]
intersection xs ys = [x | x <- xs, x `elem` ys]
-- Alternativ ohne elem:
-- 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 = [y | y <- xs, y == x] /= [] 


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



{---------------------------------------------------------------------}
{- Aufgabe G2.3 -}
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]



{---------------------------------------------------------------------}
{- Aufgabe G2.4 -}
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 = error "Postive n only"
        | even n = pow2 (n `div` 2) ^ 2
        | otherwise = 2 * pow2 (n - 1)



{---------------------------------------------------------------------}
{- Aufgabe G2.5 -}
reachable :: [(Integer, Integer)] -> Integer -> [(Integer, Integer)]
reachable graph 0 = nub $ concat [[(u, u), (v, v)] | (u, v) <- graph]
reachable graph 1 = graph
reachable graph n | n > 0 = [(u, x) | (u, v) <- graph, (w, x) <- reachable graph (n-1), v == w]



{---------------------------------------------------------------------}
{- Aufgabe H2.1 -}
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]



{---------------------------------------------------------------------}
{- Aufgabe H2.2 -}
lookupTab :: [Integer] -> [(Integer, [Char])] -> [[[Char]]]
lookupTab keys tab = [[v | (k,v) <- tab, key == k] | key <- keys]



{---------------------------------------------------------------------}
{- Aufgabe H2.3 -}
wordsOfLength :: [Char] -> Integer -> [[Char]]
wordsOfLength alphabet 0 = [[]]
wordsOfLength alphabet n = [[a] ++ s | a <- alphabet, s <- wordsOfLength alphabet (n - 1)]



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

perms' :: [Char] -> [[Char]]
perms' "" = [""]
perms' xs = [ys ++ [y] | y <- sort $ nub xs, ys <- perms' $ delete y xs]

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