Monoidy, Foldable, Traversable
IB016 Seminář z funkcionálního programování
Martin Kurečka, Adam Matoušek
(původní autoři slajdů Vladimír Štill, Martin Ukrop)
Fakulta informatiky, Masarykova univerzita
Jaro 2021
IB016: Cvičení 06 Jaro 2021 1 / 38
Monoidy
IB016: Cvičení 06 Jaro 2021 2 / 38
Motivace I: zpracovávání argumentů příkazové řádky
Chtěli bychom zpracovat argumenty příkazové řádky jako nastavení
programu.
./run -v -opt=o1 -q -opt=o2
-v (verbose) zapíná ladicí výstupy
-q (quiet) vypíná ladicí výstupy
program se vždy chová podle posledního přepínače -v/-q
každý výskyt -opt přidává programu libovolný textový
argument
výchozí nastavení je bez ladicích výstupů a bez dalších
argumentů
IB016: Cvičení 06 Jaro 2021 3 / 38
Datový typ pro konfiguraci
Nachystejme si na nastavení vhodný datový typ:
data Config = Config
{ verbose :: Bool
, options :: [String]
} deriving (Eq, Show)
IB016: Cvičení 06 Jaro 2021 4 / 38
Představa zpracování
každý přepínač je jedna změna oproti výchozímu nastavení
každý přepínač reprezentuje elementární validní nastavení
tato nastavení můžeme sloučit nějakou vhodnou funkcí
-v -opt=o1 -q -opt=o2
def { def { def { def {
verbose options verbose options
= True = ["o1"] = False = ["o2"]
} } } }
def = Config { verbose = False, options = []}
Jaké vlastnosti by měla mít funkce ?
IB016: Cvičení 06 Jaro 2021 5 / 38
Vlastnosti funkce : uzavřenost
Je množina všech platných konfigurací uzavřená na funkci ?
IB016: Cvičení 06 Jaro 2021 6 / 38
Vlastnosti funkce : uzavřenost
Je množina všech platných konfigurací uzavřená na funkci ?
Ano, protože:
Funkce by měla vracet opět platné konfigurace.
:: Config -> Config -> Config
Říkáme, že se jedná o operaci na množině konfigurací.
IB016: Cvičení 06 Jaro 2021 6 / 38
Vlastnosti operace : asociativita
Záleží na pořadí zpracovávání parametrů?
(-v -opt=o1) -q
vs.
-v (-opt=o1 -q)
IB016: Cvičení 06 Jaro 2021 7 / 38
Vlastnosti operace : asociativita
Záleží na pořadí zpracovávání parametrů?
(-v -opt=o1) -q
vs.
-v (-opt=o1 -q)
Ne, pořadí zpracování by nemělo ovlivnit výslednou konfiguraci.
Říkáme, že operace je asociativní.
IB016: Cvičení 06 Jaro 2021 7 / 38
Vlastnosti operace : komutativita
Záleží na pořadí samotných parametrů?
-v -opt=o1 -q
vs.
-q -opt=o1 -v
IB016: Cvičení 06 Jaro 2021 8 / 38
Vlastnosti operace : komutativita
Záleží na pořadí samotných parametrů?
-v -opt=o1 -q
vs.
-q -opt=o1 -v
Ano!
argumenty -q -v produkují jinou konfiguraci než -v -q
Operace proto není komutativní.
IB016: Cvičení 06 Jaro 2021 8 / 38
Vlastnosti operace : neutrální prvek
Má operace neutrální prvek?
N -v -opt=o1 -opt=o2 N
IB016: Cvičení 06 Jaro 2021 9 / 38
Vlastnosti operace : neutrální prvek
Má operace neutrální prvek?
N -v -opt=o1 -opt=o2 N
Ne (zatím), neutrálním prvkem by měla být výchozí konfigurace.
def :: Config
def = Config
{ verbose = False -- yikes! /o\
, options = []
}
IB016: Cvičení 06 Jaro 2021 9 / 38
Vlastnosti operace : neutrální prvek
Má operace neutrální prvek?
N -v -opt=o1 -opt=o2 N
Ne (zatím), neutrálním prvkem by měla být výchozí konfigurace.
def :: Config
def = Config
{ verbose = False -- yikes! /o\
, options = []
}
Jak zajistit, aby výchozí konfigurace nepřepsala případné -v?
IB016: Cvičení 06 Jaro 2021 9 / 38
Config: nová definice
Upravíme datový typ Config následovně:
data Config = Config
{ verbose :: Maybe Bool
, options :: [String]
} deriving (Eq, Show)
def :: Config
def = Config
{ verbose = Nothing
, options = []
}
Hodnota Nothing ∼ dosud nedefinovaný parametr verbose.
Je přepsána libovolnou hodnotou Just.
IB016: Cvičení 06 Jaro 2021 10 / 38
Motivace II: průchod adresářovou strukturou
Filesystem reprezentuje stromovou strukturu adresářového
systému.
data Filesystem = File Name Size
| Folder Name [Filesystem]
Chtěli bychom celý strom projít a do Map Name Size ukládat
soubory splňující zadaný regex.
IB016: Cvičení 06 Jaro 2021 11 / 38
Motivace II: průchod adresářovou strukturou
Filesystem reprezentuje stromovou strukturu adresářového
systému.
data Filesystem = File Name Size
| Folder Name [Filesystem]
Chtěli bychom celý strom projít a do Map Name Size ukládat
soubory splňující zadaný regex.
Pro každý přidaný prvek lze vytvořit jednoprvkovou Mapu.
singleton :: k -> a -> Map k a
union :: Ord k => Map k a -> Map k a -> Map k a
IB016: Cvičení 06 Jaro 2021 11 / 38
Vlastnosti funkce union
Spojení dvou struktur (Map k a) vytvoří novou strukturu
(Map k a).
union :: Ord k => Map k a -> Map k a -> Map k a
Nezáleží na „uzávorkování“ spojení Map ⇒ asociativita
Nezáleží na pořadí spojovaných Map ⇒ komutativita
Prázdná struktura je neutrální prvek vůči spojení
empty :: Map k a
⇒ V každém uzlu lze vrátit prázdnou nebo jednoprvkovou
strukturu. Pomocí operace union je následně všechny spojíme.
IB016: Cvičení 06 Jaro 2021 12 / 38
Algebraické okénko
IB016: Cvičení 06 Jaro 2021 13 / 38
Pologrupy a monoidy
Grupoid (M, ◦) je algebraická struktura. Sestává z nosné množiny
M a binární operace ◦: M × M → M.
Pologrupa je grupoid, jehož operace je asociativní:
Asociativita: ∀x, y, z ∈ M. (x ◦ y) ◦ z = x ◦ (y ◦ z)
Monoid je pologrupa s neutrálním prvkem:
Neutrální prvek: ∃e ∈ M ∀x ∈ M. x ◦ e = e ◦ x = x
IB016: Cvičení 06 Jaro 2021 14 / 38
Příklady monoidů
Jsou následující struktury monoidy?
(N, +), přirozená čísla se sčítáním
IB016: Cvičení 06 Jaro 2021 15 / 38
Příklady monoidů
Jsou následující struktury monoidy?
(N, +), přirozená čísla se sčítáním
⇒ Ano, (komutativní) monoid.
(N, −), přirozená čísla s odčítáním
IB016: Cvičení 06 Jaro 2021 15 / 38
Příklady monoidů
Jsou následující struktury monoidy?
(N, +), přirozená čísla se sčítáním
⇒ Ano, (komutativní) monoid.
(N, −), přirozená čísla s odčítáním
⇒ Ne (není ani grupoidem).
(N, min), přirozená čísla s minimem
IB016: Cvičení 06 Jaro 2021 15 / 38
Příklady monoidů
Jsou následující struktury monoidy?
(N, +), přirozená čísla se sčítáním
⇒ Ano, (komutativní) monoid.
(N, −), přirozená čísla s odčítáním
⇒ Ne (není ani grupoidem).
(N, min), přirozená čísla s minimem
⇒ Ne (neexistuje neutrální prvek), ale je pologrupa.
(N, max), přirozená čísla s maximem
IB016: Cvičení 06 Jaro 2021 15 / 38
Příklady monoidů
Jsou následující struktury monoidy?
(N, +), přirozená čísla se sčítáním
⇒ Ano, (komutativní) monoid.
(N, −), přirozená čísla s odčítáním
⇒ Ne (není ani grupoidem).
(N, min), přirozená čísla s minimem
⇒ Ne (neexistuje neutrální prvek), ale je pologrupa.
(N, max), přirozená čísla s maximem
⇒ Ano, (komutativní) monoid.
([...], ++), seznamy se zřetězením
IB016: Cvičení 06 Jaro 2021 15 / 38
Příklady monoidů
Jsou následující struktury monoidy?
(N, +), přirozená čísla se sčítáním
⇒ Ano, (komutativní) monoid.
(N, −), přirozená čísla s odčítáním
⇒ Ne (není ani grupoidem).
(N, min), přirozená čísla s minimem
⇒ Ne (neexistuje neutrální prvek), ale je pologrupa.
(N, max), přirozená čísla s maximem
⇒ Ano, (komutativní) monoid.
([...], ++), seznamy se zřetězením
⇒ Ano, (NEkomutativní) monoid.
({f | f :: a → a}, .), funkce typu a -> a se skládáním
IB016: Cvičení 06 Jaro 2021 15 / 38
Příklady monoidů
Jsou následující struktury monoidy?
(N, +), přirozená čísla se sčítáním
⇒ Ano, (komutativní) monoid.
(N, −), přirozená čísla s odčítáním
⇒ Ne (není ani grupoidem).
(N, min), přirozená čísla s minimem
⇒ Ne (neexistuje neutrální prvek), ale je pologrupa.
(N, max), přirozená čísla s maximem
⇒ Ano, (komutativní) monoid.
([...], ++), seznamy se zřetězením
⇒ Ano, (NEkomutativní) monoid.
({f | f :: a → a}, .), funkce typu a -> a se skládáním
⇒ Ano, (NEkomutativní) monoid.
(Config, ), datový typ konfigurace s operací
IB016: Cvičení 06 Jaro 2021 15 / 38
Příklady monoidů
Jsou následující struktury monoidy?
(N, +), přirozená čísla se sčítáním
⇒ Ano, (komutativní) monoid.
(N, −), přirozená čísla s odčítáním
⇒ Ne (není ani grupoidem).
(N, min), přirozená čísla s minimem
⇒ Ne (neexistuje neutrální prvek), ale je pologrupa.
(N, max), přirozená čísla s maximem
⇒ Ano, (komutativní) monoid.
([...], ++), seznamy se zřetězením
⇒ Ano, (NEkomutativní) monoid.
({f | f :: a → a}, .), funkce typu a -> a se skládáním
⇒ Ano, (NEkomutativní) monoid.
(Config, ), datový typ konfigurace s operací
⇒ Ano, (NEkomutativní) monoid!
IB016: Cvičení 06 Jaro 2021 15 / 38
A zpátky k Haskellu. . .
IB016: Cvičení 06 Jaro 2021 16 / 38
Typová třída Semigroup
class Semigroup a where
(<>) :: a -> a -> a
sconcat :: GHC.Base.NonEmpty a -> a
stimes :: Integral b => b -> a -> a
nejmenší nezbytná definice: (<>)
musí splňovat pravidlo asociativity:
x <> (y <> z) ≡ (x <> y) <> z
v Prelude jen (<>), více v Data.Semigroup
lze použít alternativní předdefinované implementace stimes
pro monoidy a/nebo idempotentní operaci; např.:
stimes = stimesMonoid
IB016: Cvičení 06 Jaro 2021 17 / 38
Typová třída Monoid
class Semigroup a => Monoid a where
mempty :: a
mappend :: a -> a -> a -- = (<>)
mconcat :: [a] -> a -- = foldr mappend mempty
musí splňovat pravidla:
levá identita: mempty <> x ≡ x
pravá identita: x <> mempty ≡ x
(asociativita: x <> (y <> z) ≡ (x <> y) <> z)
řetězení: mconcat ≡ foldr (<>) mempty
užitečné knihovní instance v Data.Monoid
Semigroup je nadtřídou teprve od base-4.11.0.0 (GHC 8.4)
IB016: Cvičení 06 Jaro 2021 18 / 38
Monoid [a]
Jak vypadá instance Monoidu pro seznamy?
IB016: Cvičení 06 Jaro 2021 19 / 38
Monoid [a]
Jak vypadá instance Monoidu pro seznamy?
instance Semigroup [a] where
(<>) = (++)
instance Monoid [a] where
mempty = []
IB016: Cvičení 06 Jaro 2021 19 / 38
Monoid Maybe a
Jak bude vypadat instance pro Maybe a?
instance Semigroup (Maybe a) where
Nothing <> b = b
(Just a) <> Nothing = Just a
(Just a) <> (Just b) = Just (a <> b)
instance Monoid (Maybe a) where
mempty = Nothing
IB016: Cvičení 06 Jaro 2021 20 / 38
Monoid Maybe a
Jak bude vypadat instance pro Maybe a?
instance Semigroup (Maybe a) where
Nothing <> b = b
(Just a) <> Nothing = Just a
(Just a) <> (Just b) = Just (a <> b)
instance Monoid (Maybe a) where
mempty = Nothing
Just „přebíjí“ Nothing
Neutrálním prvkem je Nothing
Co musí splňovat typ a?
IB016: Cvičení 06 Jaro 2021 20 / 38
Monoid Maybe a
Jak bude vypadat instance pro Maybe a?
instance Semigroup a => Semigroup (Maybe a) where
Nothing <> b = b
(Just a) <> Nothing = Just a
(Just a) <> (Just b) = Just (a <> b)
instance Semigroup a => Monoid (Maybe a) where
mempty = Nothing
Just „přebíjí“ Nothing
Neutrálním prvkem je Nothing
Co musí splňovat typ a?
Musí se jednat o instanci třídy Semigroup.
IB016: Cvičení 06 Jaro 2021 20 / 38
Pologrupa Last
Knihovní pologrupa Last (z modulu Data.Semigroup):
newtype Last a = Last { getLast :: a }
instance Semigroup (Last a) where
_ <> b = b
IB016: Cvičení 06 Jaro 2021 21 / 38
Pologrupa Last
Knihovní pologrupa Last (z modulu Data.Semigroup):
newtype Last a = Last { getLast :: a }
instance Semigroup (Last a) where
_ <> b = b
Lze zúplnit na monoid obalením v Maybe.
Analogicky existuje First a, kde (<>) = const.
IB016: Cvičení 06 Jaro 2021 21 / 38
Pologrupa Last
Knihovní pologrupa Last (z modulu Data.Semigroup):
newtype Last a = Last { getLast :: a }
instance Semigroup (Last a) where
_ <> b = b
Lze zúplnit na monoid obalením v Maybe.
Analogicky existuje First a, kde (<>) = const.
Pozor.
neplést s knihovním monoidem Data.Monoid.Last:
newtype Last a = Last { getLast :: Maybe a }
zanedlouho bude z knihovny odstraněn
doporučení: import Data.Monoid hiding (First, Last)
IB016: Cvičení 06 Jaro 2021 21 / 38
Další knihovní monoidy
Existuje-li více monoidů nad jedním typem, používá se newtype:
Num a => (Product a) – monoid vzhledem k násobení
Num a => (Sum a) – monoid vzhledem ke sčítání
Any – (Bool, ||); All – (Bool, &&)
(Ord a, Bounded a) => (Max a) – monoid vzhledem
k operaci maximum
(Ord a, Bounded a) => (Min a) – monoid vzhledem
k operaci minimum
(Monoid a, Monoid b) => (a, b) – kartézský součin
monoidů a a b
newtype Endo a = Endo { appEndo :: a -> a }
IB016: Cvičení 06 Jaro 2021 22 / 38
Řešení příkladu I
Původní:
data Config = Config
{ verbose :: Bool
, options :: [String]
} deriving (Eq, Show)
Nové:
type Config' = (Maybe (Last Bool), [String])
IB016: Cvičení 06 Jaro 2021 23 / 38
Řešení příkladu I
Původní:
data Config = Config
{ verbose :: Bool
, options :: [String]
} deriving (Eq, Show)
Nové:
type Config' = (Maybe (Last Bool), [String])
Zkuste napsat řešení pomocí Endo Config.
IB016: Cvičení 06 Jaro 2021 23 / 38
Foldable
IB016: Cvičení 06 Jaro 2021 24 / 38
Typová třída Foldable
class Foldable t where
foldr :: (a -> b -> b) -> b -> t a -> b
foldMap :: Monoid m => (a -> m) -> t a -> m
fold :: Monoid m => t m -> m
Nejmenší nezbytná definice: foldMap | foldr.
Kontejner, který lze lineárně projít a hodnoty „splácnout“.
Nemusí splňovat žádné rovnosti (na rozdíl od jiných
základních tříd).
Definováno v Prelude, další funkce v Data.Foldable.
IB016: Cvičení 06 Jaro 2021 25 / 38
foldMap vs. foldr
Obě funkce jsou ekvivalentní
foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
Je zřejmé jak vytvořit foldMap, pokud je foldr definováno.
Jak vytvořit foldr pomocí foldMap?
IB016: Cvičení 06 Jaro 2021 26 / 38
foldMap vs. foldr
Obě funkce jsou ekvivalentní
foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
Je zřejmé jak vytvořit foldMap, pokud je foldr definováno.
Jak vytvořit foldr pomocí foldMap?
Stačí přeuzávorkovat typ foldr.
(a -> b -> b) -> b -> t a -> b
→ (a -> (b -> b)) -> t a -> (b -> b)
Víme že funkce b -> b tvoří monoid – v knihovně typ Endo.
⇒ celý koncept „foldování“ lze definovat v řeči monoidů.
Foldable popisuje způsob procházení.
Monoid popisuje způsob skládání hodnot.
IB016: Cvičení 06 Jaro 2021 26 / 38
Definice pro BinTree
instance Foldable BinTree where
foldMap f (Node a l r) = f a <> foldMap f l <>
foldMap f r→
foldMap _ Leaf = mempty
Pozor! Obecný fold připojuje vždy jen jednu hodnotu.
Tj. ke každé struktuře se chová jako k seznamu.
Tj. foldr má v argumentu ve skutečnosti jen binární funkci f (na
rozdíl od treeFold z kurzu IB015).
IB016: Cvičení 06 Jaro 2021 27 / 38
Užitečné funkce
Automaticky získáme mnoho třídních funkcí:
foldl :: (b -> a -> b) -> b -> t a -> b
foldl' :: (b -> a -> b) -> b -> t a -> b
Operátor je aplikován striktně.
toList :: t a -> [a]
null :: t a -> Bool
length :: t a -> Int
elem :: Eq a => a -> t a -> Bool
maximum, minimum :: Ord a => t a -> a
sum, product :: Num a => t a -> a
Základní definice funkcí nemusí být nutně optimální. Například
elem pro Map je předefinován.
IB016: Cvičení 06 Jaro 2021 28 / 38
Traversable
IB016: Cvičení 06 Jaro 2021 29 / 38
Motivace III: vyhodnocení IO operací
Mějme Foldable a Functor kontejner (např. []), do kterého
chceme načíst hodnoty uživatele.
Začínáme se seznamem [String] obsahujícím otázky.
V každém uzlu seznamu můžeme vytvořit akci typu
IO String, která vypíše otázku a načte odpověď.
Využíváme toho, že [] je funktor.
Potřebovali bychom vytvořit jedinou akci typu IO [String].
To se nám nepodaří, pokud nevyužíváme dalších vlastností IO.
IB016: Cvičení 06 Jaro 2021 30 / 38
Motivace III: vyhodnocení IO operací
Mějme Foldable a Functor kontejner (např. []), do kterého
chceme načíst hodnoty uživatele.
Začínáme se seznamem [String] obsahujícím otázky.
V každém uzlu seznamu můžeme vytvořit akci typu
IO String, která vypíše otázku a načte odpověď.
Využíváme toho, že [] je funktor.
Potřebovali bychom vytvořit jedinou akci typu IO [String].
To se nám nepodaří, pokud nevyužíváme dalších vlastností IO.
fmap zachovává strukturu, hodnoty spolu neinteragují.
foldMap nezachovává strukturu, hodnoty spolu interagují.
Potřebujeme funkci, která umí obojí.
IB016: Cvičení 06 Jaro 2021 30 / 38
Typová třída Traversable
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f =>
(a -> f b) -> t a -> f (t b)
sequenceA :: Applicative f =>
t (f a) -> f (t a)
Minimální definice traverse | sequenceA.
Kontejner na data typu a, kterým lze projít a zachovat
strukturu dat.
Definováno v Prelude, další funkce v Data.Foldable.
IB016: Cvičení 06 Jaro 2021 31 / 38
Rovnosti pro Traversable
Musí platit rovnosti, které kontroluje programátor
Obě funkce by se měly chovat hezky k transformacím
Applicative (tj. funkce respektující <*>).
Pokud je funktor f identita (Identity), pak by se měla
sequenceA chovat jako identita a traverse by nemělo měnit
strukturu kontejneru t.
Přesné rovnosti v dokumentaci.
IB016: Cvičení 06 Jaro 2021 32 / 38
Definice pro seznam
instance Traversable [] where
traverse :: ... => (a -> f b) -> [a] -> f [b]
IB016: Cvičení 06 Jaro 2021 33 / 38
Definice pro seznam
instance Traversable [] where
traverse :: ... => (a -> f b) -> [a] -> f [b]
traverse f (x:xs) =
liftA2 (:) (f x) (traverse f xs)
traverse _ [] = pure []
IB016: Cvičení 06 Jaro 2021 33 / 38
Definice pro seznam
instance Traversable [] where
traverse :: ... => (a -> f b) -> [a] -> f [b]
traverse f (x:xs) =
liftA2 (:) (f x) (traverse f xs)
traverse _ [] = pure []
traverse' f (x:xs) = do
h <- f x
rest <- traverse f xs
return $ h : rest
traverse' _ [] = pure []
IB016: Cvičení 06 Jaro 2021 33 / 38
Definice pro binární stromy
instance Traversable BinTree where
traverse :: ... => (a -> f b) -> BT a -> f (BT b)
IB016: Cvičení 06 Jaro 2021 34 / 38
Definice pro binární stromy
instance Traversable BinTree where
traverse :: ... => (a -> f b) -> BT a -> f (BT b)
traverse f (Node a l r) =
liftA3
Node
(f a)
(traverse f l)
(traverse f r)
traverse _ Leaf = pure Leaf
IB016: Cvičení 06 Jaro 2021 34 / 38
Souvislost s Foldable
Není vidět spojení s Foldable.
IB016: Cvičení 06 Jaro 2021 35 / 38
Souvislost s Foldable
Není vidět spojení s Foldable.
Existuje instance Applicative, která se chová jako
akumulátor → můžeme definovat foldMap pomocí traverse.
IB016: Cvičení 06 Jaro 2021 35 / 38
Souvislost s Foldable
Není vidět spojení s Foldable.
Existuje instance Applicative, která se chová jako
akumulátor → můžeme definovat foldMap pomocí traverse.
Aplikativní funktor Const m.
Podobá se již zmiňované monádě písaře ([],), která má
akumulátor v první složce.
Const m ∼ (m, ())
IB016: Cvičení 06 Jaro 2021 35 / 38
Aplikativní funktor Const m
newtype Const a b = Const { getConst :: a }
instance Functor (Const a) where
fmap f (Const a) = Const a
instance Monoid a => Applicative (Const a) where
pure _ = Const mempty
Const x <*> Const y = Const (x `mappend` y)
foldMap :: (...) => (a -> m) -> t a -> m
foldMap f = getConst . traverse (Const . f)
IB016: Cvičení 06 Jaro 2021 36 / 38
Užitečné funkce
sequence :: Monad m => t (m a) -> m (t a)
Stejné jako sequenceA pro monády – historický relikt.
mapM :: Monad m => (a -> m b) -> t a -> m (t b)
Stejné jako traverse pro monády.
traverse_ :: (Applicative f, Foldable t) =>
(a -> f b) -> t a -> f ()
sequence_ :: (Applicative f, Foldable t) =>
t (f a) -> f ()
Jako odpovídající funkce, ale zapomínají výsledek.
Tj. jenom spouští dané akce (např. IO).
Nepotřebují si pamatovat strukturu → t nemusí být
Traversable.
IB016: Cvičení 06 Jaro 2021 37 / 38
Automatické odvozování instancí
U některých typů jsou instance „jasné“, „triviální“ a „mechanické“.
Příklad: instance monoidu pro součin monoidů:
data Config = Config { verbose :: Maybe (Last Bool)
, options :: [String]
} -- deriving Monoid :(
(Config v1 o1) <> (Config v2 o2) = Config (v1 <> v2) (o1 <> o2)
mempty = Config mempty mempty
IB016: Cvičení 06 Jaro 2021 38 / 38
Automatické odvozování instancí
U některých typů jsou instance „jasné“, „triviální“ a „mechanické“.
Příklad: instance monoidu pro součin monoidů:
data Config = Config { verbose :: Maybe (Last Bool)
, options :: [String]
} -- deriving Monoid :(
(Config v1 o1) <> (Config v2 o2) = Config (v1 <> v2) (o1 <> o2)
mempty = Config mempty mempty
GHC zavádí typovou třídu Generic.
Rozšíření DeriveGeneric umožňuje odvodit její instanci
Balík generic-deriving umožňuje z instance Generic
odvodit instance některých tříd, mj. monoidu či Traversable.
Existují i další rozšíření umožňující odvozování instancí.
IB016: Cvičení 06 Jaro 2021 38 / 38