--
-- Einfache Funktionsdefinition
--
square x = x * x

{-
? square (10+1)
121 :: Int
? 
-}

-- 
-- Bedingte Gleichungen
--
maxi x y | x > y     = x
         | otherwise = y

{-
? maxi 0 15
15 :: Int
? maxi 15 0
15 :: Int
? 
-}

--
-- Rekursion
--
fac n | n == 0    = 1
      | otherwise = n * fac (n - 1)

{-
? fac 0
1 :: Int
? fac 1
1 :: Int
? fac 5
120 :: Int
? 
-}

--
-- Listen, Patternmatching, Polymorphie
--
{-
head (x:xs) = x
tail (x:xs) = xs

length [] = 0
length (x:xs) = 1 + length xs
-}
append []     ys = ys
append (x:xs) ys = x:append xs ys

{-
? append "aber " "hallo"
aber hallo
? 
-}

--
-- Unendliche Listen
--
nats = [1..]
sieve (p:xs) = p:sieve [x | x <- xs, x `mod` p /= 0]
primes = sieve (tail nats)

{-
? primes
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,
223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419{Interrupted!} 
-}


--
-- Funktionen höherer Ordnung
--
twice f x = f (f x)
{-
map f []     = []
map f (x:xs) = f x:map f xs
-}

{-
? twice (\x -> x*x) 2
16 :: Int
? map ord "Hallo!"
[72, 97, 108, 108, 111, 33] :: [Int]
? 
-}

--
-- Benutzerdefinierte Datentypen: Binärbäume
--
data BTree a = MTTree | Branch a (BTree a) (BTree a)
leaves MTTree         = 1
leaves (Branch x l r) = leaves l + leaves r

numtree = Branch 10 (Branch 5  MTTree
                               MTTree)
                    (Branch 13 MTTree
		               (Branch 21 MTTree MTTree))

{-
? leaves numtree
5 :: Int
? 
-}

--
-- Sortieren
--
qs1 [] = []
qs1 (x:xs) = qs1 (filter (<x) xs) ++ [x] ++ qs1 (filter (>=x) xs)
{-
filter p [] = []
filter p (x:xs) | p x = fpxs
                | otherwise = x:fpxs
  where fpxs = filter p xs
-}

qs2 [] = []
qs2 (x:xs) = qs2 [y | y <- xs, y<x] ++ [x] ++ qs2 [y | y <- xs, y>=x]

{-
? qs1 [97, 98, 97, 258, 259, 260, 256, 261, 260, 257, 263, 266, 261]
[97, 97, 98, 256, 257, 258, 259, 260, 260, 261, 261, 263, 266] :: [Int]
? 
-}

--
-- Backtracking
--
queens :: Int -> [[Int]]
queens n = try n [1..n]

try 0 rows = [[]]
try n rows = [ r:s | s <- try (n-1) rows, r <- rows, safe r 1 s ]

safe r i [] = True
safe r i (d:ds) = r /= d && r+i /= d && r-i /= d && safe r (i+1) ds

{-
? queens 4
[[3, 1, 4, 2], [2, 4, 1, 3]] :: [[Int]]
? 
-}

--
-- Textkompression (LZW)
--
data PTrie k v = PT k v (PTrie k v) (PTrie k v) (PTrie k v) 
               | PTNil
type CodeTable = PTrie Char Int

codeString :: (String, Int) -> Int -> CodeTable ->
		((String, Int), CodeTable)
codeString s@([],_) _ _
	= (s, PTNil)
codeString s@(c:_,_) nextCode PTNil
	= (s, PT c nextCode PTNil PTNil PTNil)
codeString s@(c:cs,_) nextCode (PT key code p l r)
	| c < key   = (ls, PT key code p  l1 r)
	| c > key   = (rs, PT key code p  l  r1)
	| otherwise = (ps, PT key code p1 l  r)
  where (ls,l1) = codeString s nextCode l
	(rs,r1) = codeString s nextCode r
	(ps,p1) = codeString (cs,code) nextCode p

encode :: CodeTable -> String -> [Int]
encode initialTable cs = f (cs,0) 256 initialTable
  where f ([],_) _ _ = []
	f s nextCode table = code: f (cs,0) (nextCode+1) table'
	  where ((cs,code),table') = codeString s nextCode table

initialTable :: CodeTable
initialTable = PT 'b' 98 PTNil  (PT 'a' 97 PTNil PTNil PTNil)
				(PT 'c' 99 PTNil PTNil PTNil)

{-
? encode initialTable "aaaaaaaaaaaaaaaaaa"
[97, 256, 257, 258, 259, 257] :: [Int]
?
-}