09 - match, case, mintaillesztés

Volt az inteket tároló lista adatszerkezetünk:

trait Lista
case class UresLista() extends Lista
case class NemuresLista(head: Int, tail: Lista) extends Lista

Most erre fogunk feldolgozó kódot írni. Funkcionális programozásban nagyon gyakori az algebrai adattípusok mintaillesztéssel való feldolgozása, amire Scalában a match kulcsszó való. Nézzünk példa kódot, ami kiszámolja a lista elemeinek az összegét:

def sum(list: Lista): Int = list match {
  case UresLista() => 0
  case NemuresLista(h, t) => h + sum(t)
}
println(sum(NemuresLista(1, NemuresLista(4, NemuresLista(2, UresLista())))) ) //prints 7

Mit is látunk itt? Egy értékre való mintaillesztést a match kulcsszó vezet be, ami után (kötelezően) kapcsos zárójelek közt meg kell adnunk "ha illik erre a kifejezésre a minta, akkor ez a kifejezés értéke, különben ha illik ez a minta, akkor ez, különben ha illik ez a minta, akkor ez,... " eseteket, $\mathrm{case~}P\Rightarrow E$ alakban, ahol $P$ egy "minta", $E$ pedig a kifejezés.
Hogy nézhet ki egy minta? Például:

• lehet egy azonosító. Ez mindenre illeszkedik, rögzíti (bindeli) az azonosítóhoz az illesztett értéket, és a $\Rightarrow$ jobb oldalán ezt az értéket helyettesítjük be az azonosító helyére. 
• lehet egy érték. Ez akkor illeszkedik, ha egyenlő az illesztett értékkel.
• lehet egy $C(P_1,\ldots,P_n)$ alakú kifejezés, ahol $C$ egy case class neve, aminek $n$ mezője van. Ez akkor illeszkedik, ha a bejövő érték szintén ennek a $C$ case classnak egy példánya, az első mezője illeszkedik a $P_1$, a második a $P_2$, $\ldots$, az $n$-edik (utolsó) mezője a $P_n$ mintára. Ha minden illeszkedik és az al-mintákban volt azonosító bindelés, akkor ezek mind átmigrálnak a jobb oldalra.

 Amit a fentebbi kódban láttunk, az az első és a harmadik eset kombinációjaként áll elő. Például, ha a $\mathrm{sum}$ függvény megkapja a $list=\mathrm{NemuresLista}(3,\mathrm{NemuresLista}(2,\mathrm{UresLista}()))$ értéket, akkor mi történik:

• az első case nem illeszkedik, hiszen az egy $\mathrm{UresLista}$ case class példányra illeszkedne, $list$ pedig egy $\mathrm{NemuresLista}$.
• a második case addig biztosan illeszkedik, hogy $\mathrm{NemuresLista}$ a minta is, meg az érték is, amire illesztjük. Ekkor tehát a minta akkor illeszkedik, ha stimmelnek a mezők is: azaz, ha a $h$ (azonosító) illeszkedik a $3$, a $t$ (azonosító) pedig a $\mathrm{NemuresLista}(2,\mathrm{UresLista}())$ értékre. Ezek illeszkednek, hiszen változók, tehát a match kifejezés értékét úgy kapjuk, hogy a $h+\mathrm{sum}(t)$ kifejezésben $h$ helyébe a $3$, $t$ helyébe pedig az $\mathrm{NemuresLista}(2,\mathrm{UresLista}())$ értéket helyettesítjük és ezt a kapott kifejezést kiértékeljük, tehát: $3+\mathrm{sum}(\mathrm{NemuresLista}(2,\mathrm{UresLista}()))$ értéke.

Visszanézve az összeg típus példájára, ott a "ha kör, írd ki az adatait, ha háromszög, akkor is" match kifejezés is ilyen mintákból építkezett. Vagy nézzük ezt a kicsit bonyolultabb kódot:

def vesszok(list: Lista) = {
  def vesszokR(list: Lista): String = list match {
    case UresLista() => ""
    case NemuresLista(head, UresLista()) => head.toString
    case NemuresLista(head, tail) => head + "," + vesszokR(tail)
  }
  "(" + vesszokR(list) + ")"
}

println(vesszok(NemuresLista(3, NemuresLista(7, UresLista()))) ) // prints (3,7)

Ez ha kap egy listát, akkor kiírja kerek zárójelek közt (ezután jön a rekurzív hívás) vesszőkkel elválasztva az elemeit. Itt arra kell figyelni, hogy ha a lista üres, akkor ne írjunk ki semmit, ha egyelemű (vagyis: olyan nemüres lista, melynek a farka üres), akkor csak azt az egy elemet, egyébként pedig a fejét, vessző, rekurzió a farkára.

Még néhány minta-formátum:

• A $\_$ (underscore) minta mindenre illeszkedik (ugyanúgy, mint egy azonosító), de nem bindeli az értéket változóhoz. Ezt praktice akkor használjuk, ha a jobb oldali kifejezésben az itt szereplő értéket nem használnánk semmire.
• Ha az eddigi minták után kettősponttal teszünk egy típust, tehát $P:T$ formátumú lesz a mintánk, ahol $T$ egy típus, akkor ez akkor illeszkedik, ha $P$ illeszkedik és az érték (futásidejű) típusa $T$.
• Ha a mintánk után (lehet benne típusmegjelölés is) egy $\mathrm{if~}B$ alakú ún. if guardot teszünk, ahol $B$ egy $\mathrm{Boolean}$ típusú kifejezés, akkor ez a minta akkor illeszkedik, ha maga a minta illeszkedik és $B$ értéke igaz.

Nézzünk pár példát és próbáljuk meg átgondolni, hogy miért is épp azt valósítja meg a mintaillesztés, mint amit állítunk róla!

def length(list: Lista): Int = list match { //visszaadja a list elemszámát
  case UresLista() => 0
  case NemuresLista(_, tail) => 1 + length(tail)
}

def countOdd(list: Lista) : Int = list match { //visszaadja a páratlan elemek számát
  case UresLista() => 0
  case NemuresLista(h, t) if ( h%2 == 0 ) => countOdd(t)
  case NemuresLista(_, t) => 1 + countOdd(t)
}

Elemzés közben ne felejtsük el, hogy az első illeszkedő case jobb oldala kerül kiértékelésre.
Ha már ott vagyunk, akkor írjuk meg a rekurzív függvényeket tail rekurzívra :)