]> git.somenet.org - pub/jan/funcprog.git/blob - Aufgabe4.hs
fertig... fast
[pub/jan/funcprog.git] / Aufgabe4.hs
1 import Prelude hiding (Ord)
2 import List
3
4 --Aufg 4.1a
5 data Tree = Leaf Integer | Node Integer Tree Tree
6 type Layer = [Integer]
7
8 -- Ord datatype + show + compare
9 data Ord = BottomUp | TopDown
10
11 instance Show Ord where
12   showsPrec p (BottomUp) = showString "BottomUp"
13   showsPrec p (TopDown) = showString "TopDown"
14
15 instance Main.Eq Ord where 
16   a == b = show a == show b
17
18 -- Die eigentliche aufgabe
19 writeLayer :: Tree -> Ord -> [Layer]
20 writeLayer (Leaf x) o = [[x]]
21 writeLayer (Node x l r) o | (o == BottomUp) = (mmerge (writeLayer l o) (writeLayer r o)) ++ [[x]]
22 writeLayer (Node x l r) o | (o == TopDown) = [[x]] ++ (mmerge (writeLayer l o) (writeLayer r o))
23
24 mmerge :: [[Integer]] -> [[Integer]] -> [[Integer]]
25 mmerge x y = [x!!index ++ y!!index | index <- [0..(min (length x) (length y))-1]]
26
27
28
29 --Aufg 4.1b
30 data STree = Nil | SNode Integer STree STree deriving Show
31
32 transform :: Tree -> STree
33 transform t = toStree (sort (undup (concat (writeLayer t BottomUp))))
34
35 undup :: [Integer] -> [Integer]
36 undup [] = []
37 undup (x:xs) = x : undup (filter (\y -> not (x == y)) xs)
38
39 toStree :: [Integer] -> STree
40 toStree [] = Nil
41 toStree (x:xs) = (SNode x Nil (toStree xs))
42
43
44
45 --Aufg 4.2
46 type Cost = Integer
47 type Vertex = Integer
48 newtype Graph = Graph [(Vertex,[(Vertex,Cost)])]
49
50 instance Show Graph where
51   showsPrec p (Graph(x)) = showString "Graph(" . shows x . showChar ')'
52
53 -- Aufg 4.2a
54 data Result = Yes | No | Invalid
55 instance Show Result where
56   showsPrec p (Yes) = showString "Yes"
57   showsPrec p (No) = showString "No"
58   showsPrec p (Invalid) = showString "Invalid"
59
60 instance Main.Eq Result where
61   a == b = show a == show b
62
63
64 path :: Graph -> Vertex -> Vertex -> Cost -> Result
65 path _ _ _ _ = Invalid
66
67
68
69 --Aufg 4.2b
70 --minpath :: Graph -> Vertex -> Vertex -> ([Vertex],Cost)
71 --minpath _ _ _ _ = ([],1337)