Lösungsvorschlag Functional Programming Midterm 2005

Aus VISki
Wechseln zu: Navigation, Suche

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)  

siehe Diskussion:Lösungsvorschlag_Functional_Programming_Midterm_2005

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: (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