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

1-opakovani.hs

-- Opakování datových typů:

-- součtový typ
data Barva
    = Cervena -- konstruktor typu
    | Zelena
    | Modra
    deriving (Eq, Show)

zelenaBarva :: Barva
zelenaBarva = Zelena

-- Používáme pattern matching na rozbalení
barvaToInt :: Barva -> Int
barvaToInt b = case b of
    Cervena -> 42
    Zelena -> 0
    _ -> -1
    
-- Součinový typ
data Pair a = Pair a a
    deriving (Eq, Show)

-- Zase používáme pattern matching na rozbalení
sectiDvojici :: Pair Int -> Int
sectiDvojici (Pair x y) = x + y

-- Kombinace součtového a součinového typu
data Strom a = Konec | Vetev (Strom a) a (Strom a)
    deriving (Eq, Show)

-- Příklad rozbalení
hodnota :: Strom Int -> Int
hodnota Konec = -1
hodnota (Vetev _l x _r) = x
{-
-- Bez syntaktického cukru:

hodnota s = case s of
    Konec -> -1
    Vetev _l x _r -> x
-}

-- Preferujte pattern matching před strážemi.
-- Pokud používáte jednu z následujících funkcí:
--
-- isJust :: Maybe a -> Bool, isNothing :: Maybe a -> Bool, fromJust :: Maybe a -> a
--
-- tak si rozmyslete, jestli raději nechcete použít pattern matching.
-- 

-- Příklad, který používá jak stráže (pro booleovské podmínky),
-- tak pattern matching.
satisfies :: (a -> Bool) -> Maybe a -> Bool
satisfies p (Just x)  
    | p x = True
    | otherwise = False
satisfies _ Nothing = False

-- Datový typ pro osobu
data Person = Person String String
    deriving (Eq, Show)

firstName :: Person -> String
firstName (Person x _) = x

lastName :: Person -> String
lastName (Person _ x) = x

karel :: Person
karel = Person "Karel" "Nějaký"

-- Co kdybychom chtěli něco, co se víc blíží structu z C++?
data Osoba = Osoba { krestniJmeno :: String, prijmeni :: String }
    deriving (Eq, Show)
-- automaticky definuje ty funkce 'krestniJmeno' a 'prijmeni'

-- vytvořit můžeme buď normálně
karel2 :: Osoba
karel2 = Osoba "Karel" "Další"

-- nebo pomocí record syntaxe
karel3 :: Osoba
karel3 = Osoba { prijmeni = "Jiný", krestniJmeno = "Karel" }
-- Všimněte si toho, že mohou být v jiném pořadí.
-- Tohle se hodí pro součinové typy, které mají hodně položek.

-- Record update:
-- Tohle jsem na cvičení nezmiňoval, ale pomocí syntaxe výše se dá i updatovat:
karel4 = karel3 { prijmeni = "Úplněnový" }

-- >>> karel4
-- Osoba "Karel" "Úplněnový"

2-fronta.hs

-- Funkcionální fronta pomocí dvou zásobníků v O(1) amortizovaně:
--
-- Nové prvky jdou na začátek `revBack`
-- Prvky se odebírají z `front`.
-- Je-li `front` prázdný, otočíme `revBack` a označíme jej jako nový `front`.
data Queue a = Queue { front :: [a], revBack :: [a] } 
    deriving (Eq, Show)

empty :: Queue a
empty = Queue [] []

enqueue :: a -> Queue a -> Queue a
enqueue x (Queue f rb) = Queue { front = f, revBack = (x:rb) }

dequeue :: Queue a -> Maybe (a, Queue a)
dequeue (Queue [] []) = Nothing
dequeue (Queue (x:f) rb) = Just (x, Queue f rb)
dequeue (Queue [] rz) = dequeue $ Queue (reverse rb) []

fronta :: Queue Int
fronta = 2 `enqueue` (1 `enqueue` empty)

3-pologrupy-monoidy.hs

-- Měli jsme typové třídy:
-- Show, Eq, Ord

-- Teď si povíme o pár dalších:

