module Exercise_14 where
import qualified Data.List
import Test.QuickCheck


{---------------------------------------------------------------------}
{- Aufgabe G14.1 -}

delete :: Eq a => a -> [a] -> [a]
delete = Data.List.delete {- falsche Implementierung -}


-- Reimplementierung: Vollständig?
prop_reimplement x xs =
        delete x xs == filter (/=x) xs

-- Induktive Tests: Vollständig
prop_nil :: Int -> Bool
prop_nil x = null (delete x [])

prop_cons :: Char -> Char -> [Char] -> Bool
prop_cons x y xs =
        delete x (y : xs) ==
                if x == y then delete x xs
                else y : delete x xs

-- Kombinatorische Tests: Vollständig
prop_single x y =
        delete x [y] ==
                if x == y then []
                else [y]

prop_append x xs ys =
        delete x (xs ++ ys) == delete x xs ++ delete x ys

-- Spezifische Tests: Unvollständig
prop_noelem x xs = x `notElem` delete x xs

prop_neutrality x xs = x `notElem` xs ==> xs == delete x xs

prop_nothingNew x xs = delete x xs `subseq` xs
        where
        subseq = undefined

prop_length x xs =
        length xs - length [c | c <- xs, c == x] == length (delete x xs)

prop_idem x xs = d == delete x d
        where d = delete x xs

-- Beispiele: Sehr fragwürdig
prop_example x = delete x (replicate 10 x) == []



{---------------------------------------------------------------------}
{- Aufgabe G14.2 -}

-- Beispiele zur Endrekursion
sum1 :: Int -> Int
sum1 0 = 0
sum1 n = n + sum1 (n - 1)
{-
sum1 3 = 3 + sum1 2
    sum1 2 = 2 + sum1 1
        sum1 1 = 1 + sum1 0
            sum1 0 = 0
        sum1 1 = 1 + 0
               = 1
    sum1 2 = 2 + 1
           = 3
sum1 3 = 3 + 3
       = 6
-}

sum2 :: Int -> Int
sum2 = sum2_end 0
    where
        sum2_end acc 0 = acc
        sum2_end acc n = sum2_end (acc + n) (n - 1)
{-
sum2 3 = sum2_end 0 3
       = sum2_end 3 2
       = sum2_end 5 1
       = sum2_end 6 0
       = 6

-}


-- Concats
-- Nicht Endrekursiv
concat' :: [[a]] -> [a]
concat' [] = []
concat' (xs:xss) = xs ++ concat' xss

-- O(n)
concat'' :: [[a]] -> [a]
concat'' yss = go [] (reverse yss)
    where
    go acc [] = acc
    go acc (xs:xss) = go (xs ++ acc) xss

-- O(n^2)
concat''' :: [[a]] -> [a]
concat''' = go []
    where
    go acc [] = acc
    go acc (xs:xss) = go (acc ++ xs) xss

-- Mit Fold
concat'''' :: [[a]] -> [a]
concat'''' = foldr (++) []



{---------------------------------------------------------------------}
{- Aufgabe G14.3 -}

{-

map (*2) (1 : threes) !! 1
= ((*2) 1 : map (*2) threes) !! 1
= map (*2) threes !! 0
= map (*2) (3: threes) !! 0
= ((*2) 3 : map (*2) threes) !! 0
= (*2) 3
= 3 * 2
= 6


((\f -> \x -> x + f 2) (\y -> y * 2)) (3 + 1)
= (\x -> x + (\y -> y * 2) 2) (3 + 1)
= (3 + 1) + (\y -> y * 2) 2
= 4 + (\y -> y * 2) 2
= 4 + 2 * 2
= 4 + 4
= 8


filter (/=3) threes
= filter (/=3) (3 : threes)
= filter (/=3) threes
--> terminiert nicht

threes = 3 : threes

-}



{---------------------------------------------------------------------}
{- Aufgabe H14.1 -}

{- Type me! -}



{---------------------------------------------------------------------}
{- Aufgabe H14.2 -}

{- Proof me! -}



{---------------------------------------------------------------------}
{- Aufgabe H14.3 -}

filterMap :: (a -> Maybe b) -> [a] -> [b]
filterMap = undefined