module Exercise_12 where


{---------------------------------------------------------------------}
{- Aufgabe G12.1 -}

{-

Ausdruck: 1 + (2 * 3)
(2 * 3)                         Innermost
1 + (2 * 3)                     Outermost


Ausdruck: (1 + 2) * (2 + 3)
(1 + 2)                         Innermost
(2 + 3)                         Innermost
(1 + 2) * (2 + 3)               Outermost


Ausdruck: fst (1 + 2, 2 + 3)
(1 + 2)                         Innermost
(2 + 3)                         Innermost
fst (1 + 2, 2 + 3)              Outermost


Ausdruck: fst (snd (1, 2 + 3), 4)
(2 + 3)                         Innermost
snd (1, 2 + 3)
fst (snd (1, 2 + 3), 4)         Outermost


Ausdruck: (\x -> 1 + x) (2 * 3)
(2 * 3)                         Innermost
(\x -> 1 + x) (2 * 3)           Outermost

-}



{---------------------------------------------------------------------}
{- Aufgabe G12.2 -}

inf :: a -> [a]
inf x = x : inf x

f :: [Int] -> [Int] -> [Int] -> Int
f (x:xs) (y:ys) zs | x > y = y
f (x1:x2:xs) ys (z:zs) = x1

a = f (inf (1+0)) (inf (1+1)) (inf (1+2))
{-
f (inf (1+0)) (inf (1+1)) (inf (1+2))
-> f ((1+0) : inf (1+0)) ((1+1) : inf (1+1)) (inf (1+2))
-> f (1 : inf 1) (2 : inf 2) (inf (1+2))
-> f (1 : 1 : inf 1) (2 : inf 2) ((1+2) : inf (1+2))
-> 1
-}

b = f (inf (1+2)) (inf (1+1)) (inf (1+0))
{-
f (inf (1+2)) (inf (1+1)) (inf (1+0))
-> f ((1+2) : inf (1+2)) ((1+1) : inf (1+1)) (inf (1+0))
-> f (3 : inf 3) (2 : inf 2) (inf (1+0))
-> 2
-}

c = f (inf (1+0)) [] (inf (1+1))
{-
f (inf (1+0)) [] (inf (1+1))
-> f ((1+0) : inf (1+0)) [] (inf (1+1))
-> f ((1+0) : (1+0) : inf (1+0)) [] ((1+1) : inf (1+1))
-> (1+0)
-> 1
-}

{- Musterlösung -}
{- Aufruf:
 -    f (inf (1+0)) (inf (1+1)) (inf (1+2))
 - Argumente
 -   inf (1+0) ~~> 1 : 1: inf 1
 -   inf (1+1) ~~> 2 : inf 2
 -   inf (1+2) ~~> (1+2) : inf (1+2)
 - Warum?
 -  Zur Auswertung von f wird zunächst Pattern Matching gemacht gegen die erste
 -  Regel gemacht. Haskell muss also feststellen, ob das erste und zweite
 -  Argument die Form _:_ (statt []) hat. Das dritte Argument ist nur eine
 -  Variable, hier muss also noch nichts ausgewertet werden.
 -    inf (1+0) ~> (1+0) : inf (1+0)
 -    inf (1+1) ~> (1+1) : inf (1+1)
 -    inf (1+2) ~> inf(1+2)
 -  Jetzt wird (unter anderem) x = 1+0 und y = 1+1 gebunden.
 -  In einem zweiten Schritt muss "x > y" getestet werden, dazu müssen x und y
 -  ausgewertet werden:
 -    (1+0) : inf (1+0) ~> 1 : inf 1
 -    (1+1) : inf (1+1) ~> 2 : inf 2
 -    inf (1+2) ~> inf(1+2)
 -  Warum wurden jetzt beide 1+0 zu 1 (bzw. beide 1+1 zu 2 ausgewertet)? Weil es
 -  jeweils der selbe (nicht nur der gleiche Ausdruck war).
 -
 -  "x > y" ist False, deswegen muss jetzt noch die zweite Regel getestet werden.
 -  Dafür ist es notwendig, das erste Argument zu der Form _:_:_ und das dritte
 -  Argument zu der Form _:_ auszuwerten:
 -    1 : inf 1 ~> 1 : 1 : inf 1
 -    2 : inf 2 ~> 2 : inf 2
 -    inf (1+2) ~> (1+2) : inf (1+2)
 -  Der Rückgabewert ist jetzt 1, was schon vollständig ausgewertet ist und daher
 -  für die Anzeige nicht weiter ausgewertet werden muss.
 -}

{- Aufruf:
 -   f (inf(1+2)) (inf(1+1)) (inf(1+0))
 - Argumente:
 -   inf (1+2) ~> 3 : inf 3
 -   inf (1+2) ~> 2 : inf 2
 -   inf (1+0) ~> inf (1+0)
 - Ähnlich wie oben, nur schlägt hier der Test "x > y" nicht fehl, daher wird das
 - dritte Argument nie ausgewertet.
 -}

