TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2009-06-25

Aufgabe 1

50% Geben sie den Wert bzw. allgemeinsten Typ fuer t1 bis t7 an! (Die Werte sind mit mnr=[0,1,2,3,4,5,6] und name = "Mustermann, Max" zustande gekommen)

t1 = ( ( 27, mnr!!0, mnr!!6), (head mnr, head name), (tail.tail) mnr );
-- t1 == ((27,0,6),(0,'M'),[2,3,4,5,6])

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

t3 = t2 (sum) (product) (mnr) 
-- t3=21

t4 = ( [i|i <-mnr, i `mod` 3 == 0], [(i,i-i)|i<-mnr] );
-- t4 == ([0,3,6],[(0,0),(1,0),(2,0),(3,0),(4,0),(5,0),(6,0)])

t5 = [(i, sum[5..i])|i<-(tail mnr)];
-- t5 == [(1,0),(2,0),(3,0),(4,0),(5,5),(6,11)]

ml n l = [ l!!i | i <- [6,n,4], i < length l];

t6 = ( ml 5 mnr, [(i,j)|i<- ml 5 mnr, j<- ml 5 mnr, i<j] )
-- t6 == ([6,5,4], [(5,6),(4,6),(4,5)])

p (a:b:l) xs ys = p l ( a:xs) ( b:ys );

p _ xs ys = (sum xs, product ys);

t7 = ( p [ mnr!!5, mnr!!6] [] [], p mnr [] []);
-- t7 == ((5,6),(6,15))

Aufgabe 2

Polymorphen Datentyp TTree definieren: darzustellen ist ein Ternärer Baum mit einem Integer und einem polymorphem Element sowohl in den Blättern als auch in den Knoten.

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

Aufgabe 3

(Node 0 'a' (Node 1 'b' (Leaf 4 'e') (Leaf 5 'f') (Leaf 6 'g')) (Leaf 2 'c') (Leaf 3 'd'))

		N:0,a
	     /    |    \
	N:1,b	L:2,c	L:3,d
      /   |   \
 L:4,e  L:5,f  L:6,g

Aufgabe 4

wiederholungsfrei :: TTree a -> Bool wenn zwei unmittelbar hintereinanderfolgende Werte gleich sind soll False ausgegeben werden. Die Durchmusterungsreihenfolge war: Unterbaum1, Unterbaum2, Unterbaum3, Knoten.

Lösung 1

Nicht besonders performant, aber sollte beim Test so durchgehen.

wiederholungsfrei :: TTree a -> Bool
wiederholungsfrei tree = whf_helper (tail (tTreeToList tree)) (head (tTreeToList tree))

whf_helper :: [Integer] -> Integer -> Bool
whf_helper [] v = True
whf_helper (x:xs) v
	| x == v	= False
	| otherwise	= whf_helper xs x

tTreeToList :: TTree a -> [Integer]
tTreeToList (Leaf x _) = [x]
tTreeToList (Node x _ t1 t2 t3) = tTreeToList t1 ++ tTreeToList t2 ++ tTreeToList t3 ++ [x]

sollte nun stimmen (whf_helper: otherwise-rekursion eingebaut) --85.127.102.66 13:43, 20. Jan. 2010 (CET)

Lösung 2

wiederholungsfrei :: TTree a -> Bool
wiederholungsfrei t = not $ elem True [ fst (l!!i) == fst (l!!(i+1)) | i <- [0..((length l) - 2)]]
					  where l = flatten t

flatten :: TTree a -> [(Integer,a)]
flatten (Leaf i v) = [(i,v)]
flatten (TT i v n1 n2 n3) = flatten n1 ++ flatten n2 ++ flatten n3 ++ [(i,v)]

Aufgabe 5

alle_von_bis :: TTree a -> Integer -> Integer -> [(Integer, a)]

alle_von_bis t v b

soll den Baum wie in Beispiel 4 durchgehen. zurückgegeben werden soll eine liste mit tupeln, die den integer und polymorphen wert aller knoten vom ersten auftreten des werts v bis zum ersten auftreten des werts b enthält. zB.:

alle_von_bis (Node 3 'a' (Node 1 'b' (Leaf 2 'c') 
                                     (Leaf 1 'a') 
                                     (Leaf 3 'a')) 
                         (Leaf 4 'x') 
                         (Leaf 5 'x')) 1 4 
                         == [(1,'a'),(3,'a'),(1,'b'),(4,'x')]

Lösung

alle_von_bis :: TTree a -> Integer -> Integer -> [(Integer, a)] 
alle_von_bis tree v b = alle_bis (alle_von (tTreeToList2 tree) v) [] b

alle_von :: [(Integer,a)] -> Integer -> [(Integer,a)]
alle_von [] v = []
alle_von (x:xs) v
	| fst(x) == v	= (x:xs)
	| otherwise	= alle_von xs v
	
