Literatur
|
LYAH: Monoids
|
| |
Definition Halbgruppe
|
eine Halbgruppe ist eine Wertemenge mit einer 2-stelligen inneren Verknüpfung.
Diese Verknüpfung muss assoziativ sein.
|
Klasse
|
class Semigroup a where
(<>) :: a -> a -> a
infixr 6 <>
|
|
Bei der Definition von <> muss sicher gestellt werden,
dass das Assoziativgesetz gilt.
|
Assoziativgesetz
|
für Semigroup
|
|
x <> (y <> z) == (x <> y) <> z
|
|---|
|
Eine Halbgruppe ist eine sehr schwache Struktur.
Daher sind Halbgruppen in der SW-Technik allgegenwärtig.
|
|
Wegen des Assoziativgesetzes ist es möglich, die Auswertung von Operanden
beliebig zu gruppieren.
Dieses kann zu hohem Effizienzgewinn führen.
|
|
Wenn ein Datentyp eine Halbgruppe ist, dann können nichtleere
Listen von Werten
zu einem Wert aufsummiert werden.
|
|
Es gibt Halbgruppen, die keine Monoide sind.
|
Instanzen |
|
?
|
Halbgruppen aus der Schulzeit?
|
|
+, *
|
Listen
|
instance Semigroup [a] where
(<>) = (++)
|
| |
2. Beispiel |
|
Maybe a
|
instance Semigroup a => Semigroup (Maybe a) where
Nothing <> b = b
a <> Nothing = a
Just a <> Just b = Just (a <> b)
|
3. Beispiel |
|
Zahlen
|
instance Num a => Semigroup a where
(<>) = (+)
instance Num a => Semigroup a where
(<>) = (*)
|
|
Es sind zwei Instanzen möglich, aber nur eine ist erlaubt.
Welche?
|
| |
Definition Monoid
|
ein Monoid ist eine Halbgruppe mit neutralem Element.
|
Klasse
|
class Semigroup a => Monoid a where
mempty :: a
mappend :: a -> a -> a
mappend = (<>)
mconcat :: [a] -> a
mconcat = foldr (<>) mempty
|
zusätzliche Gesetze
|
für Monoide
|
|
x <> mempty == x
mempty <> x == x
|
|---|
|
mappend ist redundant, aber
aus Abwärtskompatibilitäts-Gründen gibt es diesen Aliasnamen noch
|
|
Das neutrale Element kann als Default-Wert genutzt werden.
|
|
Wenn ein Datentyp ein Monoid ist, dann können beliebig viele
Werte, auch 0 Werte,
zu einem Wert zusammen gefaltet (aufsummiert) werden.
|
Instanzen |
|
?
|
Halbgruppen aus der Schulzeit?
|
|
+ mit 0, * mit 1
|
Listen
|
instance Monoid [a] where
mempty = []
|
| |
2. Beispiel |
|
Maybe a
|
instance Semigroup a => Monoid (Maybe a) where
mempty = Nothing
|
| |
3. Beispiel |
|
Zahlen
|
instance Num a => Monoid a where
mempty = 0
instance Num a => Monoid a where
mempty = 1
|
| |
?
|
Welche instance-Definition (+, 0)
oder (*, 1)?
|
|
Beide sind von praktischem Nutzen, also beide aber wie?
|
3. Beispiel
Zahlen richtig
|
mit newtype-Wrapper
|
|
newtype Sum a = Sum {getSum :: a}
instance Num a => Semigroup (Sum a) where
Sum x <> Sum y = Sum (x + y)
instance Num a => Monoid (Sum a) where
mempty = Sum 0
newtype Prod a = Prod {getProd :: a}
instance Num a => Semigroup (Prod a) where
Prod x <> Prod y = Prod (x * y)
instance Num a => Monoid (Prod a) where
mempty = Prod 1
|
|
mconcat ist Σ oder Π
|
Anwendung
|
getSum . mconcat . map Sum $ [1..100]
getProd . mconcat . map Prod $ [1..100]
|
| |
?
|
Zahlen mit min und max?
Neutrales Element?
|
|
Bei einem beschränkten Intervall class Bounded
größtes oder kleinstes Element.
|
Zahlen
|
newtype Max a = Max a
instance (Ord a) => Semigroup (Max a) where
Max x <> Max y = Max (x `max` y)
instance (Ord a, Bounded a) => Monoid (Max a) where
mempty = Max minBound
newtype Min a = Min a
instance (Ord a) => Semigroup (Min a) where
Min x <> Min y = Min (x `min` y)
instance (Ord a, Bounded a) => Monoid (Min a) where
mempty = Min maxBound
|
| |
?
|
Boolesche Algebren und Monoide?
|
|
(&&, True) und (||, False)
|
|
newtype All = All { getAll :: Bool }
instance Semigroup All where
All x <> All y = All (x && y)
instance Monoid All where
mempty = All True
newtype Any = Any { getAny :: Bool }
instance Semigroup Any where
Any x <> Any y = Any (x || y)
instance Monoid Any where
mempty = Any False
|
|---|
|
mconcat als ∀ oder ∃
|
| |
Ordering |
3-wertiger Aufzählungstyp für Vergleiche
|
|
data Ordering = LT | EQ | GT
compare :: a -> a -> Ordering
instance Semigroup Ordering where
LT <> _ = LT
EQ <> y = y
GT <> _ = GT
instance Monoid Ordering where
mempty = EQ
|
|---|
|
mconcat als ∀ oder ∃
|
| |
2. Monoid für Maybe |
Der 1. gewinnt!
|
|
newtype First a = First { getFirst :: Maybe a }
instance Semigroup (First a) where
First Nothing <> y = y
x <> _ = x
instance Monoid (First a) where
mempty = First Nothing
|
|---|
Paare |
|
|
instance (Semigroup a, Semigroup b) => Semigroup (a,b) where
(a1,b1) <> (a2,b2)
= (a1 <> a2, b1 <> b2)
instance (Monoid a, Monoid b) => Monoid (a,b) where
mempty = (mempty, mempty)
|
|---|
|
Natürlich erweiterbar auf n-Tupel
|
| |
?
|
Kleinster Monoid?
|
|
instance Semigroup () where
_ <> _ = ()
mconcat _ = ()
instance Monoid () where
mempty = ()
|
| |
? |
Maps (Tabellen) als Monoide?
|
Map k v
|
import Data.Map (Map, empty, unionWith)
newtype Table k v = Table (Map k v)
instance (Ord k, Semigroup v) => Semigroup (Table k v) where
Table t1 <> Table t2 = Table $
unionWith (<>) t1 t2
instance (Ord k, Monoid v) => Monoid (Table k v) where
mempty = Table empty
|
?
|
praxisrelevant?
|
|
Beispiel Worthäufigkeiten
|
| |
Funktionen |
a -> a
|
Endomorphismen
|
mit Funktionskomposition und Identität
|
|
newtype Endo a = Endo { appEndo :: a -> a }
instance Semigroup (Endo a) where
Endo f <> Endo g = Endo (f . g)
instance Monoid (Endo a) where
mempty = Endo id
|
|---|
| |
Funktionen |
a -> b
|
|
mit Semigroup/Monoid als Resultat
|
|---|
|
instance Semigroup b => Semigroup (a -> b) where
f <> g = \ x -> f x <> g x
instance Monoid b => Monoid (a -> b) where
mempty _ = mempty
|
|---|
| |
? |
Es liegt nur eine Halbgruppe vor, aber das neutrale Element fehlt?
|
?
|
Lösung?
|
|
class Semigroup a where
(<>) :: a -> a -> a
instance Semigroup a => Monoid (Maybe a) where
Just x <> Just y = Just $ x <> y
Just x <> Nothing = Just x
Nothing <> Just y = Just y
Nothing <> Nothing = Nothing
|
|
Monoide sind allgegenwärtig!
|
|
Diese Beispiele und viele weiter Halbgruppen und Monoide sind
vordefiniert in Data.Semigroup und Data.Monoid
|
?
|
Praktische Bedeutung des Assoziativgesetzes?
|
|
Das Zusammenfalten mconcat kann beliebig
umgruppiert werden, also ist auch eine Parallelisierung
auf einfache Weise und ohne Änderung der Semantik möglich.
|
Beispiel |
für effiziente Algorithmen mit Monoiden
|
Funktionale Programmierung: Halbgruppen und Monoide
