Monoid

29. 5. 2017

Jasně si vzpomínám, jak jsme kdysi dávno na vysoké škole probírali pologrupy a monoidy a já si pomyslel: "K čemu je to dobré?" Šlo o upřímnou otázku, nikoli o znevažování všeho, co nemá okamžité uplatnění. Zajímalo mě to, protože když jsem věděl, kde se daná věc používá, dodalo mi to trochu motivace a získal jsem rámec do kterého zasadit, co jsem se naučil. Tu otázku jsem nikdy nevyslovil nahlas a proto se mi nedostalo žádné odpovědi a tak jsem žil v ignoranci než mě ze školy bez pocty vyhodili a pak (aby si byli jisti) mě vyhodili ještě jednou.

Nicméně teď už to vím. Monoidy a pologrupy jsou velice užitečné algebraické struktury a abstrakce, které se uplatní všude tam, kde se dělají agregace, které byť jenom vzdáleně vypadají jako sčítání.

Monoid je množina T s jednou asociativní binární operací a neutrálním prvkem. V kódu může vypadat třeba takto:

trait Monoid[T] {
  def zero: T
  def plus(l: T, r: T): T
}

Velice podobně je definován i v knihovně Algebird, kterou budu v tomto textu používat jako příklad.

Aby byl monoid monoidem, musí splňovat dva axiomy.

Binární operace musí být asociativní. Nezáleží tedy kam dám závorky, výsledek bude vždycky stejný.

a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c

Nulový prvek (identita) nemá žádný vliv ať už ho přičtu zleva nebo zprava.

x ⊕ 0 = x = 0 ⊕ x

To je celá definice monoidu, nekomplikovaná a strohá. Vypadá skoro až příliš jednoduše na to, aby byla k něčemu užitečná. Když se však člověk na chvíli zamyslí, začne mu docházet, že monoidy najdou uplatnění na mnoha místech. A když už ne monoidy jako takové, tak aspoň jejich chudší příbuzní pologrupy (anglicky semigroup), které vypadají úplně stejně, jen jim chybí nulový prvek¹ .

Například operace sčítání s nulovým prvkem 0 tvoří monoid. To samé pro násobení a 1, spojování řetězců a prázdný string, spojování seznamů a prázdný seznam, nebo sjednocení množin a prázdnou množinu. Protože jde o monoidy, všechno se chová uniformě, regulárně a podle diktátu pravidel o asociativitě a identitě.

Několik jednoduchých monoidů:

typ	plus	zero
Int	+	0
Int	*	1
String	+	""
List	++	List()
Set	union	Set()
Boolean	and	true
Boolean	or	false
Int	max	-Infinity
Int	min	+Infinity

To ale zdaleka není všechno. Monoidy je totiž možné kombinovat a komponovat a tvořit větší z několika menších. Jestliže nám například dva páry hodnot (ve Scale jde o Tuple2) a chci je sečíst, udělám to takhle:

(a₁, b₁) ⊕ (a₂, b₂) = (x, y)

Použiji příslušný monoid pro první komponenty a zvlášť monoid pro druhé komponenty.

x = a₁ ⊕ a₂
y = b₁ ⊕ b₂

Takže když páry mají typ (Int, String), budu sčítat první komponenty a spojovat druhé komponenty. O tom, jaký monoid se použije rozhoduje typ argumentů, které Algebird používá k výběru příslušné typeclass, která je předána jako implicitní argument.

val p1 = (1, "asd")
val p2 = (2, "xyz")

val (a, b) = Monoid.plus(p1, p2)

Kompilátor podlední řádek rekurzivně expanduje na něco ve stylu

Monoid.plus(p1, p2)(Monoid.monoid2(IntMonoid, StringMonoid))

Monoid existuje pro každý Tuple2, jehož obě komponenty mají monoidy. To samé pro Tuple3, Tuple4, atd. Stejně tak platí, že pokud mám jednoduché monoidy, můžu z nich konstruovat větší a složitější jako například Option, Either, Seq, Map nebo Function1.

Typeclass pro Option je definován takto:

class OptionMonoid[T](implicit semi: Semigroup[T]) extends Monoid[Option[T]] {
  def zero = None
  def plus(left: Option[T], right: Option[T]): Option[T] = {
    if (left.isEmpty) {
      right
    } else if (right.isEmpty) {
      left
    } else {
      Some(semi.plus(left.get, right.get))
    }
  }
}

Nulový prvek je None, plus sečte vnitřky Option pologrupou pro typ T, pokud jsou oba Some, jinak vrátí ten, který není None.

