Skip to content

Instantly share code, notes, and snippets.

@jiribenes
Last active May 13, 2021 14:41
Show Gist options
  • Save jiribenes/c5364bb56736ed812fdb98a25f9ce087 to your computer and use it in GitHub Desktop.
Save jiribenes/c5364bb56736ed812fdb98a25f9ce087 to your computer and use it in GitHub Desktop.
Cvičení z Neprocedurálního programování - 11
-- 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ý"
-- 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)
-- 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
{-
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)"
-- 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment