26 - a Set monád¶

A Set monád értékek egy halmazának tárolására alkalmas, minden érték legfeljebb egyszer szerepel benne. Szintén aliasolva van a Predef objektumban, alapértelmezésben a scala.collection.immutable.Set traitről beszélünk.

monád¶

Lássuk csak, miért is monád:

Generikus típus: Set[T]-ben T típusú értékeket tárolhatunk.
Van unit függvénye: a szokásos módon a companion object apply metódusa. Pl. val set = Set(7)-tel létrehozunk egy Set[Int]-et, melynek egyetlen eleme a 7-es szám.
Van flatMap[U]( f: T => Set[U] ): Set[U] metódusa. Ennek a szignatúrája megfelel a flatMap által elvártnak, de persze ez még kevés szemantika nélkül: ahogy azt (valószínűleg) el is várjuk, az eredmény, ha a setünk az { x1, x2, .., xn } halmaz (halmazokat kapcsosban fogunk jelölnk), melyben ugye T típusú elemek vannak, akkor az f(xi)-k a függvény fejléce alapján mint U-beli elemek halmazai, a flatMap(f) hívás eredménye pedig ezeknek az f(xi) halmazoknak az uniója.

Ellenőrizzük le a monád axiómákat egyesével!

Balegység tulajdonság teljesül?

Azt kell ellenőrizzük, hogy teljesül-e tetszőleges `x:T`-re és `f:T=>Set[U]`-ra, hogy

1	`Set(x).flatMap(f) == f(x)`

Persze: a bal oldalon a fenti def szerint azt kapjuk, hogy vegyük az `{x}` halmazt, minden elemén értékeljük ki `f`-et (egy eleme van neki, az eredmény az `f(x)` halmaz lesz, benne `U` típusú elemekkel), majd a kapott halmazoknak (annak az egynek) vegyük az unióját - semmi nem történik, az eredmény tényleg `f(x)`.

Válasz mutatása

Jobbegység tulajdonság teljesül?

Azt kell ellenőrizzük, hogy teljesül-e tetszőleges `m = {x1,..,xn}:Set[T]`-re, hogy

1	`m.flatMap( x => Set(x) ) == m`

Az `{x1, x2, ..., xn}` halmaznak minden `xi` eleméből a `unit` művelet először is elkészíti az `{x1}`, `{x2}`, ..., `{xn}` halmazokat, majd ezeknek vesszük az unióját: `{x1,x2,..,xn}`, tényleg visszakapjuk az eredeti halmazt.

Válasz mutatása

Asszociativitás teljesül?

Ellenőrizendő: igaz-e minden `m = {x1, x2, ..., xn}:Set[T]`-re, `f:T=>Set[U]`-ra és `g:U=>Set[V]`-re, hogy

1	`m.flatMap(f).flatMap(g) == m.flatMap( x => f(x).flatMap(g) )`

Most kicsit kevésbé formálisan, mint ahogy a listánál tettük: * az `m.flatMap(f)` egy `Set[U]`, benne van az összes olyan `U` típusú érték, mely szerepel valamelyik `f(xi)` alakú halmazban * akkor az `m.flatMap(f).flatMap(g)` egy `Set[V]` benne van az összes olyan `V` típusú érték, melyet megkaphatunk úgy, hogy vesszük valamelyik `xi`-t, majd az `f(xi)` halmazt, abból egy `yj` elemet, majd a `g(yj)` elemet, és akit így megkaphatunk, pontosan azok az elemek szerepelnek a bal oldali halmazban. * a jobb oldalon: ha kiindulunk egy `xi` értékből, az `f(xi).flatMap(g)` kifejezés értéke egy `Set[V]`, melyet úgy kapunk, hogy összeuniózzuk az összes `g(yj)` értéket azokra az `yj`-kre, melyek `f(xi)`-ben benne vannak * az első `flatMap` pedig pontosan ezeket a halmazokat uniózza össze. Azt kaptuk tehát, hogy mindkét oldalt az `⋃_{x∈m}⋃_{y∈f(x)}g(y)` halmaz szerepel, tehát tényleg teljesül ez az axióma is.

Válasz mutatása

nem jegyzi az eredeti sorrendet¶

Ha szeretnénk a beszúrás ,,sorrendjét'' is tárolni (immutable adatszerkezetnél persze ez valami felépülési sorrendet jelent inkább), akkor talán inkább használjunk egy vektort, vagy egy vektort és egy setet együtt. A default implementáció valami ilyesféleképp viselkedik (eltérhet):

1
2
3

  val theSet = Set(1,4,2,8,5,7)

  println( theSet ) //prints HashSet(5, 1, 2, 7, 8, 4)

Az alap implementáció (as of Scala 2.13) a HashSet, mint azt láthatjuk: algoritmusok és adatszerkezetek kurzuson fogunk tanulni erről, a főbb támogatott műveletei:

