funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Monoid

29. 5. 2017 — k47

Jasně si vzpo­mí­nám, jak jsme kdysi dávno na vysoké škole pro­bí­rali po­lo­grupymo­no­idy a já si po­mys­lel: „K čemu je to dobré?“ Šlo o upřím­nou otázku, nikoli o zne­va­žo­vání všeho, co nemá oka­mžité uplat­nění. Za­jí­malo mě to, pro­tože když jsem věděl, kde se daná věc po­u­žívá, dodalo mi to trochu mo­ti­vace a získal jsem rámec do kte­rého za­sa­dit, co jsem se naučil. Tu otázku jsem nikdy ne­vy­slo­vil nahlas a proto se mi ne­do­stalo žádné od­po­vědi a tak jsem žil v ig­no­ranci než mě ze školy bez pocty vy­ho­dili a pak (aby si byli jisti) mě vy­ho­dili ještě jednou.

Nicméně teď už to vím. Mo­no­idy a po­lo­grupy jsou velice uži­tečné al­ge­braické struk­tury a abs­trakce, které se uplatní všude tam, kde se dělají agre­gace, které byť jenom vzdá­leně vy­pa­dají jako sčí­tání.

Monoid je mno­žina T s jednou aso­ci­a­tivní bi­nární ope­rací a ne­ut­rál­ním prvkem. V kódu může vy­pa­dat třeba takto:

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

Velice po­dobně je de­fi­no­ván i v knihovně Al­ge­bird, kterou budu v tomto textu po­u­ží­vat jako pří­klad.

Aby byl monoid mo­no­i­dem, musí spl­ňo­vat dva axiomy.

  1. Bi­nární ope­race musí být aso­ci­a­tivní. Ne­zá­leží tedy kam dám zá­vorky, vý­sle­dek bude vždycky stejný.
a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
  1. Nulový prvek (iden­tita) nemá žádný vliv ať už ho přičtu zleva nebo zprava.
x ⊕ 0 = x = 0 ⊕ x

To je celá de­fi­nice mo­no­idu, ne­kom­pli­ko­vaná a strohá. Vypadá skoro až příliš jed­no­duše na to, aby byla k něčemu uži­tečná. Když se však člověk na chvíli za­myslí, začne mu do­chá­zet, že mo­no­idy najdou uplat­nění na mnoha mís­tech. A když už ne mo­no­idy jako takové, tak aspoň jejich chudší pří­buzní po­lo­grupy (an­g­licky se­mi­group), které vy­pa­dají úplně stejně, jen jim chybí nulový prvek1.

Na­pří­klad ope­race sčí­tání s nu­lo­vým prvkem 0 tvoří monoid. To samé pro ná­so­bení a 1, spo­jo­vání ře­tězců a prázdný string, spo­jo­vání se­znamů a prázdný seznam, nebo sjed­no­cení množin a prázd­nou mno­žinu. Pro­tože jde o mo­no­idy, všechno se chová uni­formě, re­gu­lárně a podle dik­tátu pra­vi­del o aso­ci­a­ti­vitě a iden­titě.

Ně­ko­lik jed­no­du­chých mo­no­idů:

typpluszero
Int+0
Int*1
String+„“
List++List()
SetunionSet()
Bo­o­leanandtrue
Bo­o­leanorfalse
Intmax-In­fi­nity
Intmin+In­fi­nity

To ale zda­leka není všechno. Mo­no­idy je totiž možné kom­bi­no­vat a kom­po­no­vat a tvořit větší z ně­ko­lika men­ších. Jestliže nám na­pří­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)

Po­u­žiji pří­slušný monoid pro první kom­po­nenty a zvlášť monoid pro druhé kom­po­nenty.

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

Takže když páry mají typ (Int, String), budu sčítat první kom­po­nenty a spo­jo­vat druhé kom­po­nenty. O tom, jaký monoid se po­u­žije roz­ho­duje typ ar­gu­mentů, které Al­ge­bird po­u­žívá k výběru pří­slušné ty­pec­lass, která je pře­dána jako im­pli­citní ar­gu­ment.

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

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

Kom­pi­lá­tor pod­lední řádek re­kur­zivně ex­pan­duje na něco ve stylu

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

Monoid exis­tuje pro každý Tuple2, jehož obě kom­po­nenty mají mo­no­idy. To samé pro Tuple3, Tuple4, atd. Stejně tak platí, že pokud mám jed­no­du­ché mo­no­idy, můžu z nich kon­stru­o­vat větší a slo­ži­tější jako na­pří­klad Option, Either, Seq, Map nebo Function1.

Ty­pec­lass pro Option je de­fi­no­vá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 po­lo­grupou pro typ T, pokud jsou oba Some, jinak vrátí ten, který není None.