{- Aufruf
 -   f (inf (1+0)) [] (inf 0)
 - Argumente:
 -   inf (1+0) ~> 1 : inf 1
 -   inf 0 ~> 0 : inf 0
 - Hier wird der Test "x > y" nie erreicht (denn das zweite Argument hat die Form []).
 - 1+0 wird dennoch zu 1 ausgewertet, da es der Rückgabewert der Funktion ist und daher
 - ausgewertet werden muss, um angezeigt zu werden.
 -}



{---------------------------------------------------------------------}
{- Aufgabe G12.3 -}

-- Beispiel: Zweierpotenzen
-- powersOfTwo == [1,2,4,8,16,...]
powersOfTwo :: [Integer]
powersOfTwo = 1 : map (*2) powersOfTwo

-- powerSeriers == [x^y, x^(y+1), x^(y+2), x^(y+3),...]
powerSeries :: Integer -> Integer -> [Integer]
powerSeries x y = x^y : powerSeries x (y+1)

{-
powersOfTwo
-> 1 : map (*2) powersOfTwo
-> 1 : map (*2) (1 : map (*2) powersOfTwo)
-> 1 : 2 : map (*2) (map (*2) powersOfTwo)
-> 1 : 2 : map (*2) (map (*2) (1 : map ...))
-> 1 : 2 : map (*2) (2 : (map (*2) (map ...)))
-> 1 : 2 : 4 : map ...
-}


-- Aufgabe
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

fib1 :: [Integer]
fib1 = 0 : 1 : zipWith (+) fib1 (tail fib1)

fib2 :: Integer -> Integer -> [Integer]
fib2 x y = x : fib2 y (x+y)


{-
fib1
-> 0 : 1 : zipWith (+) fib1 (tail fib1)
-> 0 : 1 : zipWith (+) (0 : 1 : zipWith ...) (1 : zipWith ...)
-> 0 : 1 : 1 : zipWith (+) (1 : 1 : zipWith ...) (1 : zipWith ...)
-> 0 : 1 : 1 : 2 : zipWith (+) (1 : 2 : zipWith ...) (2 : zipWith ...)
-> 0 : 1 : 1 : 2 : 3 : zipWith (+) (2 : 3 : zipWith ...) (3 : zipWith ...)


fib2 0 1
-> 0 : fib2 1 (0+1)
-> 0 : 1 : fib2 (0+1) (1+(0+1))
-> 0 : 1 : (0+1) : fib2 (1+(0+1)) ((0+1)+((0+1)+1))
-> 0 : 1 : 1 : fib2 (1+1) (1+(1+1))
-> 0 : 1 : 1 : (1+1) : fib2 (1+(1+1)) ((1+1)+((1+1)+1))
-> 0 : 1 : 1 : 2 : fib2 (1+2) (2+(2+1))
-}


{- Um fib n auszuwerten, muss fib (n-1) 2-mal, fib (n - 2) 4-mal, fib (n-3)
 - 8-mal, ... ausgewertet werden. Zur Auswertung von fib1 !! n müssen nur die
 - ersten (n+1) Elemente von fib1 jeweils 1-mal ausgewertet werden.
 - Die Laufzeit ist also linear statt exponentiell.
 -}



{---------------------------------------------------------------------}
{- Aufgabe G12.4 -}

hamming :: [Integer]
hamming = 1 : sort z (sort x y)
        where
        x = map (*2) hamming
        y = map (*3) hamming
        z = map (*5) hamming

        sort (x:xs) (y:ys)
                | x < y = x : sort xs (y:ys)
                | x > y = y : sort (x:xs) ys
                | x == y = x : sort xs ys


productOf :: [Integer] -> Integer -> Bool
productOf xs y = go xs y
  where
    go _ 1 = True
    go [] y = False
    go (z:zs) y = if y `mod` z == 0 then go xs (y `div` z) else go zs y

hamming' :: [Integer]
hamming' = filter (productOf [2,3,5]) [1 ..]



{---------------------------------------------------------------------}
{- Aufgabe H12.1 -}

wordsOf :: [a] -> [[a]]
wordsOf = undefined



{---------------------------------------------------------------------}
{- Aufgabe H12.2 -}

sumOfPrefixes :: Num a => [a] -> [a]
sumOfPrefixes = undefined



{---------------------------------------------------------------------}
{- Aufgabe H12.3 -}

findByFilter :: (a -> Bool) -> [a] -> Maybe a
findByFilter = undefined



{---------------------------------------------------------------------}
{- Aufgabe H12.4 -}

{-WETT-}
censoredWordsOf :: Eq a => [a] -> [[a]] -> [[a]]
censoredWordsOf = undefined
{-TTEW-}