23 - monádok

A funkcionális programozási paradigmában az ember előbb-utóbb találkozik azzal a fogalommal, hogy ,,monád''. Szokták erre mondani, hogy ,,aki megérti, mi az a monád, képtelenné válik arra, hogy elmagyarázza, mi az a monád'', de azért csak próbáljuk meg.

Elöljáróban: a List az egy monád lesz, mert generikus, mert van neki flatMapje, mert van egy megfelelő konstruktora és ezek között teljesülnek bizonyos összefüggések.

Vegyük tehát sorra:

generikus, unit, flatMap

• Egy monád: egy M[T] generikus osztály.
• Kell legyen egy olyan ún. unit[T]: T => M[T] generikus metódus/függvény, mely egy T értékből egy M[T] értéket készít. Ez Scalában jó közelítéssel az M osztály companion objectjében egy apply(value: T): M[T] metódus.
• Kell legyen egy flatMap[U]( f: T=>M[U] ): M[U] metódusa.
• Monád axiómák: mindjárt rátérünk.

Eddig a List-re ezek teljesülnek:

• List[T] tényleg generikus osztály, T típusú elemeket tároló listák az ebbe a típusba tartozó értékek.
• Van neki unit függvénye, hiszen pl. a List(3) hívással a 3-ból, ami egy Int, készítünk egy List[Int]-et, mégpedig az egyelemű (3) listát. Int-ből List[Int]-et, általában meg T-ből List[T]-t, eddig rendben van.
• Van neki flatMap metódusa, pont ezzel a szignatúrával: flatMap[U]( f: T=>List[U] ): List[U].

és a monád axiómák

Három monád axióma van, aminek minden x: T, f:T=>M[U], g:U=>M[V] és m:M[T] típusú értékre teljesülnie kell, hogy M-et monádnak nevezzük:

• unit(x).flatMap(f) = f(x) - ez a ,,balegység'' tulajdonság,
• m.flatMap(unit) = m - ez a ,,jobbegység'' tulajdonság,
• m.flatMap(f).flatMap(g) = m.flatMap( x => f(x).flatMap(g) ) - ez az ,,asszociativitás''.

a List osztály teljesíti az axiómákat, tehát monád

Hogy kicsit könnyebben emészthető legyen, nézzük meg, ezek mit is jelentenek konkrétan az M = List osztály esetén:

• balegység: List(x).flatMap(f) = f(x) kéne teljesüljök, ha f:T=>List[U] függvény. Nézzük, mi is ez:
  • f(x) ezek szerint valami lista, U típusú elemeké, legyen mondjuk (y1,y2,..,yk). Ez van a jobb oldalon.
  • List(x) az egy egyelemű lista, x van benne egyedül.
  • ha ezen az egyelemű listán flatmappelünk, mondjuk úgy nézzük, hogy előbb mapelünk, aztán flattenelünk:
  • map után (x)-ből lesz ((y1,y2,..,yk)) (note a dupla zárójelet: ez most egy List[List[U]])
  • flatten után ebből is (y1,y2,...,yk) lesz, tehát a két oldal tényleg egyenlő.
• jobbegység: m.flatMap( List.apply ) = m, ha m egy tetszőleges lista. Nézzük:
  • legyen mondjuk m=(x1,x2,...,xn) egy lista
  • ezen alkalmazva a flatMap-et a List.apply metódussal (ami a unit Scala megfelelője), végig kell mennünk mondjuk a listán, mapni minden elemét a List(_) metódussal, aztán flattenelni az eredményt
  • ha ezzel a metódussal mapünk, akkor abból először is lesz ((x1),(x2),...,(xn)) (minden elem helyébe bekerül az őt tartalmazó egyelemű lista)
  • aztán flattenelés után ebből visszakapjuk a (x1,x2,..,xn) listát, tehát a két oldal tényleg egyenlő.
