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