> {-# LANGUAGE NoImplicitPrelude #-}
> module Muster1 where
> import Prelude (Int,(+),(-),(++),snd,Bool,otherwise,($),String,Show(..),mod,Eq(..),(&&))

Aufgabe 1:
a. f nimmt zwei Argumente und gibt das erste zurück. Das zweite wird ignoriert.
   g liefert die erste Komponente eines Tupels.
   h verwandelt eine Funktion mit Tupelparameter in eine mit Currying.
b. f heißt const, g heißt fst, h heißt curry.
c.

> const :: a -> b -> a        
> const = curry fst

Alternativ:
        
> const' a _ = a
>
> fst :: (a,b) -> a        
> fst (a,_) = a
>
> curry :: ((a,b) -> c) -> a -> b -> c
> curry f = \a b -> f (a,b)

Aufgabe 2:
Häufig will man partiell anwenden oder etareduzieren, aber die Reihenfolge der Parameter ist ungünstig. Dann kann man sie mit flip vertauschen.

> flip :: (a -> b -> c) -> b -> a -> c
> flip f = \b a -> f a b

Aufgabe 3:
Häufig will man zwei Funktionen nacheinander ausführen, aber jedes Mal \x -> f (g x) ist zu sperrig. Dann kann man stattdessen (f . g) schreiben.

> (.) :: (b -> c) -> (a -> b) -> a -> c
> f . g = \x -> f (g x)

Aufgabe 4:
Funktionen umschreiben:
  id = \x.x
  flip = \f.\a.\b.(f b a)
  (.) = \f.\g.\x.(f (g x))

(.) flip flip = (\f.\g.\x.(f (g x))) (\f.\a.\b.(f b a)) (\f.\a.\b.(f b a))
    {beta} = (\g.\x.((\f.\a.\b.(f b a)) (g x))) (\f.\a.\b.(f b a))
    {beta} = (\g.\x.\a.\b.(g x b a)) (\f.\a.\b.(f b a))
    {alpha}= (\g.\x.\a.\b.(g x b a)) (\f.\c.\d.(f d c))
    {beta} = \x.\a.\b.((\f.\c.\d.(f d c)) x b a)
    {beta} = \x.\a.\b.((\c.\d.(x d c)) b a)
    {beta} = \x.\a.\b.((\d.(x d b)) a)
    {beta} = \x.\a.\b.(x a b)
    {eta}  = \x.\a.(x a)
    {eta}  = \x.x
           = id, q.e.d.

Aufgabe 5:
in O(n):
   
> length :: [a] -> Int
> length [] = 0
> length (x:xs) = 1+length xs

Aufgabe 6:
(!!) liegt in O(n). Wenn man Array-basierte Algorithmen funktional umschreibt,
erhält man daher häufig eine schlechtere Gesamtlaufzeit. Durch geschicktes
Umdesignen oder die Verwendung von Data.Array lässt sich das jedoch beheben.

> (!!) :: [a] -> Int -> a
> (x:_) !! 0 = x
> (_:xs) !! n = xs !! (n-1)

Aufgabe 7:

> map :: (a -> b) -> [a] -> [b]
> map _ [] = []
> map f (x:xs) = f x : map f xs

map flip :: [a -> b -> c] -> [b -> a -> c]
flip map :: [a] -> (a -> b) -> [b]

Aufgabe 8:

> filter :: (a -> Bool) -> [a] -> [a]
> filter _ [] = []
> filter f (x:xs) | f x = x : filter f xs
>                 | otherwise = filter f xs

Aufgabe 9:

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

zipWith (.) :: [b -> c] -> [a -> b] -> [a -> c]
zipWith id :: [a -> b] -> [a] -> [b]

Aufgabe 10:

> reverse :: [a] -> [a]
> reverse [] = []
> reverse (x:xs) = reverse xs ++ [x]

Aufgabe 11:

> splitAt :: Int -> [a] -> ([a],[a])
> splitAt 0 xs = ([],xs)
> splitAt n (x:xs) =
>     let (as,bs) = splitAt (n-1) xs
>     in (x:as,bs)
>        
> take :: Int -> [a] -> [a]
> take n = fst . splitAt n
>
> drop :: Int -> [a] -> [a]
> drop n = snd . splitAt n

Aufgabe 12:

> cycle :: [a] -> [a]
> cycle as = as++cycle as

Aufgabe 13:
        
Mit map:
    
> iterate :: (a -> a) -> a -> [a]
> iterate f a = a : map f (iterate f a)

Oder alternativ:
     
> iterate' :: (a -> a) -> a -> [a]
> iterate' f a = a : iterate' f (f a)

Aufgabe 14:

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

In jeder Nicht-Blatt-Rekursionsebene Spaltung in zwei Stränge => O(2^n)

Aufgabe 15:

> fib' :: Int -> Int
> fib' = snd . helper
>     where helper :: Int -> (Int,Int)
>           helper 0 = (0,0)
>           helper 1 = (0,1)
>           helper n =
>               let (p2,p1) = helper (n-1)
>               in (p1,p1+p2)

Aufgabe 16:

> fibs :: [Int]
> fibs = map fst $ iterate (\(prev,curr) -> (curr,curr+prev)) (0,1)

Aufgabe 17:

> fibs' :: [Int]
> fibs' = 0 : 1 : zipWith (+) fibs' t where (_:t) = fibs'

Aufgabe 18:

Für den Anwendungsfall, dass nur eine einzige Fibonacci-Zahl gesucht wird, sind fibs, fibs' und fibs'' gleich effizient (aus O(n)).
Für den Anwendungsfall, dass die ersten n Fibonacci-Zahlen gesucht werden, liegt fibs'' aber in O(n^2), da für jedes Element wieder alle kleineren berechnet werden. fibs und fibs' liegen weiterhin in O(n), da sie die früheren Berechnungen wiederverwenden.

Aufgabe 19:

> isFizzBuzz :: Int -> String
> isFizzBuzz n | (n `mod` 3 == 0) && (n `mod` 5 == 0) = "fizz buzz"
>              | n `mod` 3 == 0 = "fizz"
>              | n `mod` 5 == 0 = "buzz"
>              | otherwise = show n

Aufgabe 20:

> fizzBuzz :: [String]
> fizzBuzz = map isFizzBuzz [1..]

Aufgabe 21:

Das ist die aufsteigende Liste natürlicher Zahlen: [1,2,3,4,5,...]

Aufgabe 22:

`fuu n' liefert die Potenz 2^n.

Aufgabe 23:

> foo :: Num a => [a] -> [a] -> a
> foo xs ys = sum (zipWith (*) xs ys)

Aufgabe 24:

> bar = (f .) . g
> baz = uncurry ((flip f .) . g)
> buz = const id -- oder flip const