# Lösungsvorschlag Functional Programming Midterm 2008 Dem Autor des Lösungsvorschlags stellt sich eine Unklarheit betreffend der Prüfungsfrage oder deren Lösung: Angaben ohne Gewähr, Änderungsvorschläge willkommen :) --Neeko 13:51, 02. Apr 2009 (CEST) Hilf mit, die Qualität dieser Seite zu verbessern, indem du eine eindeutige Lösung einfügst oder auf der Diskussionsseite dieses Themas deine Meinung äusserst.

## Assignment 1

a) I.

(\x -> snd x) (fst, \y z -> map y ('e':z))


Beta-Reduction and Typing:

(\y z -> map y ('e':z) :: (Char -> a) -> [Char] -> [a]


II.

\x y z -> tail x == map (/=z) y :: Eq a => [Bool] -> [a] -> a -> Bool


b)

Cannot compare a list of Chars with a list of lists of Chars.

c)

Where Γ:=x:(Int,a)

==========================    ==========================
Γ,y:Int,z:(Int→b) ⊢ y::Int    Γ,y:Int,z:(Int→b) ⊢ 5::Int
==================================          --------------------------------------------------------
Γ, y:Int, z:(Int→b) ⊢ z :: (Int→b)                      Γ, y:Int, z:(Int→b) ⊢ (y+5) :: Int
------------------------------------------------------------------------------------------
Γ, y:Int, z:(Int→b) ⊢ z (y+5):: b
-------------------------------------------                ==============
Γ, y:Int ⊢ λz. z (y+5):: (Int→b)→b                          Γ ⊢ x:(Int,a)
-------------------------------------------------          -----------------
Γ ⊢ (λy.λz. z (y+5)):: Int→((Int→b)→b)                      Γ ⊢ (fst x)::Int
----------------------------------------------------------------------------
x:(Int,a) ⊢ (λy.λz. z (y+5))(fst x)::(Int→b)→b
-----------------------------------------------
⊢ λx.(λy.λz. z (y+5))(fst x)::(Int,a)→(Int→b)→b


d)

 A |- t1 :: \sigma   A,x:\sigma |- t2 :: \tau
------------------------------------------------ x \notin A
A |- let x = t1 in t2 :: \tau


## Assignment 2

(Siehe Solution Exercise Sheet 6 2009, Assignment 1)

Proof by induction over x.

Base case: x = Leaf.

 subtrees Leaf =
treeFold f [Leaf] Leaf =
[Leaf] =                             [def. of subtrees'.1]
subtrees' Leaf


Step case: x = Node y l r.

 subtrees (Node y l r) =
treeFold f [Leaf] (Node y l r) =
f y (treeFold f [Leaf] l) (treeFold f [Leaf] r) =
f y (subtrees l) (subtrees r) =
(subtrees l ++ subtrees r) =                       [(a)]
(Node y l r) : (subtrees l ++ subtrees r) =          [IH]
(Node y l r) : (subtrees' l ++ subtrees' r) =        [def. of subtrees'.2]
subtrees' (Node y l r)


## Assignment 3

a)

data LTree a b = Leaf b | ANode a (LTree a b) (LTree a b)
| BNode a (LTree a b)
deriving (Eq, Show)


b)

shape :: LTree a b -> LTree c d -> Bool
shape (Leaf _) (Leaf _) = True
shape (BNode _ t1) (BNode _ t2) = shape t1 t2
shape (ANode _ t1 t2) (ANode _ t3 t4) = (shape t1 t3) && (shape t2 t4)
shape _ _ = False


## Assignment 4

(Siehe Solution Exercise Sheet 6 2009, Assignment 5)

(a)

directSuccessors :: Eq a => DiGraph a -> a -> [a]
directSuccessors gr x = [ w | (v,w) <- gr, v == x]

directSuccessors_tests = [(directSuccessors simple_gr 'c', ['b','d']),
(directSuccessors simple_gr 'd',[])]


(b)

isPath :: Eq a => DiGraph a -> [a] -> Bool
isPath g []       = False
isPath g [_]      = False
isPath g (x:y:xs) = (x,y) elem g && (null xs || isPath g (y:xs))

isPath_tests = [(isPath simple_gr [], False),
(isPath simple_gr ['a','d'], False),
(isPath simple_gr ['a','c','d'],True)]


(c)

successors :: Eq a => DiGraph a -> a -> [a]
successors gr x = visit [] [x]
where visit vs []     = vs
visit vs (x:xs)
| x elem vs  = visit vs     xs
| otherwise    = visit (x:vs) ((directSuccessors gr x)++xs)

successors_tests = [(sort \$ successors simple_gr 'b', sort ['b','a','c','d']),
(successors simple_gr 'd', ['d'])]


## Assignment 5

a)

split :: Char -> String -> [String]
split a [] = [""]
split a (x:xs)
| a == x = "": rest
| otherwise = (x:head rest):(tail rest)
where rest = split a xs


Alternativ:

split2 :: Char -> String -> [String]
split2 c s = foldr f [""] s
where f x y = if (x==c) then [""]++y else [[x]++(head y)]++(tail y)


Alternativ:
"first" is the string until the first occurrence of the split symbol s.
"rest" is the string after the first occurrence of the split symbol s.

split3 s xs
| s elem rest = [first]  ++ split3 s rest
| otherwise = [first, rest]
where
first = takeWhile (\x -> x/=s) xs
rest = drop (length first + 1) xs


b)

center s = zipWith f (map length s) s
where max = maximum (map length s)
f x y = if ((max - x) mod 2 == 0) then
(replicate (div (max - x) 2) ' ') ++ y ++ (replicate (div (max - x) 2) ' ')
else
(replicate (div (max - x) 2) ' ') ++ y ++ (replicate (div ((max - x)+1) 2) ' ')


Alternativ:

center strings = map modify strings
where
modify str = left ++ str ++ right
where
maxLength = maximum (map length strings)
strLength = length str
leftLength = div (maxLength-strLength) 2
rightLength = maxLength - leftLength - strLength
left = replicate leftLength ' '
right = replicate rightLength ' '