TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2017-01-19

Aufgabe 1 (50%)[Bearbeiten | Quelltext bearbeiten]

Geben Sie Wert und allgemeinsten Typ für 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] :: [Integer]; -- Matrikelnummer
name = "Mustermann, Max" :: String; -- Familienname, Vorname(n)
knz = "E033 534" :: String -- Kennzahl

t1 = ("p1", (take 2.reverse.show)mnr, (head.words.(\n o ->o:name)'-')'+');
{- ("p1","]7","+Mustermann,") :: ([Char],[Char],[Char]) -}

t2 = (\x y z -> y.x.y); -- hier nur allgemeinster Typ!
{- (a -> b) -> (b -> a) -> c -> b -> a -}

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

t4 = ( [i|i<-mnr, i>2], [(i, i`mod`3)|i<-mnr] );
{- ([3,4,5,6,7],[(1,1),(2,2),(3,0),(4,1),(5,2),(6,0),(7,1)]) :: ([Integer],[(Integer,Integer)]) -}

t5 = [(sum([i..5]),i)|i<-(tail mnr)];
{- [(14,2),(12,3),(9,4),(5,5),(0,6),(0,7)] :: [(Integer,Integer)] -}

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]) -}

-- Tipp: beachte hier den unterschied zwischen : und ++ bei Listen

p (a:l) = p l + a + p l;
p (a:b:l) | a <= b = p (b:l);
p [e] = 200000;
p _ = 0;
t7 = ( (p.drop 4)mnr, p mnr);
{-t7 = (45, 769) :: (Num a, Num b, Ord a, Ord b) laut GHCI - Zeile (a:b:l) und [e] werden ignoriert, sobald ein p einen Head hat wird (a:l) aufgerufen, wenn leer dann _ -}

Aufgabe 2 (5%)[Bearbeiten | Quelltext bearbeiten]

Definieren Sie einen polymorphen algebraischen Datentyp BTree zur Darstellung von binären Bäumen. Knoten enthalten neben einem polymorphen Element zwei Unterbäume. Weiters gibt es auch leere Bäume und leere Unterbäume.

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

Aufgabe 3 (5%)[Bearbeiten | Quelltext bearbeiten]

Geben Sie einen konkreten Wert des Typs BTree (BTree Integer, String), der die Werte 1, 2 und "ab" enthält, in Haskell- Syntax und als Zeichnung an.

Node (Node 1 (Node 2 Nil Nil) Nil, "ab") Nil Nil :: BTree (BTree Integer, String)

Aufgabe 4 (5+15%)[Bearbeiten | Quelltext bearbeiten]

Definieren Sie juniq, das für einen Baum des Typs BTree genau dann True ist, wenn in jedem Knoten das polymorphe Element höchstens einmal in den Unterbäumen des Knotens vorkommt. Geben Sie für juniq auch die entsprechende Typdeklaration an. (Typklasse!)

Lösungsvorschlag: Dragobitch (Diskussion) 14:12, 23. Feb. 2017 (CET)

juniq :: Eq a => BTree a -> Bool
juniq Nil = True
juniq (Node a l r)
  | (count a l + count a r) > 1 = False
  | otherwise                   = juniq l && juniq r

count :: Eq a => a -> BTree a -> Integer
count _ Nil = 0
count a (Node b l r) 
  | a == b    = 1 + count a l + count a r
  | otherwise = count a l + count a r


Lösungsalternative:

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

class Juniq a where
    juniq :: a -> Bool

instance Eq a => Juniq (BTree a) where
    juniq Nil = True
    juniq (Node x a1 a2) = juniq' a1 x 0 && juniq' a2 x 0

juniq' :: (Eq a, Eq b, Num b) => BTree a -> a -> b -> Bool
juniq' _ _ 2 = False
juniq' Nil _ _ = True
juniq' (Node x a1 a2) y c
      | x == y = (juniq' a1 y (c+1)) && (juniq' a2 y (c+1))
      | otherwise = (juniq' a1 y c) && (juniq' a2 y c) && (juniq' a1 x 0) && (juniq' a2 x 0)

Aufgabe 5 (5+15%)[Bearbeiten | Quelltext bearbeiten]

Definieren Sie trx, das zwei Argumente erwartet: Eine einstellige boolsche Funktion und einen BTree. Die Funktion liefere eine Liste aus Tripeln jener Knoten zurück, für die die Funktion zutrifft (angewandt auf den gesamten Knoten). Im Tripel ist das erste Element das Knotenelement, das zweite der linke und das dritte der rechte Unterbaum. Die Elemente der Liste kommen in beliebiger Reihenfolge vor. Geben Sie auch hier eine möglichst allgemeine Deklaration an!