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 :: Tree -> [Integer]
  34 transform t = toStree (sort (undup (concat (writeLayer t BottomUp))))
  35
  36 undup :: [Integer] -> [Integer]
  37 undup [] =  []
  38 undup (x:xs) = x : undup (filter (\y -> not (x == y)) xs)
  39
  40 toStree :: [Integer] -> STree
  41 toStree [] = Nil
  42 toStree (x:xs) = SNode x Nil (toStree xs)
  43
  44
  45
  46 --Aufg 4.2
  47 type Cost = Integer
  48 type Vertex = Integer
  49 newtype Graph = Graph [(Vertex,[(Vertex,Cost)])]
  50
  51 instance Show Graph where
  52   showsPrec p (Graph(x)) = showString "Graph(" . shows x . showChar ')'
  53
  54 -- Aufg 4.2a
  55 data Result = Yes | No | Invalid
  56 instance Show Result where
  57   showsPrec p (Yes) = showString "Yes"
  58   showsPrec p (No) = showString "No"
  59   showsPrec p (Invalid) = showString "Invalid"
  60
  61 instance Main.Eq Result where
  62   a == b = show a == show b
  63
  64
  65 --path :: Graph -> Vertex -> Vertex -> Cost -> Result
  66 --path _ _ _ _ = Invalid
  67
  68
  69
  70 --Aufg 4.2b
  71 --minpath :: Graph -> Vertex -> Vertex -> ([Vertex],Cost)
  72 --minpath _ _ _ _ = ([],1337)