{- POLOGRUPA (Semigroup)
definováno jako

class Semigroup a where
  (<>) :: a -> a -> a
  ...
  
je asociativní operace, tedy mělo by platit, že:
pro každé a, b, c: (a <> b) <> c == a <> (b <> c)

Typické příklady:

instance Semigroup [a] where
  (<>) = (++)
  
instance Semigroup a => Semigroup (Maybe a) where
    Nothing <> Nothing = Nothing
    Nothing <> Just y = Just y
    Just x <> Nothing = Just x
    Just x <> Just y = Just $ x <> y

MONOID je pologrupa, která má neutrální prvek.
Je definována jako

class Semigroup a => Monoid a where
  mempty :: a
  ...

Mělo by tedy platit navíc, že:
pro každé a: a <> mempty = mempty <> a = a

Typické příklady:

instance Monoid [a] where
  mempty = []
  
instance Semigroup a => Monoid (Maybe a) where
  mempty = Nothing
-}

-- Příklady:
-- wrapper pro součet
newtype Sum a = Sum { getSum :: a }
-- wrapper pro součin
newtype Product a = Product { getProduct :: a }

-- Součet s nulou tvoří monoid
instance Num a => Semigroup (Sum a) where
    Sum a <> Sum b = Sum $ a + b

instance Num a => Monoid (Sum a) where
    mempty = Sum 0
    
-- Součin s jedničkou tvoří monoid
instance Num a => Semigroup (Product a) where
    Product a <> Product b = Product $ a * b

instance Num a => Monoid (Product a) where
    mempty = Product 1

-- Fizz Buzz
-- je klasický problém, který se dává na interview
-- Pro číslo i: pokud je dělitelné 3, vypište Fizz, pokud 5, vypište Buzz, jinak vypište číslo

-- Příklad:
-- 1, 2, Fizz, 4, Buzz, 5, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, ... 

-- Klasické řešení:
fizzbuzz :: Int -> String
fizzbuzz i
    | i `mod` 3 == 0 && i `mod` 5 == 0 = "FizzBuzz"
    | i `mod` 3 == 0 = "Fizz"
    | i `mod` 5 == 0 = "Buzz"
    | otherwise = show i

-- Problém: Tohle se moc neškáluje.
-- Kdybychom přidali "Wuzz" pro dělitele sedmičky, tak musíme přidat hodně edge casů.

-- Alternativní řešení:
-- 'fizzes' je nekonečný seznam typu 'Maybe String', který má každý třetí prvek Just "Fizz"
-- jinak Nothing
fizzes :: [Maybe String]
fizzes = cycle [Nothing, Nothing, Just "Fizz"]
-- podobně 'buzzes' pro Buzz
buzzes :: [Maybe String]
buzzes = cycle [Nothing, Nothing, Nothing, Nothing, Just "Buzz"]

-- Když zkombinujeme tyto dva nekonečné seznamy pomocí zipWith a `<>`,
-- dostaneme skoro to, co bychom chtěli:
fizzbuzzes :: [Maybe String]
fizzbuzzes = zipWith (<>) fizzes buzzes

-- >>> take 15 $ fizzbuzzes
-- [Nothing,Nothing,Just "Fizz",Nothing,Just "Buzz",Just "Fizz",Nothing,Nothing,Just "Fizz",Just "Buzz",Nothing,Just "Fizz",Nothing,Nothing,Just "FizzBuzz"]

-- Nyní každý Nothing nahradíme samotným číslem
fizzbuzz' :: Int -> [String]
fizzbuzz' n = zipWith fromMaybe (map show [1..n]) fizzbuzzes

-- >>> fizzbuzz' 15
-- ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

-- Pomocná funkce, která byla na minulém cvičení.
fromMaybe :: a -> Maybe a -> a
fromMaybe def Nothing = def
fromMaybe _ (Just x) = x

-- Máme tedy elegantní řešení využívající nekonečné seznamy, které je celkem jednoduché
-- a hlavně dost rozšířitelné!

-- Cvičení:
-- Vezměte si tento newtype:
newtype Nebo a = Nebo { getNebo :: Maybe a }
-- a vyrobte instanci pro Semigroup a Monoid,
-- která se bude chovat následovně:

-- >>> Nebo (Just 12) <> Nebo (Just 24)
-- Nebo (Just 12)

-- >>> Nebo Nothing <> Nebo (Just 5)
-- Nebo (Just 5)

-- >>> Nebo (Just 42) <> Nebo Nothing
-- Nebo (Just 42)

instance Semigroup (Nebo a) where
  Nebo x <> Nebo y = _ -- TODO
  
