{-
Pattern Matching (& Nicht-strikte Auswertung)
-}
and' :: Bool -> Bool -> Bool
and' _ False = False
and' False _ = False
and' True True = True
unsure :: Bool
unsure = not unsure
false1 = and' False unsure
false2 = and' unsure False
-------------------------------------------------
{-
lazy evaluation for infinite lists
-}
-- explicit recursion
from :: Integer -> [Integer]
from x = x:from (x+1)
nats :: [Integer]
nats = from 1
fibs :: [Integer]
fibs = fib 0 1
where fib x y = x:fib y (x+y)
take' :: Int -> [a] -> [a]
take' 0 _ = []
take' _ [] = []
take' (n+1) (x:xs) = x:take' n xs
-- or one utility-function and implicit recursion
sumlist :: [Integer] -> [Integer] -> [Integer]
sumlist (x:xs) (y:ys) = x+y:sumlist xs ys
ones, nats', fibs' :: [Integer]
ones = 1:ones
nats' = 1:sumlist nats' ones
fibs' = 0:1:sumlist fibs' (tail fibs')
-------------------------------------------------
{-
simple higher-order functions
-}
map' :: (a -> c) -> [a] -> [c]
map' _ [] = []
map' f (x:xs) = f x:map' f xs
-- all square numbers
squares = map' (\x -> x*x) nats
-- filter all elements that fulfill a certain predicate
filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' f (x:xs) | f x = x:filter' f xs
| otherwise = filter' f xs
-- quicksort with HO-functions
quicksort :: [Int] -> [Int]
quicksort [] = []
quicksort (x:xs) =
quicksort (filter' (< x) xs) ++ [x] ++ quicksort (filter' (>= x) xs)
-------------------------------------------------
{-
quicksort with list comprehensions
-}
qs :: Ord a => [a] -> [a]
qs [] = []
qs (x:xs) = qs [y | y <- xs, y=x]
-------------------------------------------------
{-
sets implemented as functions
Every set can be seen as a function from the elements to the booleans.
This function delivers true iff an element in the set is applied to it.
-}
type Set a = a -> Bool
-- the empty set
emptySet :: Set a
emptySet = \x -> False
-- test whether the given set contains the given element
element :: a -> Set a -> Bool
element x set = set x
-- insert given element to the set
insert :: Eq a => a -> Set a -> Set a
insert x set = \y -> if x == y then True else element y set
-- removes a element from the set
remove :: Eq a => a -> Set a -> Set a
remove x set = \y -> if x == y then False else element y set
-- compute the union of two sets
union :: Set a -> Set a -> Set a
union s1 s2 = \y -> element y s1 || element y s2
-- compute the intersection of two sets
intersect :: Set a -> Set a -> Set a
intersect s1 s2 = \y -> element y s1 && element y s2
-- compute the complement of a set
complement :: Set a -> Set a
complement set = \y -> not (element y set)
-- minus s1 s2 = s1 \ s2 (= s1 \intersect (complement s2))
minus s1 s2 = s1 `intersect` (complement s2)
-- construct a set from a list
fromList :: Eq a => [a] -> Set a
fromList [] = emptySet
fromList (x:xs) = insert x (fromList xs)
-- construct a list from a set of chars
toList :: Set Char -> [Char]
toList s = filter' (\x -> element x s) ['\0'..]
isEmpty = error "zu schwierig"
-------------------------------------------------
{-
lazy evaluation and pattern matching cont.
-}
-- replace in given list every element by first argument and give minimum
findMinAndReplace :: Int -> [Int] -> (Int, [Int])
findMinAndReplace x [y] = (y, [x])
findMinAndReplace x (y:ys) =
let (m,xs) = findMinAndReplace x ys
in (min y m,x:xs)
-- replace in one walk through the list every element by the minimum of the list
replaceByMin :: [Int] -> [Int]
replaceByMin xs = let (m,ys) = findMinAndReplace m xs
in ys
replByMin :: [Int] -> [Int]
replByMin xs = let pair = findMinAndReplace (fst pair) xs
in snd pair