Po­dobně fun­guje Map: plus spojí dvě mapy a když obě ob­sa­hují určitý klíč, sečte jejich obsah pří­sluš­ným mo­no­i­dem.

Al­ge­bird se sek­ven­cemi typu Seq za­chází jako s tuple typy – ne­spo­juje ko­lekce, ale sčítá od­po­ví­da­jící hod­noty. Sek­vence typu List spo­juje.

Jako pří­klad budu uva­žo­vat, že mám ko­lekci čísel

val numbers: Seq[Int] = ???

Když ji chci sečíst, stačí za­vo­lat:

val sum = Monoid.sum(numbers)

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

Pokud chci prů­měr­nou hod­notu, musím obalit číslo typem AveragedValue. Al­ge­bird pro něj najde od­po­ví­da­jící ty­pec­lass, která im­ple­men­tuje plus jako prů­mě­ro­vání Intů.

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

Pokud chci zjis­tit více agre­gací, stačí ma­po­vat vý­chozí data na n-tici po­ža­do­va­ných typů a Al­ge­bird udělá zbytek. Součet, mi­ni­mum, ma­xi­mum, průměr a mno­žinu všech uni­kát­ních hodnot můžu v jedné ite­raci zjis­tit na­pří­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 de­fi­no­vaná na traitu a ob­jektu Monoid sečte všechny prvky pře­dané ko­lekce pří­sluš­ným mo­no­i­dem. V pod­statě dělá jen values.foldLeft(zero)(plus).

Po­cho­pi­telně tohle není všechno. Mo­no­idy se dají kom­bi­no­vat mnohem vy­na­lé­za­věji ve snaze spo­čí­tat kom­pli­ko­va­nější agre­gace. Před­stavte si, že mám access log web­ser­veru a chci de­te­ko­vat roboty. Začnu třeba tím, že spo­čí­tám kolik pří­stupů po­chází z jed­not­li­vých IP adres.

val records: Iterator[AccessLogRecord] = readAllLogRecords()

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

Vý­sled­kem je mapa, kde klíče jsou IP adresy a hod­no­tami je počet hitů.

Dobré. Ale co kdy­bych teď chtěl tyto počty pro každý měsíc zvlášť? Toho se dá do­cí­lit jed­no­duš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 sta­tis­tiky o tom, kdy se daná IP adresa poprvé a na­po­sledy ob­je­vila a kolik z ní bylo pro­ve­deno dotazů do­hro­mady 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)))
  })

Mo­no­idy ne­e­xis­tují jen pro jed­no­du­ché součty, minima, maxima a prů­měry, ale i pro kom­pli­ko­va­nější ob­jekty jako je na­pří­klad Bloom filter, Hy­per­Lo­gLog, Count-min sketch nebo top-k. Díky tomu můžu dělat kom­pli­ko­vané agre­gace, které za­hr­nují prav­dě­po­dob­nostní al­go­ritmy, ale cho­vají se stále stejně jako ja­ký­koli jiný monoid a jsou stále kom­po­no­va­telné.

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

Když budu chtít zjis­tit 100 dotazů, které vedly k nej­vět­ším od­po­vě­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 od­had­nout počet uni­kát­ních IP adres a uni­kát­ních uži­va­telů v každém měsíci pomocí Hy­per­Lo­gLogu, který po­tře­buje kon­stantní množ­ství paměti ne­hledě na to, jaká je kar­di­na­lita mno­žiny uni­kát­ní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, po­u­žití je vždycky stejné: nejdřív trans­for­muji data do cí­lo­vého tvaru a pak roz­jedu sumaci a me­cha­nis­mus mo­no­idů pod­po­řený im­pli­cit­ními pa­ra­me­try Scaly se po­stará o zbytek. Ne­zá­leží přitom jak tri­vi­ální nebo kom­pli­ko­vaná jsou data, když pro ně exis­tuje monoid, dají se sečíst.


To, že dvo­jice nu­lo­vého prvku a aso­ci­a­tivní ope­race se vy­sky­tuje často svědčí časté po­u­žití metod/funkcí jako je foldLeft:

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

V tomto pří­padě nulový prvek a aso­ci­a­tivní ope­raci mo­no­idu. Jde tedy o:

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

neboli:

Monoid.sum[M](xs)

Z roz­hraní mo­no­idu dále vy­plývá, že je možné pro­vá­dět vý­po­čet dáv­kově, na (po­ten­ci­álně ne­ko­neč­ném) proudu dat, pa­ra­lelně a je možné dělat sna­pshoty. To všechno díky aso­ci­a­ti­vitě bi­nární ope­race.

