Assignment 1 (Function Types)

a)

```(\x y -> x y)
```

b)

```(\x -> x U)
```

c)

```(\x y z -> if x<z then y else y)
```

d)

```(\(l,f) -> map (\x -> f (x+x)) l) Addition erfordert Num a
oder
(\x -> map (snd x) (fst x))
oder (äquivalent)
uncurry (flip map)
oder mit pattern-matching
(\(x,y) -> map y x)
```

e)

```(\f -> f (\x -> x))
```

Alternativ:

```(\f -> f id)
```

f) map hat folgenden typ:

```(a -> b) -> [a] -> [b]
```

gegeben ist mit 'head [0,0,7]' aber:

```([a] -> a) -> [a]
```

was bedeutet dass das map nicht mehr über eine liste geht sondern nur noch über ein element, was nicht der definition entspricht, well typed wäre zB

```map head [[0,0,7]]
```

Assignment 2 (Lazy/Eager Evaluation)

a) lazy:

```(\x y -> x y) (\z -> y z)
(\a -> (\z -> y z) a)
```

eager:

```(\x y -> x y) (\z -> y z)
(\a -> (\z -> y z) a)
(\a -> y a)
```

b) lazy:

```(\f x -> x f) (\r -> r) (\y z -> y z)
(\x -> x (\r -> r)) (\y z -> y z)
(\y z -> y z) (\r -> r)
(\z -> (\r -> r) z)
```

eager:

```(\f x -> x f) (\r -> r) (\y z -> y z)
(\x -> x (\r -> r)) (\y z -> y z)
(\y z -> y z) (\r -> r)
(\z -> (\r -> r) z)
(\z -> z)
```

Assignment 3 (Proof with foldr/filter/map)

We will need two simple lemmas:

1. if condition then f x else f y is equivalent to f (if condition then x else y), this can be shown using a case distinction.
2. We can redefine filter in an equivalent way:
```filter _ [] = []
filter p (x:xs) = if (p x) then (x : (filter p xs)) else (filter p xs)
```

To prove: ${\displaystyle \forall l::[a].\;\operatorname {foldr} \;\operatorname {aux} \;[]\;l=\operatorname {map} \;\operatorname {f} \;(\operatorname {filter} \;\operatorname {p} \;l)}$ (1)

Proof by induction over length l = n.

• Base case: length l = 0, i.e. l = []
```foldr aux [] l
= foldr aux [] []
= []                    (definition of foldr)
= map f []              (definition of map, backwards)
= map f (filter p [])   (definition of filter, backwards)
= map f (filter p l)
```
• Induction hypothesis: for l, length l = n, (1) holds.
• Induction step: l' = x:l (length l' = n+1)
```foldr aux [] l' =
= foldr aux [] (x:l)
= aux x (foldr aux [] l)                                                (definition of foldr)
= if p x then (f x) : (foldr aux [] l) else (foldr aux [] l)            (definition of aux)
= if p x then (f x) : (map f (filter p l)) else (map f (filter p l))    (induction hypothesis, twice)
= if p x then map f (x : (filter p l)) else (map f (filter p l))        (definition of map, backwards)
= map f (if p x then (x : (filter p l)) else (map f (filter p l)))      (first lemma ())
= map f (filter p (x:l))                                                (second lemma, backwards)
= map f (filter p l')
```

q.e.d.

Assignment 4 (Implementation)

```dfsBound :: Eq a => a -> Tree a -> Int -> Bool
dfsBound _ _ 0 = False
dfsBound _ Leaf _ = False
dfsBound x (Node t t1 t2) n = x==t || dfsBound x t1 (n-1) || dfsBound x t2 (n-1)
```

wobei hier angenommen wird, dass die wurzel tiefe 1 hat! hat die wurzel tiefe 0, müsste man in der 2. zeile dfsBound _ _ (-1) = False oder dfsBound x (Node t t1 t2) 0 = (x=t) nehmen.

Assignment 5 (Alg. DT 1)

a)

```data Tree a = Leaf a | Node (Tree a) (Tree a)
deriving (Show)
```

b)

```mapT :: (a -> b) -> Tree a -> Tree b
mapT f (Leaf n) = Leaf (f n)
mapT f (Node t1 t2) = Node (mapT f t1) (mapT f t2)
```

c)

```foldT :: (a -> b) -> (b -> b -> b) -> Tree a -> b
foldT f1 f2 (Leaf n) = f1 n
foldT f1 f2 (Node t1 t2) = f2 (foldT f1 f2 t1) (foldT f1 f2 t2)
```

d)

```fringe :: Tree a -> [a]
fringe = foldT (\x -> [x]) (\x y -> x ++ y)
```

oder:

```fringe_2 :: Tree a -> [a]
fringe_2 t = foldT (\x -> [x]) (++) t
```

oder: (noch ein bisschen schöner ^^)

```fringe_3 :: Tree a -> [a]
fringe_3 = foldT (:[]) (++)
```

Assignment 6 (Alg. DT 2)

a)

```boolLists :: Int -> [[Bool]]
boolLists 0 = [[]]
boolLists n = map (\x -> False:x) (boolLists (n-1)) ++ map (\x -> True:x) (boolLists (n-1))
oder kürzer:
boolLists 0 = [[]]
boolLists n = map (False:) bL ++ map (True:) bL
where bL = boolLists (n-1)
```

b)

```func1 :: Int -> BoolFunc -> [([Bool], Bool)]
func1 n (Func f) = map (\x -> (x, (f x))) (boolLists n)
oder
func1 n (Func f) = [(x, f x) | x <- boolLists n]
oder (ev. weniger elegant)
func1 n (Func f) = zip (boolLists n) (map f (boolLists n))
```

c)

```func2 :: Int -> BoolFunc -> BoolFunc -> Bool
func2 n (Func f) (Func g) = foldr (\x y -> (f x = g x) && y) True (boolLists n)
oder
func2 n f g = (func1 n f) == (func1 n g)
oder
func2 n (Func f) (Func g) = (map f ln) == (map g ln)
where ln = lists n
```