Lösungsvorschlag Functional Programming Midterm 2008

Aus VISki
Wechseln zu: Navigation, Suche
Question.png

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) =
 (Node y (head (subtrees l)) (head (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 ' '