-- Aufgabe 1: Quicksort

qsort :: Ord (a) => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort[y | y <- xs, y < x] ++ [x] ++ qsort[y | y <- xs, y >= x]


-- Aufgabe 2: Mergesort
msort :: Ord (a) => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort (take half xs)) (msort (drop half xs))
	where half = (length xs) `div` 2
	      merge [] ys = ys
	      merge xs [] = xs
	      merge (x:xs) (y:ys)
		| (x < y) = x:(merge xs (y:ys))
		| otherwise = y:(merge (x:xs) ys)
		
-- Aufgabe 3: Insertionsort

insertionsort :: Ord (a) => [a] -> [a]
insertionsort [] = []
insertionsort (x:xs) = insert x (insertionsort xs)

insert :: Ord (a) => a -> [a] -> [a]
insert a [] = [a]
insert a (x:xs)
	|a <= x = (a:x:xs)
	|otherwise = x : (insert a xs)
	
-- Aufgabe 4: Selectionsort

selectionSort :: Ord (a) => [a] -> [a]
selectionSort xs
	| xs == [] = []
	| otherwise = minimum xs : selectionSort (delete (minimum xs) xs)

-- die Funktion delete ist im module "List" vorhanden, habe aber keine Ahnung, wie man die importiert
delete :: Eq (a) => a -> [a] -> [a]
delete x [] = []
delete x (y:ys)
	|x == y = ys
	|otherwise = y : (delete x ys)

-- Aufgabe 5: lineare Suche

linSearch :: Eq(a) => a -> [a] -> Bool
linSearch x [] = False
linSearch x (y:ys)
	|x == y = True
	|otherwise = linSearch x ys

-- Aufgabe 6: Binäre Suche
-- hat Fehler, Hilfe!!!

binSearch :: Ord a => a -> [a] -> Bool
binSearch x [] = False
binSearch x xs
	| (mid == x) = True
	| (mid > x)  = binSearch x (take half xs)
	| (mid < x)  = binSearch x (drop half xs)
	where mid = head (drop half xs)
	      half = (length xs) `div` 2


-- Aufgabe 7: reverse

-- naive Implementierung (ja, es gibt eine bessere ; ))

rev :: [a] -> [a]
rev [] = []
rev (x:xs) = rev xs ++ [x]

	-- hier die bessere Variante

rev2 :: [a] -> [a]
rev2 xs = rev' [] xs
	where rev' acc [] = acc
	      rev' acc (x:xs) = rev' (x:acc) xs

-- Aufgabe 8: Fibonacci

fibo :: Int -> Int
fibo 0 = 0
fibo 1 = 1
fibo n = fibo (n-1) + fibo(n-2)

	-- mit Akkumulator

fibo2 :: Int -> Int
fibo2 n = fibo' 0 1 n
	where fibo' a1 a2 0 = a1
	      fibo' a1 a2 n = fibo' (a1+a2) a1 (n-1)

-- Aufgabe 9: Fakultät

fak :: Int -> Int
fak 1 = 1
fak n = n * fak(n-1)

	-- mit Akkumulator

fak2 :: Int -> Int
fak2 n = fak' 1 n
	where fak' acc 1 = acc
	      fak' acc n = fak' (n*acc) (n-1)

-- Aufgabe 10: Summer einer Liste

sumList :: [Int] -> Int
sumList [] = 0
sumList (x:xs) = x + sumList xs

	-- mit Akkumulator

sumList2 xs = sumList' 0 xs
	where sumList' acc [] = acc
	      sumList' acc (x:xs) = sumList'(x+acc) xs

-- Aufgabe 11: map Funktion

map' :: (a -> b) -> [a] -> [b]
map' f [] = []
map' f (x:xs) = (f x) : map' f xs

-- Aufgabe 12: Binärer Suchbaum

data BinSTree = E | N BinSTree Int BinSTree

sumTree :: BinSTree -> Int
sumTree E = 0
sumTree (N l v r) = v + sumTree l + sumTree r

contains :: Int -> BinSTree -> Bool
contains a E = False
contains a (N l v r)
	|a == v = True
	|a < v = contains a l
	|otherwise = contains a r

insertToTree :: Int -> BinSTree -> BinSTree
insertToTree  a E = N E a E
insertToTree  a (N l v r)
	|a == v = (N l v r)
	|a < v = N (insertToTree  a l) v r
	|otherwise = N l v (insertToTree  a r)
	
deleteFromTree :: Int -> BinSTree -> BinSTree
deleteFromTree a E = E
deleteFromTree a (N l v r)
	|a == v = insertLeftTree r l
	|a < v = N l (deleteFromTree a r) 
	|otherwise = N (deleteFromTree a l) v r
	
insertLeftTree E t = t
insertLeftTree (N l v r) t = N (insertLeftTree l t) v r 
	
treeToList :: BinSTree -> [Int]
treeToList E = []
treeToList (N l v r) = treeToList l ++ [v] ++ treeToList r

-- Aufgabe 13: Ein Stack

data Stack t = E | NES t (Stack t)
	deriving(Show)

createStack :: Stack t
createStack = E

push :: t -> Stack t -> Stack t
push x s = NES x s

pop :: Stack t -> Stack t
pop E = error "Stack ist leer"
pop (NES x s) = s

top :: Stack t -> t
top E = error "Stack ist leer, kein top"
top (NES x s) = x

size :: Stack t -> Int
size E = 0
size (NES x s) = 1 + size s

isEmpty :: Stack t -> Bool
isEmpty E = True
isEmpty (NES x s) = False

-- showStack :: Stack t -> String
showStack E = "*"
showStack (NES x s) = [x] ++ showStack s

-- Aufgabe 14: Eine Queue

data Queue t = E | NEQ t (Queue t)

createQueue :: Queue t
createQueue = E

enqueue :: t -> Queue t -> Queue t
enqueue x E = NEQ x E
enqueue x (NEQ y q) = NEQ y (enqueue x q)

dequeue :: Queue t -> Queue t
dequeue E = error "Queue leer"
dequeue (NEQ x q) = q

first :: Queue t -> t
first E = error "Queue leer"
first (NEQ x q) = x

size :: Queue t -> Int
size E = 0
size (NEQ x q) = 1 + size q

isEmpty :: Queue t -> Bool
isEmtpy E = True
isEmpty (NEQ x q) = False

-- Aufgabe 15: Eine Menge

data Set t = E | NES t (Set t)

createSet :: Eq t => Set t
createSet = E

isIn :: Eq t => t -> Set t -> Bool
isIn x E = False
isIn x (NES y s)
	|y == x = True
	|otherwise = isIn x s

insert :: Eq t => t -> Set t -> Set t
insert x E = NES x E
insert x s
	|isIn x s = s
	|otherwise = NES x s

delete :: Eq t => t -> Set t -> Set t
delete x E = E
delete x (NES y s)
	|x == y = s
	|otherwise = insert y (delete x s)

size :: Eq t => Set t -> Int
size E = 0
size (NES x s) = 1 + size s

isEmpty :: Eq t => Set t -> Bool
isEmpty s = (size s == 0)

isSubSet :: Eq t => Set t -> Set t -> Bool
isSubSet E s2 = True
isSubSet (NES x s1) s2 = (isIn x s2) && isSubSet s1 s2

isEqualSet :: Eq t => Set t -> Set t -> Bool
isEqualSet s1 s2 = (isSubSet s1 s2) && (isSubSet s2 s1)