module Exercise_5 where
import Data.Maybe
import Data.List
import Test.QuickCheck

{- Library DO NOT CHANGE -}
type State = Integer
type DA = (State, State -> Char -> State, State -> Bool)
type ListDA = (State, [((State, Char), State)], [State])

a :: DA
a = (0, delta, (==1))
  where
    delta 0 'a' = 1
    delta 1 'a' = 1
    delta 2 'a' = 1
    delta 0 'b' = 2
    delta 1 'b' = 2
    delta 2 'b' = 2

toDA :: ListDA -> DA
toDA (start, delta, final) = (start, deltaFun delta, (`elem` final))
  where deltaFun dl = curry (fromMaybe 0 . flip lookup dl)
{- End Library -}


{---------------------------------------------------------------------}
{- Aufgabe G5.1 -}

iter :: Int -> (a -> a) -> a -> a
iter n f x
        | n <= 0 = x
        | otherwise = iter (n - 1) f (f x)


pow :: Int -> Int -> Int
pow n k = iter k (\x -> x*n) 1


drop' :: Int -> [a] -> [a]
drop' n xs = iter n tail xs


replicate' :: Int -> a -> [a]
replicate' n x = iter n (x:) []



{---------------------------------------------------------------------}
{- Aufgabe G5.2 -}

{- Fold-Beispiel anhand der Summenfunktion -}

sum' :: [Integer] -> Integer
sum' [] = 0
sum' (x:xs) = x + sum' xs


sum'' :: [Integer] -> Integer
sum'' xs = sum_acc xs 0
        where
        sum_acc :: [Integer] -> Integer -> Integer 
        sum_acc [] acc = acc
        sum_acc (x:xs) acc = sum_acc xs (x+acc)

sum_fold :: [Integer] -> Integer
--sum_fold xs = foldr (\x acc -> x + acc) 0 xs
sum_fold xs = foldr (+) 0 xs

{-----}

partition_rec :: (a -> Bool) -> [a] -> ([a], [a])
partition_rec p xs = partition_rec' xs ([], [])
        where
        partition_rec' [] (ts, fs) = (reverse ts, reverse fs)
        partition_rec' (x:xs) (ts, fs) =
                if p x then partition_rec' xs (x:ts, fs)
                else partition_rec' xs (ts, x:fs)


partition_foldr :: (a -> Bool) -> [a] -> ([a], [a])
partition_foldr p xs = foldr partition_foldr' ([], []) xs
        where
        partition_foldr' x (ts, fs) =
                if p x then (x:ts, fs)
                else (ts, x:fs)


partition_filter :: (a -> Bool) -> [a] -> ([a], [a])
--partition_filter p xs = (filter p xs, filter (\x -> not(p(x))) xs)
partition_filter p xs = (filter p xs, filter (not . p) xs)


prop_partition_foldr_even xs =
        partition_foldr even xs == partition even xs


prop_partition_distrib_even xs ys =
        partition even (xs ++ ys) == (ts ++ ts', fs ++ fs')
        where
        (ts, fs) = partition even xs
        (ts', fs') = partition even ys


zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] [] = []
zipWith' f (x:xs) (y:ys) = (f x y) : zipWith' f xs ys



{---------------------------------------------------------------------}
{- Aufgabe G5.3 -}

-- Beide Identitäten
lambda_1 = (\xs -> foldr (++) [] (map (\x -> [x]) xs))
lambda_2 = (\gg xx yy -> head (tail (zipWith gg [ xx , xx ] [ yy , yy ])))



{---------------------------------------------------------------------}
{- Aufgabe G5.4 -}

-- Unendliche Liste mit Nullen
zeros :: [Int] 
zeros = 0 : zeros 


length' :: [a] -> Int 
length' [] = 0 
length' (_:xs) = 1 + length' xs 


-- Terminiert immer.
-- m <= n: 0
-- m >  n: 1
h :: Integer -> Integer -> Integer
h m n
        | m == n = 0
        | m < n = h m (n - 1)
        | m >= n = h n m + 1



{---------------------------------------------------------------------}
{- Aufgabe H5.1 -}

fixpoint :: (a -> a -> Bool) -> (a -> a) -> a -> a
fixpoint = undefined


cents :: [Integer] -> [Integer]
cents = undefined


trancl :: [(Integer, Integer)] -> [(Integer, Integer)]
trancl = undefined



{---------------------------------------------------------------------}
{- Aufgabe H5.2 -}

advance :: DA -> State -> String -> State
advance = undefined


prop_advance_empty :: ListDA -> State -> Bool
prop_advance_empty = undefined


prop_advance_single :: ListDA -> State -> Char -> Bool
prop_advance_single = undefined


prop_advance_concat :: ListDA -> State -> String -> String -> Bool
prop_advance_concat = undefined


accept :: DA -> String -> Bool
accept = undefined


reachableStates :: DA -> State -> [Char] -> [State]
reachableStates = undefined



{---------------------------------------------------------------------}
{- Aufgabe H5.3 -}

{-WETT-}
quasiSubseq :: Eq a => [a] -> [a] -> Bool
quasiSubseq xs ys = undefined
{-TTEW-}