16 - map, filter, reduce, fold

Felmerül a kérdés, hogy mégis mikor érdemes valamit tagfüggvényként implementálni egy osztályon belül, és mikor rajta kívül. Van, amikor nincs más választásunk, mint bent deklarálni (pl. amikor olyan adathoz fér hozzá a függvény, ami csak az osztályon belül látható - a láthatósági módosítókról is lesz később poszt). Mindenesetre, ha van az IntListünk, és egy alkalmazásban szeretnénk pl. egy függvényt, ami visszaad egy listát, amiben minden elem kétszerese az eredeti listabelinek (tehát pl. az (1,4,2,8,5,7) listán hívva a (2,8,4,16,10,14) új listát adja vissza), azt persze leimplementálhatjuk így is:

trait IntList {
  def szorzasKettovel: IntList
}
case object Ures extends IntList {
  override val szorzasKettovel = Ures  //note: defet lehet vallal overrideolni
}
case class Nemures(head: Int, tail: IntList) {
  override def szorzasKettovel = Nemures(head * 2, tail.szorzasKettovel)
}

(Remélhetőleg) azt érzi ilyenkor az ember valahol belül, hogy ez így nem vezethet jóra, mindenkinek, aki valamikor később használni fogja az IntList osztályunkat, ki lesz ajánlva egy ,,szorzás kettővel'' függvény, amit jó eséllyel nem használna, mert csak egy bizonyos alkalmazásban egy bizonyos célra volt rá szükség.

Pláne, ha egy másik alkalmazásban épp kilenccel kell szorozni az elemeket, egy másikban hármat hozzáadni... és egy nagyon furcsa abomination kezd kifejlődni, ha ezt az utat követjük:

trait IntList {
  def szorzasKettovel: IntList
  def szorzasKilenccel: IntList
  def pluszHarom: IntList
}
case object Ures extends IntList {
  override def szorzasKettovel = Ures
  override def szorzasKilenccel = Ures
  override def pluszHarom = Ures
}
case class Nemures(head: Int, tail: IntList) {
  override def szorzasKettovel = Nemures(head * 2, tail.szorzasKettovel)
  override def szorzasKilenccel = Nemures(head * 9, tail.szorzasKilenccel)
  override def pluszHarom = Nemures(head + 3, tail.pluszHarom)
}

map

Ez az a pont, ahol egy kicsit messzebbről szemlélve a kódot valami általánosabb mintát láthatunk benne, amivel elég csak egy függvényt implementálni: mivel funkcionális programozásban próbálunk gondolkodni, észrevehetjük, hogy itt valójában két dolog szerepel inputként: a lista és egy művelet, ami a lista elemeit transzformálja valahogy egyenként, függetlenül. Az első esetben a kettővel szorzás függvény, a másodikban a kilenccel szorzás, a harmadikban a hármat hozzáadás.

Ezt így is meg lehet csinálni:

trait IntList {
  def map(f: Int=>Int): IntList //a map metódus megkapja a trafó függvényt
}
case object Ures extends IntList {
  override def map(f: Int=>Int) = Ures  //üres listából üres lista lesz
}
case class Nemures(head: Int, tail: IntList) extends IntList {
  override def map(f: Int=>Int) = Nemures(f(head), tail.map(f))
}

//tesztelgessük lambdákkal
val list = Nemures(1,Nemures(4,Nemures(2,Ures)))
println(list.map({x: Int => 2*x})) //prints Nemures(2,Nemures(8,Nemures(4,Ures)))
println(list.map { x => 9*x })     //prints Nemures(9,Nemures(36,Nemures(18,Ures)))
println(list.map { _+3 })          //prints Nemures(4,Nemures(7,Nemures(5,Ures)))
val myFavFunc: Int => Int = { x => 7*x }
println(list.map(myFavFunc))       //prints Nemures(7,Nemures(28,Nemures(14,Ures)))

Emlékeztető:

• függvényeket tudunk átadni paraméterként, a map metódus pl. egy Int=>Int függvényt vár
• lambdákat tudunk deklarálni pl. {x: Int => 2*x} alakban, ez így Int=>Int lesz mindenképp, odaadhatjuk a mapnak
• de mivel a map eleve Int=>Int függvényt vár, ha nem írjuk ki x explicit típusát, akkor (mivel a mapnak adjuk oda) a fordító arra próbál rá, hogy x legyen Int
• nem kell kirakjuk a kapcsos köré a kerek zárójelet, mert map egy unáris tagfüggvény (elé se kell feltétlen a pontot)

Az alsó három példában láthatjuk, hogy így miért is tudtuk egy füst alatt lekezelni a (valószínűleg) alkalmazásfüggő ,,szorozd konstanssal''-like függvényeket: egyszerűen csak a transzformációt kell átadjuk argumentumként. Ha ugyanazt a transzformációt használjuk sok helyen a kódban, akkor persze érdemes kimenteni egy (mondjuk) val mezőbe, és akkor látszik is, hogy miért is csináljuk, amit - és ha változtatni kell a függvényt, akkor elég lesz egy helyen piszkálni a kódot. (A fenti példában pl. a myFavFunc lehet az, amelyiket többször is alkalmazzuk több kollekcióra, és ha így van, akkor csak egy helyen kell átírjuk, ha valami változik.)

A map metódus viszont már olyan, amire gyakran lehet szükség, lista- vagy úgy általában kollekcióelemeket transzformálni gyakran szoktunk, így a map tagfüggvényként deklarálása teljesen rendben van.

