-- komentovaný zdroják k druhému cvičení IB015
{- Haskellovská knihovna je členěná do modulů, základem je modul Prelude,
 - který je přítomný vždy, další moduly můžeme importovat
 - ve zdrojáku importujeme direktivou import
 - v interpretru importujeme :m + <modul>
 -}
import Data.Char -- modul pro práci se znaky (toUpper, ...)

-- rekurzivní definice -- využívá volání sebe sama na menším problému
-- řešení rozložíme
fact :: Integer -> Integer
fact 0 = 1 -- záklaní (zastavující) případ -- je nutný pokud rekurze má skončit
           -- 0 je vzorem, na pořadí záleží
fact n = n * fact (n - 1) -- rekurzivní případ
{- příklad výpočtu:
 - fact 3 ~> 3 * fact (3 - 1) ~> 3 * fact 2 ~> 3 * 2 * fact (2 - 1)
 - ~> 3 * 2 * fact 1 ~> 3 * 2 * 1 * fact (1 - 1) ~> 3 * 2 * 1 * fact 0
 - ~> 3 * 2 * 1 * 1 ~>* 6
 - jen v poslením vyhodocení fact se použije první řádek definice
 -}

-- předchozí verze cyklí pro záporná čísla
fact' :: Integer -> Integer
fact' 0 = 1
fact' n = if n > 0 then n * fact (n-1) -- záporná čísla nelze postihnou vzorem
                   else error "Záporné číslo ve fact!" 
                      -- odsazení zajištuje, že if pokračuje na dalším řádku
                      -- funkce error ukončí program s chybovou hláškou

-- umocnování rekurzivně
na :: Double -> Int -> Double
_ `na` 0 = 1
z `na` n = z * (z `na` (n-1))

-- ǓKOL: definujte funkci na' která se na kladných exponentech chová jako na
-- ale pracuje i se zápornými exponenty
-- použijte funkci na, nepoužívejte (^^)
na' :: Double -> Int -> Double
na' z n = if n < 0 then 1 / (z `na` (abs n))
                   else z `na` n

-- dvojitý faktoriál
dfct :: Integer -> Integer
dfct 0 = 1 -- dvě zastavující podmínky: pro sudá čísla
dfct 1 = 1 --                           pro lichá čísla
dfct n = n * dfct (n - 2)

-- obskurní způsob jak vypočítat druhou mocninu
sq :: Integer -> Integer
sq 0 = 0
sq n = sq (n-1) + 2 * n - 1

{- SEZNAMY
 - jedna ze základních datový struktur Haskellu
 - prázdný seznam: nulární datový konstruktor (konstanta) []
 - operátor (:) :: a -> [a] -> [a]
 - je binární datový konstruktor seznamum který přiřetězuje jeden prvek
 - na začátek seznamu
 - konstruktory lze používat ve vzorech
 -}

-- identická funkce na seznamech -- seznam rozloží a opět složí
identita :: [a] -> [a] -- polymorfní datový typ
-- funkce přijímá seznam libovolného typu prvků a vrací opět seznam stejného typu
identita [] = [] -- vzor prázdného seznamu
identita (x : xs) = x : identita xs -- vzor neprázdného seznamu

-- délka seznamu
delka :: [a] -> Integer -- length
delka [] = 0
delka (x : xs) = 1 + delka xs
{- delka [1,2,3] ~> 1 + delka [2,3] ~> 1 + 1 + delka [3]
   ~> 1 + 1 + 1 + delka [] ~> 1 + 1 + 1 + 0 ~>* 3
--}

-- následující funkce existují i v  standartní haskellovské knihovně
-- tyto názvy uvádím v komentáří

-- hlava seznamu je jeho první prvek
hlava :: [a] -> a -- head
hlava []     = error "hlava: Prázdný seznam"
hlava (x:xs) = x

-- telo seznamu je opět seznam -- bez prvního prvku
telo :: [a] -> [a] -- tail
telo [] = error "telo: Prázdný seznam"
telo (x:xs) = xs

posledni :: [a] -> a -- last
posledni [] = error "posledni: Prázdný seznam"
posledni (x : []) = x -- vzor jednoprvkového seznamu,  vzory lze zanořovat
posledni (x : xs) = posledni xs
-- posledni [1,2] ~> posledni [2] ~> 2

zacatek :: [a] -> [a] -- init
zacatek [] = error "zacatek: Prázdný seznam"
zacatek (_ : []) = []
zacatek (x : xs) = x : zacatek xs
-- zacatek [1,2,3] ~> 1 : zacatek [2,3] ~> 1 : 2 : zacatek (3:[]) ~>
--  1 : 2 : []

-- funkce map -- bere unírní funci a seznam, aplikuje funkci na každý prvek seznamu
map' :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f (x : xs) = f x : map' f xs
{- map' toUpper [ 'a', 'b' ]
   ~> toUpper 'a' : map' toUpper [ 'b' ]
   ~> 'A' : map' toUpper [ 'b' ]
   ~> 'A' : toUpper 'b' : map' toUpper []
   ~> 'A' : 'B' : map' toUpper []
   ~> 'A' : 'B' : []
   === "AB"
   poslední krok není výpočet ale jen jiný způsob zápisu
 -}

-- funkce filter -- bere unární predikát a seznam a vrací prvky seznamu
-- které splňují predikát (predikát je funkce vracející Bool)
filter' :: (a -> Bool) -> [a] -> [a]
filter' _ []       = []
filter' p (x : xs) = if p x then x : filter' p xs
                            else     filter' p xs

plus5 :: Integer -> Integer
-- plus5 x = 5 + x -- nepraktický způsob jak definovat přičítač pětky
-- plus5 = (+) 5 -- použití částečné aplikace
plus5 = (5 +) -- použití levé operátorové sekce

-- delenoPeti x = x / 5
delenoPeti = (/ 5) -- použití pravé operátorové sekce

-- funkce zip spojí 2 seznamy do seznamu dvojic tak, že prvním prvkem výsledku
-- je dvojice prvních prvů příslušných seznamů, 2. prvkem dvojice druhých,...
-- seznam končí pokud zkončí alespoň jede ze vstupních seznamů
zip' :: [a] -> [b] -> [(a, b)]
zip' (x : xs) (y : ys) = (x, y) : zip' xs ys -- oba vzory zastupují neprázdné seznamy
zip' _        _        = [] -- alespoň jeden ze seznamů je prázdný (jinak by e použilo ^)
{- alternativně:
zip' []       _        = []
zip' _        []       = []
zip' (x : xs) (y : ys) = (x, y) : zip' xs ys
-}

-- zobecněný zip používají k stovoření výsledku libovolnou binární funkci
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f (x : xs) (y : ys) = f x y : zipWith' f xs ys
zipWith' f _        _        = []

-- zip' = zipWith' (,) -- definice zip pomocí zipWith a částečné aplikace

-- unzip převede seznam dvojic na dvojici seznamů
unzip' :: [(a,b)] -> ( [a], [b] )
unzip' [] = ( [], [] )
unzip' ( (x,y) : xys ) = let (xs, ys) = unzip' xys -- rekurzivní volání v let s vzory
                          in ( x:xs, y:ys )