TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2015-01-15

Aufgabe 1

Geben Sie die Werte bzw. den allgemeinsten Typ von t1 bis t7 an. (Hier im VoWi kannst du die leeren Zeilen auswählen um die Lösungen zu sehen.)

mnr = [ 7, 6, 5, 4, 3, 2, 1 ] -- Matrikelnummer
name = "Max Mustermann" -- Name
knz = "E 033 4711" -- Studienkennzahl

t1 = ("p1", (reverse . take 2 . words . \_ -> name)"!");

{- t1 == ("p1", ["Mustermann", "Max"]) :: ([Char], [String]) - getestet mit GHCi -}

t2 = ( \x y z a  -> x(z(z(z(a))))); -- hier allgemeinsten Typ angeben

{- t2 :: (a -> b) -> u -> (a -> a) -> a -> b - getestet mit GHCi -}

t3 = t2 (take 4) (\x-> x++x) reverse mnr

{- t3 == [1,2,3,4] :: [Integer] - getestet mit GHCi -} 

t4 = [[i+2]|i<-mnr,i+2<5] ++ [[i|i<-mnr,3<i,i>4]];

{- t4 == [[4],[3],[7,6,5]] :: [[Integer]] - getestet mit GHCi -}

t5 = take 4 [[j|j<-[5..i]]|i<-mnr]

{- t5 == [[5,6,7],[5,6],[5],[]] :: [[Integer]] - getestet mit GHCi -}

tls xs = xs : case xs of _:ys  -> tls ys; _-> []
t6 = ((tls.take 2) mnr, take 5[(i,j)|(i:j:_)<-tls mnr, i<j]);

{- t6 == ([[7,6],[6],[]],[]) :: ([[Integer]], [(Integer, Integer)] - getestet mit GHCi -}

p (a:b:l) xs ys = p l (a:b:xs) (b:ys);
p _ xs ys = (sum ys, product xs);

t7 = ( p [mnr!!5, mnr!!6] [] [], p mnr [] []);
{- t7 ==  ((1,2),(12,5040)) :: ((Integer, Integer), (Integer, Integer)) - getestet mit GHCi -}

Aufgabe 2

Erstellen sie einen polymorphen algebraischen Datentyp BTree der einem Binärbaum entspricht. Jeder Knoten enthält ein polymorphes Element und zwei Unterbäume. Ein Knoten bzw. die Unterbäume können auch leer sein.

data BTree a = Nil | Node a (BTree a) (BTree a)

Aufgabe 3

Geben Sie einen konkreten Wert für folgenden Typ in Haskell-Syntax inklusive Zeichnung an: ( BTree Integer, BTree String ). Die Bäume sollen die Werte 1,2 und "ab" enthalten.

(Node 1 (Node 2 Nil Nil) Nil, Node "ab" Nil Nil)

Aufgabe 4

Definieren Sie eine Funktion jdif die für einen BTree genau dann True liefert, wenn für jeden Knoten gilt, dass das Element des Knotens nicht in den Unterbäumen des Knotens vorkommt. (Typklasse!)

jdif :: Eq a => (BTree a) -> Bool
jdif Nil = True
jdif (Node a Nil Nil) = True
jdif (Node a n@(Node b Nil Nil) Nil)
   | a /= b = and [True, jdif n]
   | otherwise = False
jdif (Node a Nil n@(Node b Nil Nil))
   | a /= b = and [True, jdif n]
   | otherwise = False
jdif (Node a n1@(Node b Nil Nil) n2@(Node c Nil Nil))
   | and [a /= b, a /= c] = and [True, jdif n1, jdif n2]
   | otherwise = False

Bei dieser Aufgabe habe ich extra den Professor gefragt, ob das Element nur nicht in den direkten Unterbäumen gleich sein darf, oder in den gesamten Unterbäumen (und deren Unterbäume, ...). Worauf er gemeint hat, dass es für die gesamten Unterbäume etwas zu aufwändig wäre. Deswegen habe ich die Funktion so geschrieben, dass sie nur für die direkten Unterbäume (bzw. Knoten) gilt. (Hoffentlich wird das auch so gewertet beim Verbessern.)

Alternative Lösung

Interpretiert man die Angabe so, dass das Element auch in den indirekten Unterbäumen nicht vorkommen darf, könnte man dafür folgende Lösung verwenden:

jdif :: Eq a => BTree a -> Bool
jdif t = jdif' t []
 where
  jdif' (Node a t1 t2) l
   | elem a l  = False
   | otherwise = jdif' t1 (a:l) && jdif' t2 (a:l)
  jdif' Nil _ = True

Die Lösung ist allerdings speicherintensiv, da die gefundenen Elemente in Listen verwaltet werden, dafür wird allerdings jeder Knoten nur einmal angesehen.

Alternativ könnte man auch eine wenig speicher- dafür laufzeitintensive Funktion verwenden:

jdif2 :: Eq a => BTree a -> Bool
jdif2 (Node a t1 t2) = jdif' t1 a && jdif' t2 a && jdif2 t1 && jdif2 t2
 where
  jdif' (Node a t1 t2) b
   | a == b     = False
   | otherwise  = jdif' t1 b && jdif' t2 b
  jdif' Nil _   = True
jdif2 Nil = True

Aufgabe 5

Definieren Sie filtert, das eine einstellige boolsche Funktion und einen BTree erwartet und eine Liste jener Elemente in beliebiger Reihenfolge zurückliefert, bei denen die Funktion für das Element True ist. Geben Sie auch hier eine möglichst allgemeine Typdeklaration für filtert an!

filtert :: (a -> Bool) -> BTree a -> [a]
filtert _ Nil          = []
filtert f (Node a l r) = [a | f a] ++ filtert f l ++ filtert f r