instance Monoid (Nebo a) where
  mempty = _ -- TODO
  
-- BONUS: Dokažte si, že je to doopravdy pologrupa a monoid
-- (Ověřte, že platí pravidla výše)

-- Hezké cvičení:
-- Přečtěte si, jak pomocí pologrup počítat rychle a elegantně Fibonacciho čísla:
-- https://www.haskellforall.com/2020/04/blazing-fast-fibonacci-numbers-using.html

4-druhy.hs

{-
Každá hodnota má svůj typ:

>>> :t "Ahoj"
String

>>> :t Just 42
Maybe Int

>>> :t [Just "Ahoj", Nothing]
[Maybe String]

>>> :t \x -> show (x + 2)
Int -> String

Co ale typy? Je něco jako typ typu?

>>> :t Int
error

Ano, říká se mu _druh_, anglicky kind.

>>> :k Int
Int :: *

>>> :k Char
Char :: *

Kind * znamená, že ten typ je konkrétní -- reprezentovatelný

>>> :k Int -> String
Int -> String :: *

>>> :k [String]
[String] :: *

>>> :k Maybe Int
Maybe Int :: *

Ne všechny typy jsou ale rovnou reprezentovatelné,
například samotné 'Maybe':

>>> :k Maybe
Maybe :: * -> *

Tohle znamená, že 'Maybe' dostane konkrétní typ a vrátí konkrétní typ
(podobně jako funkce 'a -> a' vezme hodnotu typu 'a' a vrátí hodnotu typu 'a')

>>> :k []
[] :: * -> *

Podobně jako List není nic "opravdového" v C#/Javě/C++,
ale List<Int> ano.
-}

data Strom a = Konec | Vetev a (Strom a) (Strom a)

{-

>>> :k Strom
Strom :: * -> *


Druhy mohou být ale i o trochu složitější!


-}

data Pair a b = Pair a b

{-
>>> :k Pair
Pair :: * -> * -> *

Pair potřebuje dva typy, aby z něj byl konkrétní typ!

Tohle je podobné jako třeba Pair<T, U> v Javě/C# nebo std::pair<T, U> v C++

>>> :k Pair Int
Pair Int :: * -> *

"potřebuje ještě jeden konkrétní typ, aby to byl konkrétní typ"


>>> :k (->)
(->) :: * -> * -> *

Funkční šipka má stejný druh jako Pair

>>> :k ((->) Int) String
((->) Int) String :: *

(->) Int String se zapisuje obvykle jako Int -> String ;)
-}


-- Typové třídy také mají svůj druh:
-- >>> :k Semigroup
-- Semigroup :: * -> Constraint

-- Reálně to znamená něco jako "dej mi konkrétní typ a já ti dám omezení (Constraint)"

5-funktor.hs

-- Mnoho typů je kontejnerovitých -- mají druh * -> *
-- Co kdybychom chtěli tuto "kontejnerovitost" nějak vyjádřit typovou třídou?

-- Od toho je třída Functor!

{-
class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b
  ...
-}

-- 'fmap' je něco jako zobecněné 'map'
-- pro libovolný kontejnerovitý typ

{-

instance Functor [] where
  fmap = map
  
instance Functor Maybe where
  fmap f (Just x) = Just $ f x
  fmap _ Nothing  = Nothing

-}

-- >>> fmap (+2) [1, 2, 3]
-- [3, 4, 5]

-- >>> fmap (+2) (Just 3)
-- Just 5

-- >>> fmap (+2) Nothing
-- Nothing

-- >>> fmap (fmap (+2)) [Just 5, Nothing, Just 3]
-- [Just 7, Nothing, Just 5]

data Strom a = Konec 
             | Vetev (Strom a) a (Strom a)
  deriving (Eq, Show)

-- Všimněte si, že tady je 'Functor Strom' a ne 'Functor (Strom a)'!
instance Functor Strom where
    fmap _ Konec = Konec
    fmap f (Vetev l x r) = Vetev (fmap f l) (f x) (fmap f r)

-- Pro funktory musí platit následující pravidla:
-- fmap id = id
-- fmap (f . g) = fmap f . fmap g

-- Cvičení:
-- Napište si instanci pro Functor pro následující k-nární strom:
data RoseTree a = Node a [RoseTree a]
  deriving (Eq, Show)