Cvičení z Neprocedurálního programování - 8

1-opakovani.hs

-- Tato možnost zapne všechny warningy:
{-# OPTIONS_GHC -Wall #-}

-- Opakování:

-- Funkce třech argumentů
sectiTri :: Int -> Int -> Int -> Int
sectiTri x y z = x + y + z

-- Pokud ji částečně aplikujeme na dva argumenty,
-- dostaneme funkci dvou argumentů
prictiJednicku :: Int -> Int
prictiJednicku = sectiTri 0 1

-- >>> prictiJednicku 42
-- 43

-- Základní typy:

-- Int
-- Char
-- String = [Char]
-- [a]               .. seznam áček
-- (a, b)            .. dvojice
-- Double

2-plus-a-krat.hs

-- Datové typy
{-# OPTIONS_GHC -Wall #-}

-- Součtové typy:
-- Barva je buď červená, nebo zelená, nebo modrá
data Barva = Cervena | Zelena | Modra

barvaToString :: Barva -> String
barvaToString barva =
    case barva of                 -- rozeber možnosti `barva`
        Cervena -> "Cervena"      -- ... pokud je červená
        Zelena  -> "Zelena"       -- ... pokud je zelená
        Modra   -> "Modra"        -- ... pokud je modrá

-- >>> barvaToString Modra
-- "Modra"

jeBarvaCervena :: Barva -> Bool
jeBarvaCervena barva =
    case barva of
        Cervena -> True
        _       -> False          -- default = False

-- >>> jeBarvaCervena Zelena
-- False

-- Pattern matching v argumentu funkce
-- jde udělat i na top-level úrovni!

barvaToString' :: Barva -> String
barvaToString' Cervena = "Cervena"
barvaToString' Zelena = "Zelena"
barvaToString' Modra = "Modra"

jeBarvaCervena' :: Barva -> Bool
jeBarvaCervena' Cervena = True
jeBarvaCervena' _       = False  -- default = False


-- Intuitivně si můžeme předstvovat, že:

-- data Int =  ... | -2 | -1 | 0 | 1 | 2 | ...
-- data Char = 'a' | 'b' | 'c' | ... | 'z' | 'A' | 'B' | ...
-- data Bool = True | False 
-- [Poznámka: Bool je takhle _fakt_ definován :D]

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

-- >>> fibonacci 10
-- 34

-- Produktové typy:

data RGB = MkRGB Int Int Int -- červená, zelená, modrá

-- MkRGB je funkce typu Int -> Int -> Int -> RGB

fialova :: RGB
fialova = MkRGB 255 0 255

-- Zde můžeme pattern matchovat jednotlivé prvky
-- a přiřadit jim proměnné.
-- Pokud nějakou nechceme využít, můžeme napsat `_`.
pridejCervenou :: RGB -> RGB 
pridejCervenou (MkRGB _ g b) = MkRGB 255 g b

-- Konverze z RGB na trojici není automatická
-- i přes to, že jsou tyto typy izomorfní.
-- Pokud chcete funkci z RGB do trojice intů,
-- musíte si ji napsat sami
vyrobTrojici :: RGB -> (Int, Int, Int)
vyrobTrojici (MkRGB r g b) = (r, g, b)

foo :: (Int, Int, Int)
-- nefunguje:
-- foo = fialova

-- funguje:
foo = vyrobTrojici fialova

3-adt.hs

-- ADT
{-# OPTIONS_GHC -Wall #-}

-- součtové & produktové typy dohromady
-- => "Algebraický Datový Typ"

data Barva                -- Barva je
    = Cervena             -- ... buď červená
    | Zelena              -- ... nebo zelená
    | Modra               -- ... nebo modrá
    | RGB Int Int Int     -- ... nebo reprezentovaná jako RGB (tři inty)

-- Je barva červená?
jeBarvaCervena :: Barva -> Bool
jeBarvaCervena Cervena       = True     -- pokud je to 'Cervena', pak ano
jeBarvaCervena (RGB 255 _ _) = True     -- pokud je to 'RGB 255 _ _', pak ano
jeBarvaCervena _             = False    -- jinak ne

-- Pojmenuje barvu, ukázka pattern matchingu
pojmenujBarvu :: Barva -> String
pojmenujBarvu Cervena = "cervena"
pojmenujBarvu Modra = "modra"
pojmenujBarvu (RGB 255 0 255) = "fialova"
pojmenujBarvu (RGB _ 255 _) = "nazelenala? asi?"
pojmenujBarvu _ = "neznam :(" 

-- Příklad modelování reálného světa pomocí typů:

data SachovaBarva = Cerna | Bila
data SachovyDruh = Pesak | Jezdec | Kral | Strelec | Kralovna | Vez

data Figurka = Figurka SachovaBarva SachovyDruh

bilyKral :: Figurka
bilyKral = Figurka Bila Kral


-- Co si vyrobit seznamy? :)


data Seznam              -- Seznam je
    = Cons Int Seznam    -- ... buď číslo a zbytek seznamu
    | Nil                -- ... nebo prázdný seznam
  deriving (Show, Eq)    -- Tohle je magické zaříkadlo, aby šel náš seznam vypsat v GHCi
                         --   příště vysvětlím pořádně :)

-- Seznam obsahující [1, 2, 3]
prvniTri :: Seznam
prvniTri = Cons 1 (Cons 2 (Cons 3 Nil))

-- Rekurzivně zjistí délku seznamu
delkaSeznamu :: Seznam -> Int
delkaSeznamu Nil = 0
delkaSeznamu (Cons _ xs) = 1 + delkaSeznamu xs

-- Poznámka: Typicky používáme x jako hlavu seznamu a xs jako ocásek/zbytek seznamu.
-- Často totiž máme seznam nějakého obecného typu a v tu chvíli nemá
-- konkrétnější pojmenování smysl...

{-
Proč nepoužívat `head` a `cons`:
Vezměte si následující funkce:

head' :: Seznam -> Int
head' (Cons x _) = x

tail' :: Seznam -> Seznam
tail' (Cons _ xs) = xs

Co by měly tyto funkce vracet v případě `Nil`?
Žádná z možností není moc hezká,
Haskell prostě vypíše error... :/

Proto je dobré používat raději pattern matching!
-}

-- v Haskellu se 'Cons' píše jako (:) ... a tedy 'Cons x xs' je '(x:xs)'
--               'Nil'  píše jako []

prvniTriCisla :: [Int]
prvniTriCisla = [1, 2, 3] -- také jde napsat jako (1:2:3:[]) explicitně

-- Délka seznamu
delka :: [Int] -> Int
delka [] = 0
delka (_:xs) = 1 + delka xs

-- >>> delka prvniTriCisla
-- 3

{- Pattern matching pro seznamy:

[] ... prázdný seznam
xs ... libovolný seznam (i prázdný)
[x] ... seznam o právě jednom prvku
[x, y] ... seznam o právě dvou prvcích 

(x:xs) ... seznam o alespoň jednom prvku
(x:y:xs) ... seznam o alespoň dvou prvcích...
-}

-- take' n xs ... vezme prvních n prvků ze seznamu xs
take' :: Int -> [Int] -> [Int]
take' 0 _ = []                      -- pokud chceme vzít 0 prvků, pak vrátíme prázdný seznam
take' _ [] = []                     -- pokud chceme brát z prázdného seznamu, tak vrátíme prázdný seznam
take' n (x : xs) =                  -- jinak rozdělíme seznam na (x:xs)
    let rest = take' (n - 1) xs        -- zarekurzíme se: vezmeme (n-1) prvků ze seznamu xs a uložíme do 'rest'
     in x : rest                       -- vrátíme 'x' připojený na začátek 'rest'

4-parametricke-typy.hs

-- Parametrické typy -- typy s parametrem ("generika" v C#)
{-# OPTIONS_GHC -Wall #-}

identitaProCisla :: Int -> Int
identitaProCisla x = x 

-- >>> identitaProCisla 42
-- 42

-- čteme "pro každý typ a: a -> a"
-- typové proměnné se píšou malými písmenky!
-- jsou obecně kvantifikované (s provšechnítkem)
identita :: a -> a
identita x = x

{-
V jiných jazycích:

T identita<T> (T x) {
    return x;
}

template <typename T>
T identita (T x) {
    return x;
}
-}


-- Tyto typy nejsou pro identitu platné!

-- (čteme pro každé a, b: a -> b)
--identita1 :: a -> b
--identita1 x = x          -- nejde, a se musí rovnat b!

--identita2 :: a -> Int
--identita2 x = x          -- nejde, a by se musel rovnat 'Int'!

--identita3 :: Int -> a
--identita3 x = x          -- nejde, a by se musel rovnat 'Int'!

-- Tato funkce vezme funkci a aplikuje ji dvakrát
dvakrat :: (a -> a) -> a -> a
dvakrat f x = f (f x)

-- >>> dvakrat (\x -> x + 2) 1
-- 5

-- Vezme funkci z 'a' do 'b', seznam 'a'ček a vrátí seznam 'b'ček
map' :: (a -> b) -> [a] -> [b]
map' _ [] = []                      -- pro prázdný seznam vrátí prázdný seznam
map' f (x : xs) = f x : map' f xs   -- jinak vrátí (f x) na začátku a zarekurzí se na zbytek seznamu

-- 'map' jsme si vyrobili i v Prologu,
-- připomínám, že je to dobrý způsob jak si pořídit "for loop"
-- (jak udělat něco pro každý prvek seznamu)

-- >>> map (\x -> x + 2) [1..5]
-- [3, 4, 5, 6, 7]

-- >>> map (\x -> x * 2) [1..5]
-- [2, 4, 6, 8, 10]

-- 'filter' vezme predikát a seznam a vrátí prvky vyhovující predikátu
filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' p (x:xs) = 
    case p x of                       -- data Bool = True | False , takže můžeme pattern matchovat
        True  -> x : filter' p xs         -- pokud predikát platí, přidáme x a zarekurzíme se
        False ->     filter' p xs         -- jinak se jen zarekurzíme
        
-- >>> filter (\x -> x > 3) [1..5]
-- [4, 5]

filter'' :: (a -> Bool) -> [a] -> [a]
filter'' _ [] = []
filter'' p (x:xs) = 
    if p x then x : filter'' p xs        -- to samé, ale pomocí 'if-then-else'
           else     filter'' p xs

filter''' :: (a -> Bool) -> [a] -> [a]
filter''' _ [] = []
filter''' p (x:xs)
    | p x       = x : filter''' p xs     -- to samé, ale pomocí stráží (guards)
    | otherwise =     filter''' p xs

-- Příklad pro guards:
pojmenuj :: Int -> Int -> String
pojmenuj x y
    | x > y     = "x je vetsi"
    | x == y    = "stejne"
    | otherwise = "y je vetsi"

-- Verze výše je rozhodně hezčí než tohle:
pojmenuj' :: Int -> Int -> String
pojmenuj' x y =
    if x > y then "x je vetsi"
             else if x == y then "stejne"
                            else "y je vetsi"

-- Často používané operátory u seznamů.
-- Zkuste odhadnout co dělají dle jejich typu
-- (++) :: [a] -> [a] -> [a]             ... O(N)
-- (!!) :: Int -> [a] -> a               ... O(N)

-- Klasický příklad --- quicksort! :)
quicksort :: [Int] -> [Int]
quicksort [] = []
quicksort (pivot:rest) = quicksort left ++ [pivot] ++ quicksort right
    where
        -- mensi nez pivot => nalevo od pivota
        left :: [Int]
        left = filter (\x -> x < pivot) rest
        
        -- vetsi nebo rovno nez pivot => napravo od pivota
        right :: [Int]
        right = filter (\x -> x >= pivot) rest


nasSeznam = [10,9..1 :: Int]

-- >>> quicksort nasSeznam
-- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]