alle_bis :: [(Integer,a)] -> [(Integer,a)] -> Integer -> [(Integer,a)]
alle_bis [] result _ = result
alle_bis (x:xs) result b
	| fst(x) == b	= result ++ [x]
	| otherwise	= alle_bis xs (result ++ [x]) b

tTreeToList2 :: TTree a -> [(Integer, a)]
tTreeToList2 (Leaf v g)			= [(v,g)]
tTreeToList2 (Node v g t1 t2 t3)	= tTreeToList2 t1 ++ tTreeToList2 t2 ++ tTreeToList2 t3 ++ [(v,g)]

---

andere lösung 28.02.2010

---

alle_von_bis :: TTree a -> Integer -> Integer -> [(Integer, a)] 
alle_von_bis tree v b = alle_bis (alle_von (tTreeToList2 tree) v) b
 
alle_von :: [(Integer,a)] -> Integer -> [(Integer,a)]
alle_von [] v = []
alle_von (x:xs) v
	| fst(x) == v	= (x:xs)
	| otherwise	= alle_von xs v

alle_bis :: [(Integer,a)] -> Integer -> [(Integer,a)]
alle_bis [] a = []
alle_bis (x:xs) b
	| fst(x) /= b	= [x] ++ alle_bis xs b
	| otherwise	= [x]

tTreeToList2 :: TTree a -> [(Integer, a)]
tTreeToList2 (Leaf v g)			= [(v,g)]
tTreeToList2 (Node v g t1 t2 t3)	= tTreeToList2 t1 ++ tTreeToList2 t2 ++ tTreeToList2 t3 ++ [(v,g)]

---

für Schreibfaule

---

alle_von_bis :: TTree a -> Integer -> Integer -> [(Integer, a)]
alle_von_bis tree v b = 
    takeWhile (\x -> fst(x) /= b) (dropWhile (\x -> fst(x) /= v) treelist)
    where
    treelist = treetolist tree

treetolist :: TTree a -> [(Integer, a)]
treetolist (Leaf i elem) = [(i, elem)]
treetolist (Node i elem left middle right) = treetolist left ++ treetolist middle ++ treetolist right ++ [(i, elem)]

Dir geht dann aber das letzte Element verloren:
[(1,'a'),(3,'a'),(1,'b')]

---

noch eine Lösung 19.01.2011

---

alle_von_bis :: TTree a -> Integer -> Integer -> [(Integer,a)]
alle_von_bis t v b = reverse (dropTo (reverse (dropTo (treeToList t) v)) b)
    where
    treeToList :: TTree a -> [(Integer,a)]
    treeToList (Leaf x y) = [(x,y)]
    treeToList (Node x y first second third) = (x,y) : rest
	where
	rest = (treeToList third) ++ (treeToList second) ++ (treeToList first)

    dropTo :: [(Integer,a)] -> Integer -> [(Integer,a)]
    dropTo [] _ = []
    dropTo ((x,y):xs) b
	| x == b	= ((x,y):xs)
	| otherwise	= dropTo xs b

---

weitere Lösung [14.01.2013]

---

-- Funktion laut Angabe. Helper-Funktion wird mit einem False-Flag aufgerufen, dh es wurde
-- noch kein Element ermittelt, welches in die Ziel-Liste gehört (Initialisierungsdefault).
alle_von_bis :: TTree a -> Integer -> Integer -> [(Integer, a)]
alle_von_bis t v b = alle_von_bis_helper l v b False
	                 where l = flatten t

-- Läuft die Liste durch, und anhand eines Flags, welches bei 'von' auf True gesetzt wird, 
-- werden nachfolgend alle Elemente bis 'bis' genommen.
alle_von_bis_helper :: [(Integer, a)] -> Integer -> Integer -> Bool -> [(Integer, a)]
alle_von_bis_helper [] _ _ _ = []
alle_von_bis_helper t@(e@(i,w):r) v b f = if f == False && i == v then
	                                        [e] ++ alle_von_bis_helper r v b True
	                                      else if f == True && i /= b then
	                                      	[e] ++ alle_von_bis_helper r v b True
	                                      else if f == True && i == b then
	                                      	[e]
	                                      else
	                                      	alle_von_bis_helper r v b f

-- Alternative zu alle_von_bis_helper ohne if-else
alle_von_bis_helper2 :: [(Integer, a)] -> Integer -> Integer -> Bool -> [(Integer, a)]
alle_von_bis_helper2 [] _ _ _ = []
alle_von_bis_helper2 t@(e@(i,w):r) v b f
  | f == False && i == v  = [e] ++ alle_von_bis_helper2 r v b True
  | f == True  && i /= b  = [e] ++ alle_von_bis_helper2 r v b True
  | f == True  && i == b  = [e]
  | otherwise             = alle_von_bis_helper2 r v b f

-- Plättet den Baum und liefert das Integer und den Polymorphen Wert zurück.
flatten :: TTree a -> [(Integer,a)]
flatten (Leaf i v) = [(i,v)]
flatten (TT i v n1 n2 n3) = flatten n1 ++ flatten n2 ++ flatten n3 ++ [(i,v)]