Monoidy, zpracovávání argumentů
příkazové řádky
IB016 Seminář z funkcionálního programování
Vladimír Štill, Martin Ukrop
Fakulta informatiky, Masarykova univerzita
Jaro 2018
IB016: Cvičení 06 Jaro 2018 1 / 20
Motivace: 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á ladící výstupy
-q (quiet) vypíná ladící výstupy
program se vždy chová podle posledního přepínače -v/-q
-opt umožňuje přidat programu libovolný textový argument
výchozí nastavení je bez ladících výstupů a bez dalších
argumentů
IB016: Cvičení 06 Jaro 2018 2 / 20
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 2018 3 / 20
Představa zpracování
každý přepínač vlastně zodpovídá nějakému nastavení
nedaly by se jednoduše „spojit“ nějakou vhodnou funkcí?
-v -opt=o1 -q -opt=o2
IB016: Cvičení 06 Jaro 2018 4 / 20
Představa zpracování
každý přepínač vlastně zodpovídá nějakému nastavení
nedaly by se jednoduše „spojit“ 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 = []}
IB016: Cvičení 06 Jaro 2018 4 / 20
Představa zpracování
každý přepínač vlastně zodpovídá nějakému nastavení
nedaly by se jednoduše „spojit“ 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 má funkce ?
IB016: Cvičení 06 Jaro 2018 4 / 20
Vlastnosti operace : uzavřenost
Je množina všech platných konfigurací uzavřená na operaci ?
IB016: Cvičení 06 Jaro 2018 5 / 20
Vlastnosti operace : uzavřenost
Je množina všech platných konfigurací uzavřená na operaci ?
Ano, protože:
Operace má správný typ.
:: Config -> Config -> Config
Můžeme ji zadefinova tak, aby jejím výsledkem nikdy nebyla
neplatná konfigurace.
IB016: Cvičení 06 Jaro 2018 5 / 20
Vlastnosti operace : asociativita
Je operace asociativní?
-v -opt=o1 -q -opt=o2
IB016: Cvičení 06 Jaro 2018 6 / 20
Vlastnosti operace : asociativita
Je operace asociativní?
-v -opt=o1 -q -opt=o2
Ano, pořadí zpracování by nemělo ovlivnit výslednou konfiguraci.
IB016: Cvičení 06 Jaro 2018 6 / 20
Vlastnosti operace : komutativita
Je operace komutativní?
-v -opt=o1 -q -opt=o2
IB016: Cvičení 06 Jaro 2018 7 / 20
Vlastnosti operace : komutativita
Je operace komutativní?
-v -opt=o1 -q -opt=o2
Ne, na pořadí záleží.
argumenty -q -v produkují jinou konfiguraci než -v -q
IB016: Cvičení 06 Jaro 2018 7 / 20
Vlastnosti operace : neutrální prvek
Má operace neutrální prvek?
N -v -opt=o1 -opt=o2 N
IB016: Cvičení 06 Jaro 2018 8 / 20
Vlastnosti operace : neutrální prvek
Má operace neutrální prvek?
N -v -opt=o1 -opt=o2 N
Ano, neutrálním prvkem by měla být výchozí konfigurace.
def :: Config
def = Config
      { verbose = NotSet
      , options = []
      }
IB016: Cvičení 06 Jaro 2018 8 / 20
Config: nová definice
Upravíme tedy datový typ Config následovně:
data Flag a = Set a
                  | NotSet
                  deriving (Eq, Show)
data Config = Config
      { verbose :: Flag Bool
      , options :: [String]
      } deriving (Eq, Show)
IB016: Cvičení 06 Jaro 2018 9 / 20
Monoidy: matematická definice
Monoid1 je algebraická struktura. Je to grupoid (M; ·), tedy
množina M s binární operací · : M × M → M, a těmito axiomy:
Asociativita: ∀x, y, z ∈ M. (x · y) · z = x · (y · z)
Neutrální prvek: ∃e ∈ M ∀x ∈ M. x · e = e · x = x
Někdy se uvádí i následující axiom plynoucí z definice binární
operace grupoidu:
∀x, y ∈ M. x · y ∈ M
1
Definice převzata z https://cs.wikipedia.org/wiki/Monoid
IB016: Cvičení 06 Jaro 2018 10 / 20
Příklady monoidů
Jsou následující struktury monoidy?
(N, +), přirozená čísla se sčítáním
IB016: Cvičení 06 Jaro 2018 11 / 20
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 2018 11 / 20
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í asociativní, neexistuje neutrální prvek).
(N, ·), přirozená čísla s násobením
IB016: Cvičení 06 Jaro 2018 11 / 20
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í asociativní, neexistuje neutrální prvek).
(N, ·), přirozená čísla s násobením
⇒ Ano, (komutativní) monoid.
(N, xy ), přirozená čísla s umocňováním
IB016: Cvičení 06 Jaro 2018 11 / 20
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í asociativní, neexistuje neutrální prvek).
(N, ·), přirozená čísla s násobením
⇒ Ano, (komutativní) monoid.
(N, xy ), přirozená čísla s umocňováním
⇒ Ne (není asociativní, neexistuje neutrální prvek).
([...], ++), seznamy se zřetězením
IB016: Cvičení 06 Jaro 2018 11 / 20
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í asociativní, neexistuje neutrální prvek).
(N, ·), přirozená čísla s násobením
⇒ Ano, (komutativní) monoid.
(N, xy ), přirozená čísla s umocňováním
⇒ Ne (není asociativní, neexistuje neutrální prvek).
([...], ++), 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 2018 11 / 20
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í asociativní, neexistuje neutrální prvek).
(N, ·), přirozená čísla s násobením
⇒ Ano, (komutativní) monoid.
(N, xy ), přirozená čísla s umocňováním
⇒ Ne (není asociativní, neexistuje neutrální prvek).
([...], ++), 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 2018 11 / 20
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í asociativní, neexistuje neutrální prvek).
(N, ·), přirozená čísla s násobením
⇒ Ano, (komutativní) monoid.
(N, xy ), přirozená čísla s umocňováním
⇒ Ne (není asociativní, neexistuje neutrální prvek).
([...], ++), 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 2018 11 / 20
Typová třída Monoid
class Monoid a where
      mempty :: a
      mappend :: a -> a -> a
      mconcat :: [a] -> a
      mconcat = foldr mappend mempty
