Tilman
259 lines
5.5 KiB
Haskell
259 lines
5.5 KiB
Haskell
-- 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)
|