filter

Egy másik gyakran használt listaművelet a filter: pl. ha az IntListünkben gondolkodunk, akkor lehet az egy feladat, hogy legyűjtsük a pozitív értékeket egy listába, vagy a páratlan számokat:

trait IntList {
  def pozitivak: IntList
  def paratlanok: IntList
}
case object Ures extends IntList {
  override def pozitivak = Ures
  override def paratlanok = Ures
}
case class Nemures(head: Int, tail: IntList) extends IntList {
  override def pozitivak = if (head>0) Nemures(head, tail.pozitivak) else tail.pozitivak
  override def paratlanok = if (head%2==1) Nemures(head, tail.paratlanok) else tail.paratlanok
}

ugyanúgy, mint az előbb, rájöhetünk arra is, hogy ez egy általános minta, amit egy predikátum (az objektumból, mint most az Int, Booleanba képző függvényeket hívják így) átadásával tudunk egységesen kezelni:

trait IntList {
  def filter(p: Int=>Boolean): IntList
}
case object Ures extends Intlist {
  override def filter(p: Int=>Boolean) = Ures
}
case class Nemures(head: Int, tail: IntList) extends IntList {
  override def filter(p: Int=>Boolean) = if (p(head)) Nemures(head, tail.filter(p)) else tail.filter(p)
}

//teszteljük
val list = Nemures(1,Nemures(4,Nemures(2,Ures)))
println(list.filter { _%2==1 }) //prints Nemures(1,Ures)

fold / reduce

Egy harmadik tipikus műveletcsalád, amit egy kollekción (mondjuk egy listán) gyakran végzünk: a redukálás, mikor a lista egészéből valamiféle kétváltozós művelet alapján számított eredményt szeretnénk visszaadni.

Ilyenek például:

• adjuk vissza a lista elemeinek az összegét: itt pl. ha a listánk (x1,x2,..,xn), akkor az eredmény az x1+x2+...+xn összeg, amit az összeadás _+_ kétváltozós műveletből meg tudunk kapni pl. ((((x1+x2) + x3) + x4) + ... ) + xn formában: kiindulva x1 értékéből mint ,,aktuális értékből'', majd a lista minden egyes elemét hozzáadjuk (jobbról) az aktuális értékünkhöz
• szorzatát: ugyanez, csak a szorzás művelettel
• maximumát: ugyanez, csak a max függvénnyel, minimum is ugyanez

Írjunk olyan függvényt a listánkba, mely kap egy iniciális értéket ,,aktuális érték''ként, és egy kétváltozós aggregátor függvényt, és a fenti módon összeaggregálja, redukálja a lista elemeit! Ha a függvény neve mondjuk reduce, akkor mi lesz a fejléce?

def reduce( init: Int, op: (Int,Int) => Int ): Int

Válasz mutatása

Implementáljuk is a függvényt!

trait IntList {
  def reduce( init: Int, op: (Int,Int) => Int ): Int
}
case object Ures extends Intlist {
  //üres listán csak vissza kell adnunk az aggregált értéket
  override def reduce( init: Int, op: (Int,Int) => Int ) = init  
}
case class Nemures(head: Int, tail: IntList) extends IntList {
  //aggregáljuk a fejjel az értékünket, és az eredménnyel redukáljuk a farkat
  //tail rekurzív!
  override def reduce( init: Int, op: (Int,Int) => Int ) =       
    tail.reduce( op(init,head), op )
}

//teszteljük
val list = Nemures(1, Nemures(4, Nemures(2, Ures)))
println( list.reduce(0, { _+_ } ) ) //prints 7

Válasz mutatása

Valójában többféle módon szokás redukálni egy kollekciót:

• A fentit, mikor is a lista elemeinek a típusa egyben a kiszámított eredmény típusa is, azt redukálásnak hívják
• Az asszociativitás egy fontos tulajdonság: azt kéri, hogy az átadott op műveletre igaz legyen op(op(x,y),z) == op(x,op(y,z)) tetszőleges x,y,z értékekre. Ha ez nem teljesül, akkor tudatosan kell választanunk a reduceLeft és a reduceRight opciók közül: a fenti, amit implementáltunk, a reduceLeft, mikor is a lista fejelemétől kezdjük el az aggregálást, és mindig op(akt,current) lesz az új aggregált értékünk, ha eddig akt volt, current pedig a lista következő eleme. A reduceRight a lista végétől indul és mindig op(current,akt) lesz az új érték.
• A ,,redukálás'' üres listára nem mindig definiált: sokszor csak a kétváltozós műveletet kell átadjuk kezdőérték nélkül és a lista fejével kerül inicializálásra.
• Ha üres listára, kezdőértékkel kell működjön a kód, és nem feltétlen ugyanaz a típus lesz az aggregált érték, mint ami a listánkban lévő adatoké, akkor a műveletet foldnak nevezzük (és ennek is van left/right változata).

Alakul a listánk! Kár, hogy ha nem Inteket akarunk tárolni, akkor újra kell írni az egészet... vagy nem?

Kérdések, feladatok

• Írjuk meg a map és filter metódusokat tail rekurzívan is! Ehhez lehet, hogy szükségünk lesz egy reverse függvényre, mely megfordítja (tail rekurzívan) a listánkat.
• Bizonyítsuk be a korábbi indukciós módszerrel, hogy a map, filter és reduce metódusok fenti implementációja tényleg helyes.

---

Utolsó frissítés: 2021-02-07 23:06:47