TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2010-01-21 (Lösung)

Prüfung 2010-01-21

Aufgabe 1

50% Geben Sie Wert bzw. allgemeinsten Typ für t1 bis t7 an!

name = "Mustermann"
mnr = [0,1,2,3,4,5,6]

t1 = (27, [mnr!!0, mnr!!6], (head mnr, head name), (tail.tail) mnr );
{- t1 == ( 27, [                                         -}

t2 = (\x y z -> x(z)); {- Allgemeinster Typ! -}
{- t2 ::                                                 -}

t3 = t2 (product) (sum) (mnr)
{- t3 ==                                                 -}

t4 = ( [i|i<-mnr, i `mod` 2 == 0], [(i,i>4)|i<-mnr] );
{- t4 == ([                                              -}

t5 = [(i,sum[4..i])|i<-(tail mnr)];
{- t5 == [ (                                             -}

ml n l = [ l!!i | i<-[6,n,4], i< length l ];
t6 = (ml 5 mnr, [(i,i>j,j)|i<-ml 5 mnr, j<-ml 5 mnr, i<j] )
{- t6 == (                                               -}

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 == (                                               -}

Lösung

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)); {- Allgemeinster Typ! -}
{- t2 :: (a -> b) -> c -> a -> b                         -}

t3 = t2 (product) (sum) (mnr)
{- t3 == 0                                               -}

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

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

ml n l = [ l!!i | i<-[6,n,4], i< length l ];
t6 = (ml 5 mnr, [(i,i>j,j)|i<- ml 5 mnr, j<-ml 5 mnr, i<j] )
{- t6 == ([6,5,4],[(5,False,6),(4,False,6),(4,False,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))                                  -}

{- t7 == ((5,6), (0,120)) -} -- meine Loesung ???

deine Lösung stimmt nicht p [0,1,2,3,4,5,6] [] [] -> p [2,3,4,5,6] [0] [1] -> p [4,5,6] [0,2] [1,3] -> p [6] [0,2,4] [1,3,5] => sum [0,2,4] = 6, product [1,3,5] = 15, daraus folgt t7 == ((5,6),(6,15)) ---- by SibaJebacDovlineMame

die Loesung von SJDM sehe ich auch so, allerdings wird auf dem Weg das a und b an den Kopf der List gehaengt. also: p [0,1,2,3,4,5,6] [] [] -> p [2,3,4,5,6] [0] [1] -> p [4,5,6] [2,0] [3,1] -> p [6] [4,2,0] [5,3,1] => sum [4,2,0] = 6, product [5,3,1] = 15 Auch wenn es hier wegen sum und product egal ist, kann es bei anderen Beispielen zu Fehlern fuehren. ---- cheers wastelandgummybear

Aufgabe 2

5% Definieren Sie einen polymorphen algebraischen Datentyp TTree zur Darstellung von ternären Bäumen. Knoten und Blätter sollen neben einem Element Integer ein polymorphes Element enthalten. Es gibt also keine leeren Blätter.

Lösung

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

Aufgabe 3

5% Geben Sie einen konkreten TTree-Baum mit genau zwei Knoten (und passend vielen Blättern) als Zeichnung und in Haskell-Syntax an.

Lösung

ttree :: TTree Char
ttree = (Node 100 'a'   (Node 400 'b' (Leaf 430 'c') (Leaf 420 'd') (Leaf 410 'e'))    (Leaf 120 'f')    (Leaf 110 'g') )

Aufgabe 4

20% Definieren sie wiederholungsfrei, das für einen konkreten Baum genau dann wahr (True) ist, wenn beim Durchwandern des Baums keine zwei gleichen Integer-Einträge (in Blättern oder Knoten) unmittelbar hintereinander vorkommen.

Ein ternärer Knoten wird in folgender Reihenfolge durchwandert: Das Knotenelement, dritter, zweiter, erster Unterbaum.

wiederholungsfrei :: TTree a -> Bool;

Lösung

-- Aufruf: wiederholungsfrei ttree

wiederholungsfrei :: TTree a -> Bool
wiederholungsfrei (Leaf _ _) = True
wiederholungsfrei t0@(Node x _ t3 t2 t1) = 
  wiederholungsfrei t1 &&
  wiederholungsfrei t2 &&
  wiederholungsfrei t3 &&
  notEqVal t0 t1 &&
  notEqVal t1 t2 &&
  notEqVal t2 t3
  
notEqVal :: TTree a -> TTree a -> Bool
notEqVal (Leaf x _) (Leaf y _) = x /= y
notEqVal (Leaf x _) (Node y _ _ _ _) = x /= y
notEqVal (Node x _ _ _ _) (Node y _ _ _ _) = x /= y
notEqVal (Node x _ _ _ _) (Leaf y _) = x /= y

Lösung by Aymeba

wiederholungsfrei :: TTree a -> Bool
wiederholungsfrei (Leaf _ _) = True
wiederholungsfrei tree = checkList liste
			where liste = createList tree

createList :: TTree a -> [Integer]
createList (Leaf i a) = [i]
createList (Node i a t1 t2 t3) = [i] ++ createList t3 ++ createList t2 ++ createList t1

checkList :: [Integer] -> Bool
checkList [] = True
checkList [i] = True
checkList (a:b:l) = if a == b then False else checkList (b:l)

Lösung by patrikf für Schreibfaule

wiederholungsfrei :: TTree a -> Bool;
wiederholungsfrei t = all (uncurry (/=)) $ zip elems $ tail elems
    where elems = walk t

walk :: (TTree a) -> [Integer]
walk (Leaf x _) = [x]
walk (Node x _ a b c) = [x] ++ (concatMap walk [c,b,a])

Lösung von thomas

naive / intutive lösung.

der baum ist wf wenn

• alle teilbäume wf sind und
• der aktuelle knotenwert ungleich dem des linken, des mittleren und des rechten teilbaumes des aktuellen knotens ist

ein blatt ist axiomatisch wiederholungsfrei

wf :: TTree a -> Bool
wf (TNode i _ l m r) = (wf r && wf m && wf l) -- reihenfolge nach angabe
                       &&
                       (i /= val r && i /= val m && i /= val l)
  where
    val (TNode i _ _ _ _)	= i
    val (TLeaf i _)		= i
wf _ = True

sehr ähnliche Lösung

whf :: TTree a -> Bool
whf (Leaf (x,y)) = True
whf (Node (x,y) t1 t2 t3) = (x /= (getInt t3)) && (x /= (getInt t2)) && (x /= (getInt t1)) && whf t3 && whf t2 && whf t1

getInt :: TTree a -> Integer
getInt (Leaf (x,y)) = x
getInt (Node (x,y) _ _ _) = x

Lösung Aufgabe 5

20% DEfinieren Sie alle_von_bis t v b, das beim Durchwandern eines Baumes ab dem ersten Integer-Eintrag v bis einschließlich zum danach ersten Integer-Eintrag vorkommenden (polymorphen) Elemente als Paare liefert. Die Reihenfolge ist die gleiche wie bei wiederholungsfrei. Bei unpassenden v und b soll die leere Liste zurückgegeben werden.

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

Lösung

-- Aufruf: alle_von_bis ttree 100 300

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

ttree :: TTree Char
ttree = (Node 100 'a'    (Leaf 500 'f') (Node 400 'b' (Leaf 430 'c') (Leaf 420 'd') (Leaf 410 'e'))       (Leaf 200 'g') )


alle_von_bis :: TTree a -> Integer -> Integer -> [(Integer,a)]
alle_von_bis tree from to = avb (getTupelList tree []) from to []

getTupelList :: TTree a -> [(Integer,a)] -> [(Integer,a)]
getTupelList (Leaf x a) list = ((x,a):list)
getTupelList (Node x a t3 t2 t1) list = ((x,a):list) ++ (getTupelList t1 []) ++ (getTupelList t2 []) ++ (getTupelList t3 [])

avb :: [(Integer, a)] -> Integer -> Integer -> [(Integer,a)] -> [(Integer,a)]
avb [] _ _ _= []
avb ((x,a):rest) from to erg
  | x == from	= avb_to rest to ((x,a):erg)
  | otherwise   = avb rest from to erg
  
avb_to :: [(Integer, a)] -> Integer -> [(Integer,a)] -> [(Integer,a)]
avb_to [] _ _ = []
avb_to ((x,a):rest) to erg
  | x == to	= 
     reverse ((x,a):erg)
  | otherwise	= 
     avb_to rest to ((x,a):erg)

Lösung by aymeba

alle_von_bis :: TTree a -> Integer -> Integer -> [(Integer,a)]
alle_von_bis tree von bis = von_bis (convertPair tree) von bis

von_bis :: [(Integer,a)] -> Integer -> Integer -> [(Integer,a)]
von_bis [] _ _= []
von_bis (p:pairs) von bis = 
			if fst(p) == von then bisPair (p:pairs) bis 
			else von_bis pairs von bis

bisPair :: [(Integer,a)] -> Integer -> [(Integer,a)]
bisPair [] _ = []
bisPair (x:xs) bis = 
		if fst(x) == bis then [x] 
		else [x] ++ bisPair xs bis

convertPair :: TTree a -> [(Integer,a)]
convertPair (Leaf i a) = [(i,a)]
convertPair (Node i a t1 t2 t3) = [(i,a)] ++ convertPair t3 ++ convertPair t2 ++ convertPair t1

Lösung von mir!

treetolist :: TTree a -> [(Integer,a)]
treetolist (Leaf a i) = [(a,i)]
treetolist (Node a i l m r) = (a,i) :  treetolist (r) ++ treetolist (m) ++ treetolist (l)

alle_von_bis :: TTree a -> Integer -> Integer -> [(Integer,a)]
alle_von_bis t v b = alle_von_bis_list (treetolist t) v b

alle_von_bis_list :: [(Integer,a)] -> Integer -> Integer -> [(Integer,a)]
alle_von_bis_list l v b
	| (length main) < (length main_trail) = main ++ [ main_trail!!(length main)]
	| otherwise = main -- oder [] je nach interpretation
	where
		main_trail = (dropWhile (\x -> (fst x) /= v) l)
		main = takeWhile (\x -> (fst x) /= b) main_trail

Lösung von r0f1

alle_von_bis :: TTree a -> Integer -> Integer -> [(Integer,a)];
alle_von_bis t v b = if(v>b) then [] else takeWhile (\(x,y) -> x>=v && x<=b) (toList t)

toList :: TTree a -> [(Integer, a)]
toList (Node i j l m r) = [(i,j)] ++ toList r ++ toList m ++ toList l
toList (Leaf i j) = [(i,j)]

Anmerkung von high_stick: Ich nehme an, die Integer-Werte sind nicht aufsteigend, daher darf keine Sortierung oder ähnliches vorausgesetzt werden.

Lösung von high_stick

pairs :: TTree a -> [(Integer,a)]
pairs (Leaf n x) = [(n,x)]
pairs (Node n x a b c) = [(n,x)] ++ pairs c ++ pairs b ++ pairs a

alle_von_bis :: TTree a -> Integer -> Integer -> [(Integer,a)]
alle_von_bis t v b 
	| elem b (map fst list) = takeWhile not_b list ++ [head (dropWhile not_b list ) ]
	| otherwise = []
	where
		list = dropWhile (\(x,y) -> x /= v) (pairs t)
		not_b = \(x,y) -> x /= b

Lösung von alexf91

avb :: TTree a -> Integer -> Integer -> [(Integer, a)]
avb t v b = avb_drop_after (avb_drop_to (flatten t) v) b

flatten :: TTree a -> [(Integer, a)]
flatten (Leaf x y) = [(x,y)]
flatten (Node x y t1 t2 t3) = [(x,y)] ++ concatMap flatten [t3, t2, t1]

avb_drop_to :: [(Integer, a)] -> Integer -> [(Integer, a)]
avb_drop_to [] _ = []
avb_drop_to (x:xs) b  
    | (fst x) == b = (x:xs)
    | otherwise = avb_drop_to xs b
     
avb_drop_after :: [(Integer, a)] -> Integer -> [(Integer, a)]
avb_drop_after [] _ = []
avb_drop_after (x:xs) b
    | (fst x) /= b = x:(avb_drop_after xs b)
    | otherwise = [x]