természetesen tudunk rajta mapni, filterni, foreachni a flatMap mellett. A Set eredeti bejárási sorrendjének nem feltétlen lesz köze az eredmény set bejárási sorrendjéhez! pl:

  val theSet = Set(1,4,2,8,5,7)

  println( theSet )                  //HashSet(5, 1, 2, 7, 8, 4)
  println( theSet filter { _ > 3 } ) //HashSet(5, 7, 8, 4)
  println( theSet map { _ * 2 } )    //HashSet(10, 14, 2, 16, 8, 4)
  println( theSet flatMap { x => Set(x, 2*x) } ) //HashSet(5, 10, 14, 1, 2, 7, 16, 8, 4)

Pl. a mapnél láthatjuk, hogy előbb listázza az 5 dupláját, majd a 7-ét, majd az 1-ét stb; a flatmapnél is igaz, hogy a készített kételemű setek, melyeknek aztán az unióját vesszük, elemei is kerülhetnek egymástól simán ,,messze'', pl. a 7 és a 14 esetében ahogy láthatjuk.

Ennek okait megérthetjük majd algoritmusokon, a lényeg, hogy azért, hogy a keresés, beszúrás és törlés műveletek hatékonyak legyenek, a HashSet adatszerkezet egy úgynevezett hashCode alapján tárolja az elemeket.

hashCode és ==¶

Ugyanúgy, mint ahogy toString: String metódus is létezik minden objektumhoz, ugyanúgy egy hashCode(): Int metódus is, mely ,,valamilyen alapon'' egy int számot rendel az objektumhoz. Ami itt fontos: ha két elem egyenlő, akkor a hash kódjuk is meg kell egyezzen. A hashset lényegében létrehoz egy Vector[List[T]]-t, és a hashcode alapján számítja ki, hogy a vektor hanyadik elemében lévő listába szúrja be a beszúrandó elemet. Ha a hashcode függvény ,,jól'' van megírva, akkor nagyjából egyenletesen fogja szétszórni a vektorban az elemeket, ha azok ,,random'' objektumok, így a listák hossza ,,átlagban'' kicsi lesz; olyankor meg, mikor kezd betelni a vektor, foglal egy nagyobbat és abba újra szétosztja hashcode alapján az objektumokat, ezzel azt remélve, hogy majd így megint rövidülnek a listák.

A lényeg, hogy ha jól van megírva a hashcode függvény, akkor egy hashsetben átlagos esetben konstans idő alatt lehet beszúrni, törölni, keresni a következő metódusokkal:

contains(elem: T):Boolean, ugyanaz, mint apply(elem: T):Boolean: igaz, ha elem szerepel a halmazban
+(elem: T): Set[T]: visszaad egy új halmazt, melyben az összes eredeti elem és elem is szerepel. (Ha elem eleve benne volt, nem változik a halmaz)
-(elem: T): Set[T]: visszaad egy új halmazt, melyben az összes eredeti elem szerepel, kivéve elemet. (Ha elem eleve nem volt benne, nem változik a halmaz)

Természetesen ahogy a többi kollekciónak is, ennek is rengeteg metódusa van, a teljesség igénye nélkül pl. toVector, toList metódusokkal lehet az elemeiből (valamilyen sorrendben) vektort ill. listát gyártani, utóbbi kettőnek és az Optionnek is van toSet metódusa, ami az elemeikből készít egy halmazt; a ++ metódus két halmaz unióját, -- a különbségét, & a metszetét állítja elő (ezek a műveletek már nem konstans időigényűek!), lehet az elemeit redukálni/foldolni is, isEmpty adja vissza, hogy üres-e a halmaz, size pedig a méretét.

case classok under the hood¶

Amit pl. egy case class deklaráláskor ,,ingyen'' kapunk, az egy hashCode és egy == implementáció: az == először a referenciát teszteli, hogy egyezik-e (ha ugyanaz a memóriacím, ahol a ,,két'' objektum van, akkor persze hogy egyenlőek), majd magát a konkrét osztályt (ha az egyik Alma, a másik Süti, akkor persze, hogy nem egyenlőek), és ha a két konkrét osztály megegyezik, akkor rendre az adattagok egyenlőségét (ha mind páronként egyenlő, akkor egyenlőek), rekurzívan az azok == operátorával.

Továbbá, kapunk egy hashCode implementációt is, ami az adattagok hashcode-jaiból aggregál össze egy új hashcode-ot.

Ezzel kapcsolatban pár dolgot érdemes megjegyezni:

ha nem case classt, hanem sima classt deklarálunk, akkor ezt se kapjuk meg - ekkor az == metódusunk pl. csak akkor jelenti le, hogy két objektum egyenlő, ha a memóriacímük ugyanaz, rendszerint nem ez az, amit szeretnénk, a hashcode is a memóriacímből számítódik
ha Javát használunk, ott is így van, nekünk kell kézzel megírni az equals metódust és a hashCode metódust, méghozzá úgy, hogy az equals akkor mondja, hogy true, ha szeretnénk, hogy ez a két objektum ,,érték szerint'' egyenlő legyen, és a hashCode-ot is úgy kell megírjuk, hogy ha két objektum egyenlő érték szerint, akkor a hash kódjuk egyezzen meg,
ebből a tárgyból nem nagyon fogunk mutálódó adattal dolgozni, de egy imperatív nyelven, mint a Java, szoktunk. A HashSet működése Javában is hasonló: a hashCode alapján berakja az elemet egy vektor egy elemébe egy kollekcióba. Ez azt jelenti, hogy ha a hashcode megváltozna, akkor nem rakná át máshova: a hashCode az objektum teljes életciklusa alapján ugyanaz kell maradjon! Tehát például nem számolhatjuk a hashcode-ot olyan adattagokból, melyek megváltozhatnak, csak a finalokból.
hashingről még lehet pl. olvasni itt is.

SortedSet¶

Lehet rá igényünk, hogy a halmazunk valamiféle rendezés szerint növekvő sorrendben tárolja az adatokat. Erre alkalmas a SortedSet adatszerkezet, használata:

import scala.collection.immutable.SortedSet //ez már nincs a Predefben

val theSet = SortedSet(1,4,2,8,5,7)

println( theSet )                  //TreeSet(1, 2, 4, 5, 7, 8)
println( theSet filter { _ > 3 } ) //TreeSet(4, 5, 7, 8)
println( theSet map { _ * 2 } )    //TreeSet(2, 4, 8, 10, 14, 16)
println( theSet flatMap { x => Set(x, 2*x) } ) //TreeSet(1, 2, 4, 5, 7, 8, 10, 14, 16)

Mivel a SortedSet leszármazottja a Set traitnek, minden metódussal rendelkezik, mint az eredeti Setünknél amiket felsoroltunk. Láthatjuk, hogy (as of Scala 2.13) a default implementációja egy TreeSet, ami egy ún. kiegyensúlyozott bináris keresőfa adatszerkezet, algából lehet, hogy ezt is tárgyaljuk részletesebben. Mindenesetre amit érdemes tudni róla:

csak akkor tudjuk használni, ha az adattípusunk rendezhető, vagy ha szállítunk neki egy rendező metódust konstruáláskor Utóbbira példa: ha pl. Stringeket akarunk tárolni hossz szerint növekvő sorrendben, átadhatunk így egy compare metódust:

  val stringSet = SortedSet()( (x: String, y: String) => x.length - y.length )
  val plusSet = stringSet ++ Vector("dinnye", "alma", "körte")
  println( plusSet )  //TreeSet(alma, körte, dinnye)
  println( plusSet.contains("sanyi") ) //true!!!

Mit is látunk itt?

Mikor létrehozzuk a halmazunkat, átadhatunk egy összehasonlító metódust, ami az input adattípusból kap két elemet, és visszaad egy Intet: azt kell biztosítsuk, hogy negatív legyen, ha x<y, pozitív, ha y<x és 0, ha x=y.
Tehát pl. az igaz, hogy így a rövidebb stringeket ezzel a kivonással a hosszabbak elé rendezzük
Viszont a definíció azt is mondja, hogy pontosan akkor adjunk vissza nullát, ha egyenlőnek akarjuk kezelni a két elemet: így ez a rendezés pl. az egyenlő hosszú stringeket ,,érték szerint egyenlőnek'' kezeli, ezért adja vissza, hogy contains("sanyi") igaz, mert a Setben lévő "körte" string is pont 5 karakter hosszú, tehát az átadott komparátorunk szerint egyenlőek.
Általában nem ez az, amit szeretnénk. Jó gyakorlat mindig úgy megírni a komparátort és az ==-t (Scalában) vagy equalst (Javában), hogy a komparátor pontosan akkor adjon vissza 0-t, ha az == / equals true-t!

Kérdések¶

Nem mond ez a legutóbbi annak, hogy a SortedSet egy monád?

Lehet készíteni olyan ,,rendezést'', amin az **asszociativitás** nem teljesül (próbáljunk meg készíteni egyet!) Azonban **matematikailag** az egyenlőség mást jelent, mint pl. Scalában: matematikában ha két objektum, `x` és `y` egyenlőek, akkor például tetszőleges `f` függvényre `f(x)==f(y)` is muszáj teljesüljön. Mivel felül tudjuk írni (például) a hashcode, az `==` vagy a compare metódusokat úgy, hogy egyenlőnek ,,lejelentett'' értékekre lehetséges legyen, hogy valamilyen `f` függvény mégis mást adjon eredményül a két értékre, ezért **el lehet rontani** az asszociativitást. Ha a definícióban szereplő `f`-re és `g`-re megköveteljük, hogy ,,ha `x==y`, akkor `f(x)=f(y)` és `g`-re hasonlóan, akkor már kijön az asszociativitás is.

Válasz mutatása

Utolsó frissítés: 2020-12-25 13:10:44