• asszociativitás: m.flatMap(f).flatMap(g) = m.flatMap( x => f(x).flatMap(g) ), ha m egy lista, f és g meg megfelelő szignatúrájú függvények. Lássuk, mi ez:
  • legyen m=(x1,x2,...,xn) a listánk
  • hogy beszélni tudjunk az f-ről, ennek az x-ekhez egy-egy (mondjuk) U típusú listát kell visszaadnia, legyen mondjuk f(x1) = (y11,y12,..,y1t1), f(x2)=(y21,y22,...,y2t2) stb.
  • akkor m.flatMap(f) = (y11,y12,...,y1t1,y21,y22,...,y2t2,...,yn1,yn2,..,yntn), az összes eredménylista konkatenáltja
  • a g függvény ezekből az y-okból mindből készít egy-egy (mondjuk) V típusú listát, legyen mondjuk g(yij) = (zij1,zij2,..,zijkij)
  • a hosszú y listánkon pedig ezzel flatmapve azt kapjuk, hogy m.flatMap(f).flatMap(g) = (z111,z112,...,z11k11,z121,z122,...,z12k12,...,zntn1,zntn2,...,znznknzn), a lényeg, hogy itt meg ezek a listák vannak megfelelő sorrendben egymás után konkatenálva: legelőször mindenki, aki végülis x1-ből készült, majd azok, akik végülis x2-ből, stb.
  • lássuk a jobb oldalt: m.flatMap( x => f(x).flatMap(g) ), nézzük, akkor minden xi-n ezt a belső függvényt, f(xi).flatMap(g)-t kell kiértékelnünk és az eredménylistákat egymás után fűzni
  • ebből f(xi)=(yi1,..,yiti)
  • és ha ezen flatmapjük g-t, azt kapjuk, hogy xi képe (zi11,zi12,..,zi1ni1,zi21,zi22,...,zi2ni2,...,ziti1,...,zitiniti)
  • amiket ha egymás után írunk az xi-k eredeti sorrendjében, itt is visszakapjuk az összes olyan elem listáját ugyanabban a sorrendben, mint az előbb, amiket úgy kapunk, hogy az eredeti lista elemein alkalmazzuk f-et, az így előálló listák elemeinek mindegyikén alkalmazzuk g-t, és az így előálló listák elemeit elsősorban az x indexe, másodsorban ha az x megegyezik, akkor az f(x)-beli lista sorrendje szerint rakjuk őket sorba.

Tehát a List egy monád.

monádban van map és flatten is

Kicsit korábban kifejezgettük oda-vissza a flatMap, flatten és map metódusokkal (és a List.apply metódussal) egymást. Ez nem volt véletlen: ha van egy monádunk, abban pontosan úgy definiáljuk a map és flatten metódusokat, mint ahogy a listában tettük.

Persze a Scala nem fogja nekünk ellenőrizni, hogy ha van egy generikus osztályunk, flatMappel és apply[T]vel a companion objectben, akkor vajon teljesítjük-e a monád axiómákat és ha van még map meg flatten metódusunk is, annak valóban ,,köze van-e'' a flatMaphez. Mindazonáltal jó gyakorlat az, ha így nevezzük el a metódusainkat, akkor így is viselkedjenek; persze lehet hatékonyabban implementálni őket, mint a lenti ,,definícióban'' ahogy szerepel, a lényeg, hogy ugyanazt az értéket adja, mint amit a két lenti összefüggés megszab:

• Ha M egy monád, akkor a map metódusát definiáljuk a következőképpen: ha m:M[T] és f:T=>U, akkor legyen

  m.map(f) = m.flatMap( x => unit(f(x)) )
  

• Ha M egy monád, akkor a flatten metódusát definiáljuk a következőképpen: ha m:M[M[T]], akkor legyen

  m.flatten = m.flatMap( x=>x )
  

Ellenőrizzük le, hogy ezek az absztrakt monád metódus definíciók megfelelnek a List monád azonos nevű metódusainak!

Ahogy korábban is: * az `(x1,...,xn).flatMap( x => List(f(x)) )` kifejezés értéke a `((f(x1)),(f(x2)),...,(f(xn)))` lista flattened értéke, azaz pont `(f(x1),f(x2),...,f(xn))` lesz, ami valóban a `map` értéke lenne; * az `((x11,x12,..,x1t1),(x21,x22,..,x2t2),...,(xn1,xn2,..,xntn))`-re hívva az identikus `x=>x` függvényt, majd flattenelve tényleg (ofc) megkapjuk a flattened listát.

Válasz mutatása

Tehát mostantól ha monádokról beszélünk, azokban lesz flatMap és unit, és az így definiált map és flatten is.

Persze a List-nek is, mint minden beépített osztálynak, ha van egy adott célra megnevezett függvénye, akkor használjuk is azt, nehogy pl. egy mapet úgy végezzünk el, hogy egyelemű listákat építünk, aztán flatMapelünk. A lényeg csak az, hogy egy monádban a map, flatten, flatMap és unit metódusok részéről elvárt egyfajta ,,kontrakt'', hogy úgy viselkedjenek, hogy megtehessünk ezen az alapon valamiféle átírásokat kiértékeléskor, és tudjunk bizonyítani a programunkról (jó esetben legalább félig automatikusan) helyességet.

---

Utolsó frissítés: 2020-12-24 19:34:45