TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2015-03-06

Forum

Diskussion im Forum dazu: Thread

Aufgabe 1

Geben Sie die Werte und 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 = "Max Mustermann" -- Name
knz = "E 033 4711" -- Studienkennzahl

t1 = ("p2", unlines((:) ((head.words) name)["!"]));

{- t1 == ("p2", "Max\n!\n") :: ([Char], String)  
   Der Rückwert von unlines ist ein String! -}

t2 = ( \x y z  -> y.x.y ); -- Nur allgemeinster Typ

{- t2 :: (b -> a) -> (a -> b) -> c -> a -> b -}

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

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

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

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

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

{- t5 == [[],[],[],[]] :: [[Integer]] - Innere Listen sind in diesem Beispiel leer, da mnr mit 1,2,3,4 beginnt -}
{- t5 == [[5,4,3,2,1],[5,4,3,2],[5,4,3],[5,4]] :: [[Integer]] - Dieser Operator funktioniert mMn anders: https://web.archive.org/web/20180731235828/https://en.wikibooks.org/wiki/Haskell/Lists_II -}
{- Das erste t5 mit 4 leeren Listen stimmt schon. Aus dem Link sieht man, dass [5,4..1] == [5,4,3,2,1], aber hier steht z.B. [5..1] was [] ergibt. Das wird als "von bis" gelesen. -}

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

{- t6 == ([[2,3],[3],[]],[(2,3),(3,4),(4,5),(5,6),(6,7)]) :: ([[Integer]],[(Integer, Integer)]) -}

p (a:b:l) | a <= b = p (b:l);
p (a:l) = p l + a + p l;
p [e] = 10000;
p [] = 0;
t7 = ( (p.drop 4)mnr , p mnr);

{- t7 == (7,7) :: (Integer, Integer) -}

Aufgabe 2

Erstellen sie einen polymorphen algebraischen Datentyp TTree der einem ternären Baum entspricht. Jedes Blatt enthält genau ein polymorphes Element. Jeder Knoten enthält genau drei Unterbäume. Ein Knoten, Blatt bzw. die Unterbäume können auch leer sein.

Vorschlag:

data TTree a = Nil | Leaf a | Node (TTree a) (TTree a) (TTree a)

Aufgabe 3

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

Leaf (Node (Leaf 1) (Leaf 2) Nil)

Es handelt sich also um einen Baum, der in seinem Blatt einen Baum enthält. Die Zeichnung müsste also eigentlich so aussehen, dass man ein Blatt zeichnet (Leaf), das den Baum mit einem Knoten und zwei Blättern sowie einem Nil beinhaltet (siehe auch "Rekursive Typen (4)" im Kapitel 6.3 der VO-Folien).

Aufgabe 4

Definieren Sie eine Funktion geordnet die für einen TTree genau dann True liefert, wenn:

1. Das Element vom ersten Unterbaum < das Element vom zweiten Unterbaum ist
2. Das Element vom zweiten Unterbaum < das Element vom dritten Unterbaum ist

geordnet :: Ord a => (TTree a) -> Bool
geordnet (Node (Leaf a) (Leaf b) (Leaf c)) = a < b && b < c
geordnet _                                 = False

Anmerkung bei der oben angegeben Lösung bricht der Algo ab falls keine Leafs in dem Node enthalten sind. Es können jedoch auch Nodes in dem ersten Node vorhanden sein, dann muss man sich die nächste Ebene anschauen:

geordnet :: Ord a => TTree a -> Bool
geordnet (Node (Leaf a) (Leaf b) (Leaf c)) = a < b && b < c
geordnet (Node n1 n2 n3)                   = geordnet n1 && geordnet n2 && geordnet n3
geordnet _                                 = False

Aufgabe 5

Definieren Sie die Methode zipT , die zwei TTree vergleicht, und einen TTree zurückgibt, der genau an der Stelle einen Knoten hat, wo die zwei übergebenen TTree einen Knoten haben, und genau dort ein Blatt hat, wo die zwei übergebenen TTree ein Blatt haben. Der Wert im Blatt des neuen Blattes ist ein Paar aus den Werten der Blätter der übergebenen TTrees. Überall anders soll ein leeres Element stehen.

zipT :: TTree a -> TTree b -> TTree (a,b)
zipT (Leaf a) (Leaf b)               = Leaf (a,b)
zipT (Node a1 b1 c1) (Node a2 b2 c2) = Node (zipT a1 a2) (zipT b1 b2) (zipT c1 c2)
zipT _ _                             = Nil