Podobně funguje Map: plus spojí dvě mapy a když obě obsahují určitý klíč, sečte jejich obsah příslušným monoidem.

Algebird se sekvencemi typu Seq zachází jako s tuple typy - nespojuje kolekce, ale sčítá odpovídající hodnoty. Sekvence typu List spojuje.

Jako příklad budu uvažovat, že mám kolekci čísel

val numbers: Seq[Int] = ???

Když ji chci sečíst, stačí zavolat:

val sum = Monoid.sum(numbers)

Výchozí monoid pro typ Int je sčítání + 0.

Pokud chci průměrnou hodnotu, musím obalit číslo typem AveragedValue. Algebird pro něj najde odpovídající typeclass, která implementuje plus jako průměrování Intů.

val average = Monoid.sum(
  numbers map { num => AveragedValue(num) }
)

Pokud chci zjistit více agregací, stačí mapovat výchozí data na n-tici požadovaných typů a Algebird udělá zbytek. Součet, minimum, maximum, průměr a množinu všech unikátních hodnot můžu v jedné iteraci zjistit například takto:

val (sum, min, max, avg, uniqueNumbers) =
  Monoid.sum(numbers map { x =>
    (x, Min(x), Max(x), AveragedValue(x), Set(x))
  })

Metoda sum(vs: TraversableOnce[T]): T definovaná na traitu a objektu Monoid sečte všechny prvky předané kolekce příslušným monoidem. V podstatě dělá jen values.foldLeft(zero)(plus).

Pochopitelně tohle není všechno. Monoidy se dají kombinovat mnohem vynalézavěji ve snaze spočítat komplikovanější agregace. Představte si, že mám access log webserveru a chci detekovat roboty. Začnu třeba tím, že spočítám kolik přístupů pochází z jednotlivých IP adres.

val records: Iterator[AccessLogRecord] = readAllLogRecords()

val map: Map[IpAddress, Int] =
  Monoid.sum(records map { r =>
    Map(r.clientIpAddress -> 1)
  })

Výsledkem je mapa, kde klíče jsou IP adresy a hodnotami je počet hitů.

Dobré. Ale co kdybych teď chtěl tyto počty pro každý měsíc zvlášť? Toho se dá docílit jednoduše:

val map: Map[Month, Map[IpAddress, Int]] =
  Monoid.sum(records map { r =>
    Map(yearAndMonth(r.date) -> Map(r.clientIpAddress -> 1))
  })

A co třeba statistiky o tom, kdy se daná IP adresa poprvé a naposledy objevila a kolik z ní bylo provedeno dotazů dohromady a v každou denní hodinu?

val res: Map[IpAddress, (Min[Date], Max[Date], Int, Map[Hour, Int])] =
  Monoid.sum(records map { r =>
    Map(r.clientIpAddress -> (Min(r.date), Max(r.date), 1, Map(hourOf(r.date) -> 1)))
  })

Monoidy neexistují jen pro jednoduché součty, minima, maxima a průměry, ale i pro komplikovanější objekty jako je například Bloom filter, HyperLogLog, Count-min sketch nebo top-k. Díky tomu můžu dělat komplikované agregace, které zahrnují pravděpodobnostní algoritmy, ale chovají se stále stejně jako jakýkoli jiný monoid a jsou stále komponovatelné.

Algebird nabízí tyto možnosti: DecayedValue, DecayedVector, Interval, Moments, BloomFilter, HLL, CMS, SpaceSaver, SketchMap, MinHash, HashingTrick, TopK.

Když budu chtít zjistit 100 dotazů, které vedly k největším odpovědím, můžu to udělat takhle:

// top-100 řazeno sestupně podle bytesSent
implicit val topk = new TopKMonoid(100)(Ordering.by[AccessLogRecord, Int](_.bytesSent).reverse)

val res: List[AccessLogRecord] =
  Monoid.sum(records map { r => topk.build(r) })

Nebo třeba odhadnout počet unikátních IP adres a unikátních uživatelů v každém měsíci pomocí HyperLogLogu, který potřebuje konstantní množství paměti nehledě na to, jaká je kardinalita množiny unikátních hodnot:

implicit val hll = new HyperLogLogMonoid(bits = 12)

val res: Map[Month, (Double, Double)] =
  Monoid.sum(records map { r =>
    Map(yearAndMonth(r.date) -> hll.toHLL(r.clientIpAddress), hll.toHLL(r.userId))
  }).mapValues { case (ips, users) => (ips.estimatedSize, users.estimatedSize) }

