TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2010-03-04

An die exakten Fragestellungen kann ich mich nicht mehr erinnern, die Angabe war aber im Prinzip sehr ähnlich zu den letzten Prüfungen (keine Theorie, nur Praxisbespiele mit Bäumen).

Bsp 1

war wieder die Bestimmung des Typs/Werts von ein paar Ausdrücken

Bsp 2

war ein polymorpher, binärer Baum. Kein spezieller Typ für Leaves, sondern einfach Knoten mit Nil als Nachfolger. Jeder Knoten hält ein Integer und ein polymorphes Element

Lösung:

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

ttree :: BTree Char
ttree = (Node 10 'a' (Node 12 'b' Nil (Node 21 'c' Nil Nil)) Nil)

Bsp 3

eine Funktion, die bestimmt, ob der Baum "aufsteigend" ist, d.h. ob der Integer-Wert in alle Child-Knoten kleiner ist als im aktuellen, + ob alle Kind-Bäume auch aufsteigend sind

Lösung:

-- Loesung
-- Baispielaufruf:
-- aufsteigend ttree
data BTree a = 
	Nil
    |	Node Integer a (BTree a) (BTree a)

ttree :: BTree Char
ttree = (Node 10 'a' (Node 12 'b' Nil (Node 21 'c' Nil Nil)) Nil)


aufsteigend :: BTree a -> Bool
aufsteigend Nil = True
aufsteigend tree@(Node val _ t1 t2) = 
  let
      list = getList tree
  in
      (allBigger val (tail list)) 	&&
      (aufsteigend t1) 			&&
      (aufsteigend t2)
       

getList :: BTree a -> [Integer]
getList Nil = []
getList (Node val _ t1 t2) = (val:[]) ++ (getList t1) ++ (getList t2)

allBigger :: Integer -> [Integer] -> Bool
allBigger _ [] = True
allBigger x (e:list)
  | x < e	= (allBigger x list)
  | otherwise	= False

Lösung alternativ:

tree1 = (Node 1 'a' (Node 2 'b' Nil (Node 3 'c' Nil Nil)) Nil) -- ascending == True
tree2 = (Node 99 'a' (Node 2 'b' Nil (Node 3 'c' Nil Nil)) Nil) -- ascending == False
tree3 = (Node 1 'a' (Node 2 'b' (Node 3 'c' Nil Nil) (Node 3 'c' Nil Nil)) (Node 2 'b' Nil Nil)) -- ascending == True
tree4 = (Node 1 'a' (Node 2 'b' (Node 1 'c' Nil Nil) (Node 3 'c' Nil Nil)) (Node 2 'b' Nil Nil)) -- ascending == False

ascending :: (BTree a) -> Bool
ascending Nil = True
ascending (Node x c left right) = and [smaller left x, smaller right x]

smaller :: (BTree a) -> Integer -> Bool
smaller Nil _ = True
smaller (Node x c left right) y = and [y > x, smaller left x, smaller right x]      EDIT:  y<x   to   y>x

Bsp 4

eine Funktion, die die polymorphen Elemente aller Knoten zurückgibt, deren Integer-Wert höher als x ist

Lösung

b :: (BTree a) -> Integer -> [a]
b Nil _ = []
b (Node x c left right) y
  | x > y = c : (b left y) ++ (b right y)
  | otherwise = (b left y) ++ (b right y)