Aufgabe4.hs

   1 import Prelude hiding (Ord)
   2 import List
   3
   4 --Aufg 4.1a
   5 data Tree = Leaf Integer | Node Integer Tree Tree deriving (Eq,Show)
   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 (Eq,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 deriving (Eq,Show)
  55
  56 path :: Graph -> Vertex -> Vertex -> Cost -> Result
  57 path _ _ _ _ = Invalid
  58
  59
  60
  61 --Aufg 4.2b
  62 --minpath :: Graph -> Vertex -> Vertex -> ([Vertex],Cost)
  63 --minpath _ _ _ _ = ([],1337)