Stre­a­mo­vání je jasné – když do­stanu nová data, přičtu je k sou­čas­nému vý­sledku a všechno jede bez pro­blémů. Musím jednom za­ru­čit že ne­do­šlo ke změně pořadí v jakém po­ložky při­chá­zejí, pro­tože ope­race není nutně ko­mu­ta­tivní. Mož­nost sna­pshotů je pak duál této vlast­nosti.

Pa­ra­le­li­zace vy­plývá z faktu, že můžu výraz li­bo­volně uzá­vor­ko­vat.

Na­pří­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á­vor­ko­vat 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 me­zi­vý­sledky

AF + GM + NT + UZ

Opět je po­třeba za­ru­čit jenom, že ne­do­jde ke změně pořadí po­lo­žek a me­zi­vý­sledků (nebo za­ru­čit ko­mu­ta­ti­vitu2) a pa­ra­le­li­zace je zcela bez­pro­blé­mová a kon­cepčně za­darmo.

Tady skon­čím, pro­tože tohle stačí jako od­po­věď na tu nikdy ne­vy­slo­ve­nou otázku z let dávno mi­nu­lých. Je pře­kva­pivé, že tak málo může po­skyt­nout tolik ga­rancí a fle­xi­bi­lity, a že tolik re­ál­ných a uži­teč­ných věcí, struk­tu­rou od­po­vídá něčemu, co na první pohled vypadá jako aka­de­mická po­div­nost po­psaná ně­ko­lika řec­kými pís­meny a zcela ne­pří­stupná re­ál­nému světu prag­ma­tiků, kteří se dřou pod pra­po­rem worse is better.

V po­dob­ném duchu ne­če­kané abs­trakce, která se ob­je­vuje na ne­če­ka­ných mís­tech se nese před­náška Re­gexes, Kleene al­ge­bras, and real ul­ti­mate power!. Člověk nemusí po­cho­pit všechny de­taily, aby cítil ne­po­pi­ra­tel­nost před­sta­vo­vané abs­trakce.


Jako člověk, kte­rému se ne­štítí po­čí­tání taktů pro­ce­soru se musím zmínit ještě o jedné věci – výkonu. Al­ge­bird byl na­vr­žen s kon­cepční čis­to­tou, která ne nutně musí vést k rych­lému vý­sled­nému pro­gramu. Sumace pomocí mo­no­idů uva­žuje, že všechny ob­jekty jsou ne­měnné a při každém součtu se vy­tvoří další, což vede k po­měrně di­vo­kým alo­ka­cím. To je ještě horší pro­blém, když sčítám mapy tuplů vno­řené do jiných map tuplů. Při každé ite­raci je velká část této struk­tury znovu vy­tvo­řena. Ne celá, pro­tože per­si­s­tentní datové struk­tury po­u­ží­vají struk­tu­rální sdí­lení pod ka­po­tou. Přesto jde o řádově víc alo­kací, než by dělal kód, který ma­ni­pu­luje mě­ni­tel­nými struk­tu­rami. Vý­sle­dek může být až ně­ko­li­krát po­ma­lejší. Ale na druhou stranu je sumace pro­střed­nic­tvím mo­no­idů ne­srov­na­telně jed­no­dušší (hlavně, když se do hry do­sta­nou hlu­boce vno­řené struk­tury) a bez­pečně pa­ra­le­li­zo­va­telná. Si­tu­aci také pomáhá fakt, že ve scale jsou im­mu­table mapy a mno­žiny ručně spe­ci­a­li­zo­vány pro 1 až 4 po­ložky. Alo­kace malých map/množin je tedy re­la­tivně levná, pro­tože není třeba vy­tvo­řit celé HAMT. Tech­nicky by bylo možné pro­vést stream fusion (na­pří­klad pomocí maker), které by od­stra­nilo nut­nost alo­kace do­čas­ných a efemér­ních ob­jektů.

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


  1. Fakt, že po­lo­grupy po­strá­dají nulový prvek lehce kom­pli­kuje ně­které ope­race. Když chci sečíst li­bo­vol­nou sek­venci dat, po­lo­grupa si s tím neumí po­ra­dit, pro­tože li­bo­volná sek­vence může být prázdn. V ta­ko­vém pří­padě by se vy­pla­tilo vrátit nulový prvek. V Al­ge­bi­rdu je proto na třídě Semigroup de­kla­ro­vána metoda sumOption(xs: TraversableOnce[T]): Option[T]sum zcela chybí.
  2. Mnoho ope­rací je ko­mu­ta­tiv­ních, pro­tože jsou zá­ro­veň idem­po­tentní: min, max, sjed­no­cení množin, lo­gické ope­race, kon­strukce Bloom fil­teru a Hy­per­Lo­gLogu. Jiné nejsou idem­po­tentní, ale přesto ko­mu­tují: sčí­tání, kon­strukce Count-min sketch.

Dále k tématu:

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články