TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2011-01-20

Die Angabe des ersten Beispiels habe ich leider nicht mehr im Kopf, bitte ergänzen. --W1n5t0n 20:37, 20. Jan. 2011 (CET)

Aufgabe 1

z.B: mnr = [0,1,2,3,4,5,6]

t1 = ( ( "p1", [head mnr], [(head.tail) mnr], [(tail.tail) mnr]) )
-- ("p1",[0],[1],[[2,3,4,5,6]])

t2 = (\x y z -> z.x.x);
-- \x y z -> z . x . x :: (a -> a) -> b -> (a -> c) -> a -> c

t3 = t2 tail head sum mnr
-- 20

t4 = ( [(i*2,i)|i<-mnr], [i>2|i<-mnr] ):
-- ([(0,0),(2,1),(4,2),(6,3),(8,4),(10,5),(12,6)],[false,false,false,true,true,true,true])
...

Aufgabe 2

Polymorphen Datentyp TTree definieren: darzustellen ist ein Ternärer Baum mit einem polymorphen Datentyp und Null.

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

Aufgabe 3

Zeichnen sie einen Baum mit genau zwei Knoten und geben sie die Haskell-Syntax an.

Node 3 (Node 5 Nil Nil Nil) Nil Nil

		N:3
	     /    |    \
	N:5	Nil	Nil
      /   |   \
    Nil	 Nil   Nil

Aufgabe 4

geordnet :: Ord a => TTree a -> Bool Durchmustern des ganzen Baumes, und True, falls immer alle Subknoten in allen Subbäumen größer sind, als der Wert eines Knotens

Lösung

-- Beispielaufrufe (sollten alle True returnen)
-- True == geordnet (Node 3 (Node 5 Nil Nil Nil) Nil Nil)
-- False == geordnet (Node 3 (Node 2 Nil Nil Nil) Nil Nil)
-- False == geordnet (Node 3 (Node 5 Nil Nil (Node 5 Nil Nil Nil)) Nil (Node 5 Nil Nil Nil))	
-- True == geordnet (Node 3 (Node 5 Nil Nil (Node 6 Nil Nil Nil)) Nil (Node 5 Nil Nil Nil))

geordnet :: Ord a => TTree a -> Bool
geordnet Nil = True
geordnet (Node x t1 t2 t3) = let
			c1 = concatTree t1
			c2 = concatTree t2
			c3 = concatTree t3
			in
			checkOrd c1 x &&
			checkOrd c2 x &&
			checkOrd c3 x &&
			geordnet t1 &&
			geordnet t2 &&
			geordnet t3

concatTree :: TTree a -> [a]
concatTree Nil = []
concatTree (Node a t1 t2 t3) = [a] ++ (concatTree t1) ++ (concatTree t2) ++ (concatTree t3)

checkOrd :: Ord a => [a] -> a -> Bool
checkOrd [] _ 		= True
checkOrd [x] y		= x > y
checkOrd (x:xs)	y	= (x > y) && (checkOrd xs y)

andere lösung ohne listenbildung

geordnet :: Ord a => TTree a -> Bool
geordnet Nil = True
geordnet (Node x a b c) = and [allekleinerals a x, allekleinerals b x, allekleinerals c x, geordnet a, geordnet b, geordnet c]

allekleinerals :: Ord a => TTree a -> a -> Bool
allekleinerals Nil _ = True
allekleinerals (Node x a b c) y = and [x > y, allekleinerals a y, allekleinerals b y, allekleinerals c y] -- Es nicht notwendig allekleinerals a y usw. aufzurufen. Da ">" bzw "<" transitiv ist. x>y würde ausreichen.

Noch schönere Lösung (wenn auch nicht unbedingt einfacher)

geordnet :: Ord a => TTree a -> Bool
geordnet Nil = True
geordnet n@(Node _ a b c) = all (\x -> n < x && geordnet x) [a,b,c]

instance Eq a => Eq (TTree a) where
    (==) Nil Nil = True
    (==) (Node x _ _ _) (Node y _ _ _) = x == y
instance Ord a => Ord (TTree a) where
    (<) Nil _ = False
    (<) _ Nil = True
    (<) (Node x _ _ _) (Node y _ _ _) = x < y

Aufgabe 5

alle_groesser :: Ord a => TTree a -> a -> [a]

Alle Werte in irgendeiner Reihenfolge ausgeben, die größer sind, als der übergebene Wert.

Lösung

-- Beispielaufruf
-- alle_groesser (Node 3 (Node 5 Nil Nil Nil) Nil Nil) 4
alle_groesser :: Ord a => TTree a -> a -> [a]
alle_groesser tree limit = filter (\x -> x > limit) (concatTree tree)

Lösung 2

-- Beispielaufruf:
-- alle_groesser ttree 3
ttree = (Node 5 (Node 10 (Node 15 Nil Nil Nil) Nil Nil) Nil Nil)


alle_groesser :: Ord a => TTree a -> a -> [a]
alle_groesser tree x = ag1 tree x []
  
  
ag1 :: Ord a => TTree a -> a -> [a] -> [a]
ag1 Nil _ list = list
ag1 (Node val t1 t2 t3) x list
  | val > x 	= val:list ++ (ag1 t1 x list) ++ (ag1 t2 x list) ++ (ag1 t3 x list)
  | otherwise	= (ag1 t1 x list) ++ (ag1 t2 x list) ++ (ag1 t3 x list)

Lösung 3 by aymeba

alle_groesser :: Ord a => TTree a -> a -> [a]
alle_groesser Nil _ = []
alle_groesser (Node a t1 t2 t3) limit = if a > limit then [a] ++ others else others
		where others = (alle_groesser t1 limit) ++ (alle_groesser t2 limit) ++(alle_groesser t3 limit)

Lösung 4

alle_groesser :: Ord a => TTree a -> a -> [a] 
alle_groesser Nil _ = []
alle_groesser (Node x a b c) limit
    | x > limit = x : concat (map (\y -> alle_groesser y limit) [a,b,c])
    | otherwise = concat (map (\y -> alle_groesser y limit) [a,b,c])

Lösung 5

alle_groesser :: Ord a => TTree a -> a -> [a]
alle_groesser Nil _ = []
alle_groesser (Node a t1 t2 t3) b = [a|a>b] ++ (alle_groesser t1 b) ++ (alle_groesser t2 b) ++ (alle_groesser t3 b)