1a. alg. Menge (Haskell data) 2a. alg. Queue (Haskell data) 3a. alg. Stack (Haskell data) 4a. alg. Baum (Haskell data) 1a. Algebraische Spezifikation einer Menge (types,operators,axioms) --------------------------------------------------------------------------------------------------- types : Menge m,m,Bool //Menge,element,Bool data Menge m = E | (In m (Menge m)) //Empty | Menge mit e operators : createM :: Menge m isEmpty :: Menge m -> Bool insert :: m -> Menge m -> Menge m delete :: m -> Menge m -> Menge m isIn :: m -> Menge m -> Bool Alle x <- m , s <- Menge m axioms : createM () = E isEmpty (E) = True isEmpty (insert x s) = False insert (x,E) = (In x E) //x:E insert (x,s) | isIn (x,s) = s | otherwise = (In x s) //x:M delete (x,E) = E delete (y,(In x m)) |y == x = m |otherwise = Insert x (delete (y,m)) isIn (x,E) = False isIn (y,(In x m)) |y == x = True |otherwise = isIn (y,m) 2a. Algebraische Spezifikation einer Schlange (types,operators,axioms) --------------------------------------------------------------------------------------------------- types : Queue q,q,Bool //Schlange,element,Bool data Queue q = E | NeQ q (Queue q) //Empty | Queue mit elem operators : createQ :: Queue q isEmpty :: Queue q -> Bool enqueue :: q -> Queue q -> Queue q dequeue :: Queue q -> Queue q first :: Queue q -> q Alle x <- q, s <- Queue q axioms : createQ () = E isEmpty (E) = True isEmpty (s) = False enqueue (x,s) = (NeQ x s) dequeue (NeQ x s) = s first (NeQ x s) = x 3a. Algebraische Spezifikation eines Stacks (types,operators,axioms) --------------------------------------------------------------------------------------------------- types Stack,e,Bool,int data Stack s = E | NeS e (Stack s) operators : createS :: Stack s isEmpty :: Stack s -> Bool push :: e -> Stack s -> Stack s pop :: Stack s -> Stack s top :: Stack s -> e size :: Stack s -> int axioms : create () = E isEmpty (E) = True isEmpty (NeS x s) = False push (x,s) = (NeS x s) pop (E) = error "Stack ist leer!" pop (NeS x s) = s top (E) = error "Stack ist leer!" top (NeS x s) = x size (E) = 0 size (NeS x s) = 1 + size(s) 4a. Algebraische Spezifikation eines Baumes (types,operators,axioms) --------------------------------------------------------------------------------------------------- types BTree,n,Bool,int data BTree t = E | N (BTree t) t (BTree t) operators : insert :: n -> BTree t -> BTree t delete :: n -> BTree t -> BTree t hoehe :: BTree t -> int isIn :: t -> BTree t -> Bool isEmpty :: BTree t -> Bool leftTree :: BTree t -> BTree t rightTree :: BTree t -> BTree t axioms : insert x E = (N E x E) insert x (N l v r) | x == v = (N l x r) | x < v = (N (insert x l) v r) | x > v = (N l v (insert x r)) delete :: (Ord t) => t -> BTree t -> BTree t delete x E = error "ist bereits leer" delete y (N E x E) | y == x = E | otherwise = (N E x E) delete y (N l x r) | y < x = (N (delete y l) x r) | y > x = (N l x (delete y r)) | (l==E)&&(x==y)= r | (r==E)&&(x==y)= l | y == x = (N (delete (maxi l) l)(maxi l) r) where max :: BTree t -> t max (N E x E) = x max (N l v r) = max l hoehe E = 0 hoehe (N E x E) = 1 hoehe (N l v r) = 1 + max (hoehe l)(hoehe r) where max :: int -> int max x y | x <= y = y |otherwise = x isIn x E = False isIn x (N l v r) | x == v = True | otherwise = (isIn x l) || (isIn x r) isEmpty E = True isEmpty t = False leftTree E = error "alles Leer -> links auch" leftTree (N l v r) = l rightTree E = error "alles Leer -> rechts auch" rightTree (N l v r) = r