definováno v Data.Monoid
<> je infixové synonymum pro mappend (v Data.Monoid)
mnoho užitečných knihovních instancí
opět několik pravidel, která musí platit
levá identita: mempty <> x ≡ x
pravá identita: x <> mempty ≡ x
asociativita: x <> (y <> z) ≡ (x <> y) <> z
IB016: Cvičení 06 Jaro 2018 12 / 20
Instance pro konfigurace
Udělejme tedy instanci typu Config pro třídu Monoid:
instance Monoid Config where
IB016: Cvičení 06 Jaro 2018 13 / 20
Instance pro konfigurace
Udělejme tedy instanci typu Config pro třídu Monoid:
instance Monoid Config where
      mempty = defaultConfig
      c1 `mappend` c2 =
            Config (verbose c1 `mappend` verbose c2)
                     (options c1 `mappend` options c2)
Teď ale potřebujeme ještě:
instanci pro datový typ Flag
instanci pro seznamy
IB016: Cvičení 06 Jaro 2018 13 / 20
Instance pro Flag
Jak chceme, aby se chovala instance pro Flag a?
instance Monoid (Flag a) where
IB016: Cvičení 06 Jaro 2018 14 / 20
Instance pro Flag
Jak chceme, aby se chovala instance pro Flag a?
instance Monoid (Flag a) where
      mempty = NotSet
      _ `mappend` (Set x) = Set x
      x `mappend` NotSet = x
IB016: Cvičení 06 Jaro 2018 14 / 20
Instance pro seznamy
Jak chceme, aby se chovala instance pro seznamy?
instance Monoid [a] where
IB016: Cvičení 06 Jaro 2018 15 / 20
Instance pro seznamy
Jak chceme, aby se chovala instance pro seznamy?
instance Monoid [a] where
      mempty = []
      x `mappend` y = x ++ y
(je součástí knihovny)
IB016: Cvičení 06 Jaro 2018 15 / 20
Všechno spolu
A teď máme elegantní, rozšiřitelný systém parsující argumenty
příkazové řádky :-}.
... který navyše využívá pěknou algebraickou teorii.
IB016: Cvičení 06 Jaro 2018 16 / 20
Monoid: knihovní instance
V knihovně je vícero instancí pro Monoid:
[a] – instance stejná, jako jsme vytvořili my
Last a – odpovídá našemu Flag a (je to vlastně instance
pro newtype nad Maybe a)
First a – jako Flag a, jenom prioritu má první výskyt
definované hodnoty (ne poslední)
Any – newtype nad Bool s operací ||
All – newtype nad Bool s operací &&
Num a => (Product a) – numerická instance kolem operace
násobení
Num a => (Sum a) – numerická instance kolem sčítání
. . .
IB016: Cvičení 06 Jaro 2018 17 / 20
Semigroups, automatické instance
Semigroups
vyžaduje pouze mappend (nemusí existovat neutrální prvek)
existuje návrh udělat Semigroup prerekvizitou Monoid
IB016: Cvičení 06 Jaro 2018 18 / 20
Semigroups, automatické instance
Semigroups
vyžaduje pouze mappend (nemusí existovat neutrální prvek)
existuje návrh udělat Semigroup prerekvizitou Monoid
Balík derive
automatické instance
(Monoid, Default, Arbitrary, ...)
používá Template Haskell (celkem velká magie)
často si stejně potřebujete napsat vlastní...
IB016: Cvičení 06 Jaro 2018 18 / 20
Typeclassopedia
https://wiki.haskell.org/Typeclassopedia
The goal of this document is to serve as a starting point for the
student of Haskell wishing to gain a firm grasp of its standard type
classes. The essentials of each type class are introduced, with
examples, commentary, and extensive references for further reading.
třídy, které už známe (Functor, Applicative, . . . )
třídy, které na nich staví (Monoid → Foldable)
třídy jěště vyšší abstrakce (MonadTrans, Arrow)
IB016: Cvičení 06 Jaro 2018 19 / 20
Úkol: rozšíření pro další volby
Rozšiřte program o možnost následujících argumentů:
-printer=lj4a nastaví tiskárnu, identifikovanou řetězcem.
Vždy se použije první zadaná tiskárna.
Předělejte příznak verbose tak, aby úrověn výstupů byla
charakterizována přirozeným číslem (vychozí hodnota 1).
Použije se vždy maximální z nastavených hodnot, pokuď není
použit přepínač -q. Tedy argumenty -v=1 -v=5 -v=2 nastaví
level na 5 a argumenty -v=1 -q -v=6 na 0.
Zkuste si v Typeclassopedii přečíst o typové třídě Foldable, která
zobecňuje struktury, přes které se dá „foldovat“.
IB016: Cvičení 06 Jaro 2018 20 / 20