TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2016-03-04

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 = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] -- Matrikelnummer
name = "Mustermann, Max" -- Name
knz = "E 033 4711" -- Studienkennzahl

t1 = ("p1", (take 3.reverse.show) mnr, ???)
{- ("p1","]7,","???") :: ([Char],[Char],???) -}

t2 = (\x y z -> y.x.y) -- Nur allgemeinster Typ
{- (a -> b) -> (b -> a) -> c -> b -> a -}

t3 = t2 (take 4) (\x->x++x) reverse mnr
{- [1,2,3,4,1,2,3,4] :: [Integer] -}

t4 = ([i|i<-mnr,i>2], ???)

t5 = ???

tls xs = xs : case xs of _:ys  -> tls ys; _-> []
t6 = ((tls.take 3) mnr, take 5 [j|(0:j:_)<-tls mnr]);
{- ([[1,2,3],[2,3],[3],[]],[]) :: ([[Integer]],[Integer]) -}

p (a:l) = p l + a + p l;
p (a:b:l) | a <= b = p (b:l);
p [e] = 10000;
p [] = 0;

t7 = ( (p.drop 4)mnr , p mnr);
{- (45,769) :: (Integer,Integer) -}

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 (BTree Integer, String). Die Bäume sollen die Werte 1,2 und "ab" enthalten.

Node (Node 1 (Node 2 Nil Nil) Nil, "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 öfters als einmal in den Unterbäumen des Knotens vorkommt. (Typklasse!)

jdif :: (Eq a) => BTree a -> Bool -- (Eq a) wird benötigt damit elem funktioniert
jdif btree = jdif2 btree []

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

Anmerkung: ich glaub das ist nicht ganz richtig, da das Element eben mindestens einmal in den Unterbäumen vorkommen kann, aber im Beispiel oben beim ersten duplizierten Auftreten des Elements "False" ausgegeben wird! Kleine Änderung unter Verwendung einer "count" funktion (warum ist das nicht im standard drin :P ):

jdif :: (Eq a) => BTree a -> Bool
jdif t = noDupl t []

noDupl :: (Eq a) => BTree a -> [a] -> Bool
noDupl Nil _ = True
noDupl (Node a t1 t2) list
    | count 0 a list >= 2 = False -- hier ist der Unterschied zu oben! das element darf insgesamt 2 mal, also einmal in der wurzel, einmal im Unterbaum, vorkommen
    | otherwise = (noDupl t1 list2) && (noDupl t2 list2)
    where list2 = list ++ [a]

count :: (Eq a) => Integer -> a -> [a] -> Integer
count occ _ [] = occ
count occ a (x:xs)
  | a == x = count (occ + 1) a xs
  | otherwise = count occ a xs

Ich hab das anders verstanden:

jdif :: (Eq a) => BTree a -> Bool
jdif (Node a leftTree rightTree) = (((count a leftTree) + (count(a)(rightTree))) <= 1) && jdif(leftTree) && jdif(rightTree)
jdif Nil = True

count :: (Eq a) => a -> BTree a -> Integer
count (a)(Node b leftTree rightTree) = (if a == b then 1 else 0) + count(a)(leftTree) + count(a)(rightTree)
count _ Nil = 0;

--tests:
main = do 
  print $ jdif(Node 1 (Node 1 Nil Nil) (Node 1 Nil Nil)) == False
  print $ jdif(Node 1 (Node 0 Nil Nil) (Node 1 Nil Nil)) == True
  print $ jdif(Node 1 (Node 0 (Node 1 Nil Nil) Nil) (Node 1 Nil Nil)) == False
  print $ jdif(Node 1 (Node 0 (Node 1 Nil Nil) Nil) (Node 0 Nil Nil)) == True

Aufgabe 5

Definieren Sie ftx, das eine einstellige boolsche Funktion und einen BTree erwartet und eine Liste mit Tripeln in beliebiger Reihenfolge zurückliefert, bei denen die Funktion für den Knoten True ist. Das erste Element des Tripels soll den Knoten enhalten, das zweite und dritten den linken bzw. rechten Unterbaum. Geben Sie auch hier eine möglichst allgemeine Typdeklaration für ftx an!

ftx :: (BTree a -> Bool) -> BTree a -> [(BTree a, BTree a, BTree a)]
ftx _ Nil = []
ftx f n@(Node a t1 t2) = [(n,t1,t2) | f n] ++ ftx f t1 ++ ftx f t2