===== Cvičení 6  =====

   * Seznameni s prostredim Hugs/WinHugs: [[http://ai.ms.mff.cuni.cz/~vyskocil/WinHugs.zip]]
   * Download [[http://www.haskell.org|GHC]]
   * [[http://www.haskell.org/tutorial/|A Gentle Introduction To Haskell]] 

==== Simple Pattern Matching and Guards ====

<code haskell>
fact :: Integer -> Integer
fact 0 = 1
fact n = n * fact (n-1)

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

-- effective version:
twofibs :: Int -> (Int,Int)
twofibs 0 = (0,1)
twofibs n = (b,a+b) where (a,b) = twofibs (n-1) 

fib_eff :: Int -> Int
fib_eff n = fn where (_,fn) = twofibs n

-- guards
mymax :: Int -> Int -> Int
mymax x y = if (x>y) then x else y

mymax2 x y | x>y       = x
           | otherwise = y
</code>

==== Lists and Pattern Matching ====

<code haskell>

prvnich :: Int -> [a] -> [a]
prvnich 0 xs = []
prvnich n (x:xs) = (x:prvnich (n-1) xs)

otoc :: [a] -> [a]
otoc xs = otoc_acc xs [] where
   otoc_acc [] acc = acc
   otoc_acc (x:xs) acc = otoc_acc xs (x:acc)

spoj :: [a] -> [a] -> [a]
spoj [] ys = ys
spoj (x:xs) ys = (x:spoj xs ys)

sluc :: [[a]] -> [a]
sluc [] = []
sluc (xs:xss) = spoj xs (sluc xss)

split :: [a] -> ([a],[a])
split [] = ([],[])
split [x] = ([x],[])
split (x:y:xs) = (x:fs,y:ss) where (fs,ss) = split xs

merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) | x<y       = (x:merge xs (y:ys))
                    | otherwise = (y:merge (x:xs) ys)

mergesort :: Ord a => [a] -> [a]
mergesort [] = []
mergesort [x] = [x]
mergesort xs = merge (mergesort ls) (mergesort rs) 
   where (ls,rs) = split xs
</code>

==== Data Types ====

<code haskell>

data Colors = Red | Green | Blue deriving Eq
-- Red :: Colors 

isred :: Colors -> Bool
isred Red = True
isred _ = False

isred2 c = (c == Red) -- only with "deriving" above

data Tree = Leaf Int | Node Tree Tree -- deriving Show
-- Leaf :: Int -> Tree
-- Node :: Tree -> Tree -> Tree

instance (Show Tree) where
   show (Leaf a) = show a
   show (Node l r) = "<" ++ show l ++ ":" ++ show r ++ ">"

hloubka :: Tree -> Int
hloubka (Leaf _) = 1
hloubka (Node l r) = 1 + mymax (hloubka l) (hloubka r)

listy :: Tree -> [Int]
listy (Leaf a) = [a]
listy (Node l r) = spoj (listy l) (listy r)

data NTree a = NNode a [NTree a]

cesty :: NTree a -> [[a]]
cesty (NNode a []) = [[a]]
cesty (NNode a ts) = map (a:) (sluc (map cesty ts))


</code>