Jak je vidět, použití je vždycky stejné: nejdřív transformuji data do cílového tvaru a pak rozjedu sumaci a mechanismus monoidů podpořený implicitními parametry Scaly se postará o zbytek. Nezáleží přitom jak triviální nebo komplikovaná jsou data, když pro ně existuje monoid, dají se sečíst.

To, že dvojice nulového prvku a asociativní operace se vyskytuje často svědčí časté použití metod/funkcí jako je foldLeft:

xs.foldLeft(0)((a, b) => a + b)

V tomto případě nulový prvek a asociativní operaci monoidu. Jde tedy o:

xs.foldLeft(M.zero)(M.plus)

neboli:

Monoid.sum[M](xs)

Z rozhraní monoidu dále vyplývá, že je možné provádět výpočet dávkově, na (potenciálně nekonečném) proudu dat, paralelně a je možné dělat snapshoty. To všechno díky asociativitě binární operace.

Streamování je jasné - když dostanu nová data, přičtu je k současnému výsledku a všechno jede bez problémů. Musím jednom zaručit že nedošlo ke změně pořadí v jakém položky přicházejí, protože operace není nutně komutativní. Možnost snapshotů je pak duál této vlastnosti.

Paralelizace vyplývá z faktu, že můžu výraz libovolně uzávorkovat.

Například

a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+w+x+y+z

můžu uzávorkovat takhle

(a+b+c+d+e+f)+(g+h+i+j+k+l+m)+(n+o+p+q+r+s+t)+(u+v+w+x+y+z)

každou závorku spočítat v jednom vlákně a pak sečíst mezivýsledky

AF + GM + NT + UZ

Opět je potřeba zaručit jenom, že nedojde ke změně pořadí položek a mezivýsledků (nebo zaručit komutativitu² ) a paralelizace je zcela bezproblémová a koncepčně zadarmo.

Tady skončím, protože tohle stačí jako odpověď na tu nikdy nevyslovenou otázku z let dávno minulých. Je překvapivé, že tak málo může poskytnout tolik garancí a flexibility, a že tolik reálných a užitečných věcí, strukturou odpovídá něčemu, co na první pohled vypadá jako akademická podivnost popsaná několika řeckými písmeny a zcela nepřístupná reálnému světu pragmatiků, kteří se dřou pod praporem worse is better.

V podobném duchu nečekané abstrakce, která se objevuje na nečekaných místech se nese přednáška Regexes, Kleene algebras, and real ultimate power!. Člověk nemusí pochopit všechny detaily, aby cítil nepopiratelnost představované abstrakce.

Jako člověk, kterému se neštítí počítání taktů procesoru se musím zmínit ještě o jedné věci - výkonu. Algebird byl navržen s koncepční čistotou, která ne nutně musí vést k rychlému výslednému programu. Sumace pomocí monoidů uvažuje, že všechny objekty jsou neměnné a při každém součtu se vytvoří další, což vede k poměrně divokým alokacím. To je ještě horší problém, když sčítám mapy tuplů vnořené do jiných map tuplů. Při každé iteraci je velká část této struktury znovu vytvořena. Ne celá, protože persistentní datové struktury používají strukturální sdílení pod kapotou. Přesto jde o řádově víc alokací, než by dělal kód, který manipuluje měnitelnými strukturami. Výsledek může být až několikrát pomalejší. Ale na druhou stranu je sumace prostřednictvím monoidů nesrovnatelně jednodušší (hlavně, když se do hry dostanou hluboce vnořené struktury) a bezpečně paralelizovatelná. Situaci také pomáhá fakt, že ve scale jsou immutable mapy a množiny ručně specializovány pro 1 až 4 položky. Alokace malých map/množin je tedy relativně levná, protože není třeba vytvořit celé HAMT. Technicky by bylo možné provést stream fusion (například pomocí maker), které by odstranilo nutnost alokace dočasných a efemérních objektů.

Neříkám, že kvůli tomu jsou monoidy špatné nebo pomalé. Jde o jednu věc, o které je třeba se zmínit.

Fakt, že pologrupy postrádají nulový prvek lehce komplikuje některé operace. Když chci sečíst libovolnou sekvenci dat, pologrupa si s tím neumí poradit, protože libovolná sekvence může být prázdn. V takovém případě by se vyplatilo vrátit nulový prvek. V Algebirdu je proto na třídě Semigroup deklarována metoda sumOption(xs: TraversableOnce[T]): Option[T] a sum zcela chybí.
Mnoho operací je komutativních, protože jsou zároveň idempotentní: min, max, sjednocení množin, logické operace, konstrukce Bloom filteru a HyperLogLogu. Jiné nejsou idempotentní, ale přesto komutují: sčítání, konstrukce Count-min sketch.

Dále k tématu: