14 - az immutable generic List osztály

Természetesen a lista mint adatszerkezet annyira alap komponense a funkcionális programozás eszköztárának, hogy van belőle built-in, nem kell újra írnunk mindig egyet. Nagyon sokrétű, a funkcionalitásai egy részével össze fogunk ismerkedni a félév során, mindenesetre:

• A típus neve $\mathrm{List}$ (teljes neve $\mathrm{scala.collection.immutable.List}$, de a Scala $\mathrm{Predef}$ objektumában szerepel mint type alias, ezért látszik a rövid neve is.
• Generic típus, a lista elemeinek típusát kapja paraméterként. Pl. az eddigi $(1,4,2,8,5,7)$ példánk $\mathrm{List}[\mathrm{Int}]$ típusúnak felel meg.
• Az eddigi $\mathrm{Ures}$ objektumunknak (amit genericként egyelőre csak mint case classt tudtunk összehozni) megfelelő üres lista a $\mathrm{Nil}$ nevű objektum. Igen, objektum, és mindenféle típusú generic listának megfelel, ezt később jobban meg fogjuk érteni.
• Az eddigi $\mathrm{Nemures}$ lista objektumunknak megfelelő osztály neve $\mathrm{::}$. Két kettőspont. Tehát akár így is létrehozhatunk egy $(1,4,2)$ értéket a mostani tudásunk alapján:
  

  
  val list: List[Int] = ::(1,::(4,::(2,Nil)))
  

• A $\mathrm{::}$ osztály nevét a fenti prefix (avagy lengyel) jelölés helyett infix is használhatjuk konstruáláskor, így szokás (és figyeljük meg, hogy ennek is ki tudja következtetni a type inference, hogy $\mathrm{List}[\mathrm{Int}]$ lesz:
  

  
  val list = 1 :: 4 :: 2 :: Nil
  

• A companion object apply metódusának köszönhetően így is létrehozhatjuk ugyanezt:
  

  
  val list = List(1,4,2,8,5,7)
  

• A $\mathrm{List}[T]$-ben egyebek mellett szerepelnek a $\mathrm{filter}(p:T\Rightarrow\mathrm{Boolean}):\mathrm{List}[T]$ és a $\mathrm{map}[U](f:T\Rightarrow U):\mathrm{List}[U]$ függvények, pontosan ugyanazzal a viselkedéssel, mint amit az előző posztokban láttunk.
• A $\mathrm{toString}$ metódusa visszaadja a $\mathrm{List}$ szót, majd zárójelek közé zárva vesszővel elválasztva a lista elemeit.
• Lehet rá mintailleszteni, az elv ugyanúgy megy, mint a saját korábbi implementációnkban: a nemüres listának van egy feje és egy farka, $\mathrm{head :: tail}$-ként is illeszthető rá a minta, így szoktuk kiírni, de persze fordul a $\mathrm{::(head,tail)}$ minta is.
• Egy hasznos metódusa a $\mathrm{zip}$, ami egy másik listával "pároztatja össze" úgy, hogy egy $\mathrm{List}[T]$ zipje egy $\mathrm{List}[U]$ zipjével egy $(T,U)$ párokat tartalmazó lista, vagyis egy $\mathrm{List}[(T,U)]$ lesz: az első elemek párja fogja alkotni a zipelt lista első elemét, a másodikoké a másodikat, stb, azaz pl. $\mathrm{List}(1,2,3)\mathrm{.zip~List}(\textrm{"dinnye"},\textrm{"szilva"},\textrm{"narancs"})$ értéke $\mathrm{List}((1,\textrm{"dinnye"}),(2,\textrm{"szilva"}),(3,\textrm{"narancs"}))$. Az ilyen pároknak, melyekből az eredménylista áll, egyébként az első mezőjét a $\_1$, a második mezőjét a $\_2$ adattagjukkal érjük el. Ha a zipelt listák hossza nem azonos, akkor a rövidebb lista hossza lesz az eredmény hossza, a hosszabb lista "leeső" farka nem számít az eredménybe.
• Amiért a $\mathrm{zip}$ pl. hasznos tud lenni: ha egy $\mathrm{list}$ nemüres listát zipelünk a farkával: $\mathrm{list}.\mathrm{zip}(\mathrm{list.tail})$, az, ha belegondolunk, a szomszédos elemeket teszi egy cellába, pl. $\mathrm{List}(1,4,2,8).\mathrm{zip}(\mathrm{List}(4,2,8))=\mathrm{List}((1,4),(4,2),(2,8))$. Ez hasznos lehet akkor, ha ez alapján akarunk $\mathrm{map}$ni vagy $\mathrm{filter}$ezni.

13 - generic

Hogy csak $\mathrm{Int}$eket tároló listákkal kelljen dolgozzunk, az nem egy real-life scenario. Lehet szükség $\mathrm{Double}$ listákra, $\mathrm{String}$ listákra stb. Mivel pedig maga a funkcionalitás ugyanaz mindháromban elviekben, nagyon error-prone megközelítés lenne copypaste gyártani minden típusra egy újabb és újabb osztályt pl. így:

trait IntLista {
  def filter(p: Int=>Boolean): IntLista
}
case object UresIntLista extends IntLista {
  override def filter(p: Int=>Boolean) = UresIntLista
}
case class NemuresIntLista(head: Int, tail: IntLista) {
  override def filter(p: Int=>Boolean) =
    if (p(head)) NemuresIntLista(head, tail.filter(p)) else tail.filter(p)
}
trait DoubleLista {
  def filter(p: Double=>Boolean): DoubleLista
}
case object UresDoubleLista extends DoubleLista {
  override def filter(p: Double=>Boolean) = UresDoubleLista
}
case class NemuresDoubleLista(head: Double, tail: DoubleLista) {
  override def filter(p: Double=>Boolean) =
    if (p(head)) NemuresDoubleLista(head, tail.filter(p)) else tail.filter(p)
}
trait StringLista {
  def filter(p: String=>Boolean): StringLista
}
case object UresStringLista extends StringLista {
  override def filter(p: String=>Boolean) = UresStringLista
}
case class NemuresStringLista(head: String, tail: StringLista) {
  override def filter(p: String=>Boolean) =
    if (p(head)) NemuresStringLista(head, tail.filter(p)) else tail.filter(p)
}

Ilyenkor, mikor az osztályok tényleg összesen egy mező típusában különböznek, ésszerűnek látszik az igény: bárcsak lehetne ezt parametrikusan csinálni, egyetlen osztályt implementálni mondjuk $\mathrm{Lista}$ néven és valahogy futás közben megmondani, hogy most épp egy $\mathrm{Int}$ listát, vagy $\mathrm{Double}$ listát akarunk létrehozni.

És lehet: (ahogy egyébként Javában is) a parametrikus típussal ellátott osztályt generic osztálynak nevezik és ilyen a szintaxisa a listánk esetében:

trait Lista[T] {
  def filter(p: T=>Boolean): Lista[T]
}
case class Ures[T]() extends Lista[T] {
  override def filter(p: T=>Boolean) = Ures()
}
case class Nemures[T](head: T, tail: Lista[T]) extends Lista[T] {
  override def filter(p: T=>Boolean) = if (p(head)) Nemures(head, tail.filter(p)) else tail.filter(p)
}

val intList = Nemures[Int]( 1, Nemures[Int](4, Nemures[Int](2, Ures[Int]() )))
val intList2: Nemures[Int] = Nemures(1,Nemures(4,Nemures(2,Ures())))
val stringList: Nemures[String] = Nemures("dinnye", Nemures("szilva", Nemures("narancs", Ures())))
println( intList.filter { _%2 == 1 } )

Itt tehát azt mondjuk, hogy a $\mathrm{Lista}$ osztályunk kap egy $[T]$ típusparamétert, ami bármi lehet: $\mathrm{Int}$, $\mathrm{String}$, $\mathrm{Boolean}$, sőt akár $\mathrm{Lista}[\mathrm{Int}]$ is (ekkor int listák listáját tároljuk), és ezt a $T$ paramétert az osztály belsejében teljesen legális módon, mint típust használhatjuk, ahogy a fenti kód is mutatja. Létrehozáskor pl. eljárhatunk úgy is, ahogy a kód alsó részén felépítünk egy $\mathrm{Int}$ és egy $\mathrm{String}$ listát.

A $\mathrm{map}$ azért elsőre még mindig úgy tűnhet, mintha külön-külön kéne kezelnünk a $T\Rightarrow\mathrm{Int}$, $T\Rightarrow\mathrm{String}$, $T\Rightarrow\mathrm{Boolean}$ függvényeket (meg az összes többit, ami előjöhet) és ezek mindegyikére a megfelelő típusú kimeneti listát produkáltatni:

trait Lista[T] {
  def filter(p: T=>Boolean): Lista[T]
  def mapInt(f: T=>Int): Lista[Int]
  def mapBoolean(f: T=>Boolean): Lista[Boolean]
  def mapString(f: T=>String): Lista[String]
}
case class Ures[T]() extends Lista[T] {
  override def filter(p: T=>Boolean) = Ures()
  override def mapInt(f: T=>Int) = Ures()
  override def mapBoolean(f: T=>Boolean) = Ures()
  override def mapString(f: T=>String) = Ures()
}
case class Nemures[T](head: T, tail: Lista[T]) extends Lista[T] {
  override def filter(p: T=>Boolean) = if (p(head)) Nemures(head, tail.filter(p)) else tail.filter(p)
  override def mapInt(f: T=>Int) = Nemures(f(head), tail.mapInt(f))
  override def mapBoolean(f: T=>Boolean) = Nemures(f(head), tail.mapBoolean(f))
  override def mapString(f: T=>String) = Nemures(f(head), tail.mapString(f))
}
val intList = Nemures[Int]( 1, Nemures[Int](4, Nemures[Int](2, Ures[Int]() )))
println( intList.filter { _%2 == 1 } )
println( intList.mapString { _.toBinaryString }) //prints Nemures(1,Nemures(100,Nemures(10,Ures())))

(egyébként ha mindegyiket csak $\mathrm{map}$nak neveznénk el, akkor nem fordul le, mert a JVM nem tud különbséget tenni a különböző szignatúrájú függvények mint paraméterek között). Láthatjuk, hogy itt is mennyivel jobb lenne, ha a bejövő paraméterben az a $\mathrm{Boolean}$, $\mathrm{Int}$, $\mathrm{String}$ valami (másik, mert nem feltétlenül ugyanaz, mint a $T$ nevű paraméter) típus is parametrizálható is lenne - és az!

trait Lista[T] {
  def filter(p: T=>Boolean): Lista[T]
  def map[U](f: T=>U): Lista[U]
}
case class Ures[T]() extends Lista[T] {
  override def filter(p: T=>Boolean) = Ures()
  override def map[U](f: T=>U) = Ures()
}
case class Nemures[T](head: T, tail: Lista[T]) extends Lista[T] {
  override def filter(p: T=>Boolean) = if (p(head)) Nemures(head, tail.filter(p)) else tail.filter(p)
  override def map[U](f: T=>U) = Nemures(f(head), tail.map(f))
}
val intList = Nemures[Int]( 1, Nemures[Int](4, Nemures[Int](2, Ures[Int]() )))
println( intList.filter { _%2 == 1 } )
println( intList.map { _.toBinaryString }) //prints Nemures(1,Nemures(100,Nemures(10,Ures())))

Egyébként a $T$ és az $U$ csak nevezéktan: általában az első típusparaméter "neve" $T$, a másodiké $U$ szokott lenni, de ettől számos eltérés van, ha a paramétereknek van valami konkrétabb jelentésük. Azt láthatjuk tehát, hogy függvényeket is lehet generic paraméterekkel ellátni, a példában a $\mathrm{map}$ metódus lett generic egy $U$ nevű típusparaméterrel, a $T$-re parametrizált típusú listánkon belül, ezért lett a paraméterének a szignatúrája $f:T\Rightarrow U$ és a kimenete $\mathrm{Lista}[U]$ típusú. De ettől eltekintve az $U$ típust, miután generic paraméternek deklaráltuk, ugyanúgy használhatunk a metódus szignatúrájában és törzsében, mint bármilyen másik "létező" típust.
Egy szépséghibája azért még mindenképp van a kódnak, amit láthatunk: object nem lehet generic, ezért az üres lista már case class lett, és emiatt ki kell rakjuk utána a zárójeleket is. (Ezt még később megoldjuk, amikor a kovariáns genericeket meg a $\mathrm{Nothing}$ típust nézzük.)

12 - map és filter

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 $\mathrm{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. a $(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
}
case class Nemures(head: Int, tail: IntList) {
  override def szorzasKettovel = Nemures(head * 2, tail.szorzasKettovel)
}

de (remélhetőleg) azt érzi ilyenkor az ember valahol belül, hogy ez így nem lesz jó, mindenkinek, aki valamikor később használni fogja az $\mathrm{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)
}

és 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
}
case object Ures extends IntList {
  override def map(f: Int=>Int) = Ures
}
case class Nemures(head: Int, tail: IntList) extends IntList {
  override def map(f: Int=>Int) = Nemures(f(head), tail.map(f))
}
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)))

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. Névtelen, lambda-függvényként átadni pl. úgy lehet, ahogy a fenti példában látjuk. Ha ugyanazt a transzformációt használjuk sok helyen a kódban, akkor persze érdemes kimenteni egy (mondjuk) $\mathrm{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.

Egy másik gyakran használt listaművelet a $\mathrm{filter}$: pl. ha az $\mathrm{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
}

és 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 $\mathrm{Int}$, $\mathrm{Boolean}$ba 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)
}
val list = Nemures(1,Nemures(4,Nemures(2,Ures)))
println(list.filter { _%2==1 }) //prints Nemures(1,Ures)

Már csak az üthet szöget a fejünkbe, hogy mi van, ha nem csak $\mathrm{Int}$eket tároló listákkal akarunk dolgozni, ez a következő poszt témája

folytköv

11 - class member függvények

$\mathrm{class}$on, $\mathrm{object}$en belül is lehet függvényeket vagy értékeket is deklarálni, pl:

case class Vektor(x: Double, y: Double) {
  def length = Math.sqrt(this.x * this.x + this.y * this.y)
}
val v = Vektor(1.0,2.0)
println(v.length)  //prints 2.23606797749979

Mi történik ennél a hívásnál?

• Ha a $C$ osztályban egy $f(x_1:T_1,\ldots,x_n:T_n)$ tagmetódusát hívjuk az $a$ példányon (amit pl. $\mathrm{val}~a~=\ldots$ deklaráltunk), akkor \[a.f(a_1,\ldots,a_n)\] hívjuk a függvényt, ahol az $a_i$ argumentumok $T_i$ típusúak (most nincs argumentum, de nemsokára lesz)
• a függvény törzsében az $x_i$-k helyére az $a_i$ értékek kerülnek
• és a $\mathrm{this}$ kulcsszó helyére pedig maga az $a$ érték.

(matematikailag legalábbis ez történik, ha pure funkcionális stílusban programozunk.)

Pl. a fenti $\mathrm{v.length}$ hívásnál:

\[\begin{align*}\mathrm{v.length}&\triangleright \mathrm{Vektor}(1.0,2.0)\mathrm{.length}\\&\triangleright \mathrm{Math.sqrt}(\mathrm{Vektor}(1.0,2.0).x\cdot \mathrm{Vektor}(1.0,2.0).x+\mathrm{Vektor}(1.0,2.0).y\cdot\mathrm{Vektor}(1.0,2.0).y)\\&\triangleright \mathrm{Math.sqrt}(1.0\cdot 1.0+2.0\cdot 0.2)\\&\triangleright\mathrm{Math.sqrt}(5.0)\\&\triangleright 2.2360679\ldots\end{align*}\]

Az előző kód példája egy paraméter nélküli metódus volt. Ilyenkor a Scala fordító elfogadja zárójelekkel is $\mathrm{def~length}() = \ldots$ és mint fent, anélkül is. A konvenció az, hogy ilyenkor azokat a metódusokat írjuk zárójel nélkül, melyeknek nincs mellékhatásuk. A fenti $\mathrm{length}$ például ilyen, csak az adattagokból számít ki valamit. Ha megnézzük a hívást, $\textrm{v.length}$, szemre akár egy $\mathrm{val}$ member adatmező is lehetne. És tényleg:

case class Vektor(x: Double, y: Double) {
  def length_def = Math.sqrt(this.x * this.x + this.y * this.y)
  val length_val = Math.sqrt(this.x * this.x + this.y * this.y)
  lazy val length_lazy_val = Math.sqrt(this.x * this.x + this.y * this.y)
}
val v = Vektor(1.0,2.0)
println(v.length_def)  //prints 2.23606797749979
println(v.length_val)  //prints 2.23606797749979
println(v.length_lazy_val)  //prints 2.23606797749979

Nem csak a már korábban látott $\mathrm{val}$ és $\mathrm{def}$, hanem a $\mathrm{lazy~val}$ is opció. A különbségek köztük:

• a  $\mathrm{val}$ értéke az objektum létrehozásakor (ez a $\mathrm{val}~v=\mathrm{Vektor(1.0,2.0)}$ értékadás jobb oldali kifejezésének kiértékelésekor történik) kiszámítódik, ez az érték bekerül plusz egy adattagba, innentől kezdve ezt adjuk vissza.
• a $\mathrm{def}$ értéke minden egyes lekérdezéskor újra és újra kiértékelődik a definíciójának megfelelően, viszont nem foglalódik neki plusz adattag objektumpéldányonként.
• a $\mathrm{lazy~val}$nak foglalódik egy plusz adattag, de létrehozáskor még nem értékelődik ki, csak az első lekérdezéskor. Ekkor az érték bekerül az adattagba és onnantól kezdve nem számolódik újra.

Tehát: a $\mathrm{val}$ok kicsit több helyet foglalnak, a $\mathrm{val}$ mindenképp kiszámolja létrehozáskor az értékét, a $\mathrm{def}$ lekérdezésenként tovább tart, mire megjön az eredmény. A $\mathrm{lazy~val}$ sem mindig jobb választás, mint a $\mathrm{val}$, mert annak is van plusz költsége (adattagban is,  és a $\mathrm{val}$ lekérdezéseként is), hogy minden lekérdezéskor fut egy check, hogy ki van-e már számolva ez az érték. Ezt minden esetben a programozó kell mérlegelje, hogy a három lehetőség közül melyik lenne a legjobb - de a jó hír, hogy ha később mégiscsak váltani lenne jobb és átírja az osztályban az egyik kulcsszót a másikra, akkor nem töri el a hívó kódokat, mert számukra teljesen transzparens, hogy ez most épp melyik a három közül.

Ennek megfelelően ennek a kódnak:

case class Vektor(x: Double, y: Double) {
  def length_def = { println("def"); Math.sqrt(this.x * this.x + this.y * this.y) }
  val length_val = { println("val"); Math.sqrt(this.x * this.x + this.y * this.y) }
  lazy val length_lazy_val = { println("lazy_val"); Math.sqrt(this.x * this.x + this.y * this.y) }
}

val v = Vektor(1.0,2.0)
println("start")
v.length_def
v.length_val
v.length_lazy_val
v.length_def
v.length_val
v.length_lazy_val
v.length_def
v.length_val
v.length_lazy_val

a kimenete:

val
start
def
lazy_val
def
def

(Figyeljük meg a debug printlnt: így, hogy két kifejezés van egymás után, a másodiknak az értéke lesz az érték, az elsőt eldobjuk - ami úgyis $\mathrm{Unit}$, tehát $\mathrm{()}$ -, ez is egy módja a debugolásnak, de fogunk azért látni jobbat is.

Nem csak classba vagy objectbe, de traitbe is írhatunk defet vagy valt (lazy valt nem). Ha például szeretnénk az $\mathrm{IntList}$ traitünket felruházni egy $\mathrm{sum}$ függvénnyel, ami visszaadja az elemei összegét:

trait IntList {
  def sum: Int
}
case object Empty extends IntList {
  override def sum = 0
}
case class Nonempty extends IntList {
  override def sum = head + tail.sum
}
//így használjuk
val list = Nonempty(3, Nonempty(4, Nonempty(7, Empty)))
println(list.sum) // prints 14

Világos, hogy ahhoz, hogy egy listára, amiről annyit tudunk, hogy $\mathrm{IntList}$ a típusa, hívhassuk a $\mathrm{sum}$ függvényt, és ez leforduljon, tényleg kellhet az, hogy már eleve az $\mathrm{IntList}$ traitben meglegyen a függvény deklarációja. Típust is kell adjunk neki, de definíciót nem tudunk adni ezen a ponton - szerencsére nem is kell, traitekben megengedett dolog csak deklarálni, de nem definiálni a függvényt.
A case objectben és a case classban viszont, ha akarunk is belőlük példányt létrehozni, minden létező metódusnak kell már legyen definíciója - meg kell adjuk a $\mathrm{sum}$ függvényt mindkét esetben. Célszerű ilyenkor a def elé beírni az $\mathrm{override}$ kulcsszót is: ez a kulcsszó azt jelzi a fordítónak, hogy legyen szíves leellenőrizni, hogy ugye volt már egy pont ilyen nevű és szignatúrájú metódus feljebb a hierarchiában (az $\mathrm{extends}$eken keresztül) és ha nem, akkor dobjon hibát. Ezzel magunkat védjük: egyrészt ha elgépeljük a fentebbről örökölt (inherited) metódus nevét, akkor erre hamar fény derül, másrészt ha majd mások olvassák a kódunkat, ebből ránézésre látják majd ő is, hogy ebből a metódusból van följebb is másmilyen.

Persze nem csak paraméter nélküli metódust lehet létrehozni:

case class Vektor(x: Double, y: Double) {
  def plus(that: Vektor) = Vektor(this.x+that.x, this.y+that.y)
}
val u = Vektor(1.0, 2.0)
val v = Vektor(3.0, 4.0)
println(u.plus(v)) //prints Vektor(4.0,6.0)

Itt tehát az történik, hogy a $\mathrm{Vektor}$ osztályunknak (amihez korábban az osztályon kívül deklaráltunk egy összeadó függvényt és kb $\mathrm{add(v1: Vektor, v2: Vektor): Vektor}$ volt a fejléce, így is hívtuk meg) belülre deklarálunk egy összeadó metódust, aki így már csak egy további vektort vár, hiszen a bal oldali vektor az lesz, akin hívjuk, aki behelyettesítődik a $\mathrm{this}$ helyére. (Egyébként Scalában bevett konvenciónak számít, hogy ha egy osztálynak egy függvénye egyváltozós, és ugyanannak az osztálynak várja egy másik példányát, akkor ezt a formális paramétert $\mathrm{that}$nak nevezik el. Nem kötelező, a $\mathrm{that}$ nem kulcsszó, csak szokás.) Ez már talán eggyel kulturáltabban néz ki, hogy az $\mathrm{add}$ függvény a két vektor között van, mintha tényleg pl egy bináris operátor lenne...
...de bizony ezt lehet hívni így is

println( u plus(v) )

(a pont sok esetben elhagyható, ennek a konvencióiról azért még majd írok, van, aki szerint olvashatóbb a kód pontokkal, van, aki szerint nem; szerintem ha hosszú chainelés van, akkor külön sorba érdemes írni a lánc elemeit és ekkor kell is kirakni a pontot, ha meg rövid, én nem szoktam kirakni általában)
..sőt lehet hívni így is

println( u plus v )

egyváltozós member function argumentuma körül a kerek zárójel is legtöbbször elhagyható (olyankor lehet belőle értelmezési zavar, ha pl. tovább folytatjuk a kifejezést egy ponttal és pont egy olyan függvényt, mondjuk $\mathrm{toString}$et hívunk rajta, ami van az argumentumnak is és az eredménynek is).
ez így már majdnem annyira kényelmesen néz ki, mint egy rendes, infix módon írt összeadás.
És hát why not?

case class Vektor(x: Double, y: Double) {
  def +(that: Vektor) = Vektor(this.x+that.x, this.y+that.y)
}
val u = Vektor(1.0, 2.0)
val v = Vektor(3.0, 4.0)
println( u + v ) //prints Vektor(4.0,6.0)

Scalában nagyon, nagyon sok minden elmegy metódusnévnek, itt például a metódus neve az lett, hogy $\mathrm{+}$. És így már két vektor összeadása úgy is néz ki, mint két $\mathrm{Int}$ összeadása, egy nagyon természetes szintaxist ad a függvényhívásnak, könnyen olvashatót programozó számára.
Nem véletlen egyébként a hasonlóság: a $2+3$-at úgy is írhatjuk, hogy $2.+(3)$, mert a $+$ jel ebben az esetben az $\mathrm{Int}$ osztály (azaz majdnem az $\mathrm{Int}$ osztály but still) egyik tagfüggvényének a neve. Persze ettől még primitív típusra fog lefordulni, hatékony lesz, csak forráskódi szinten, kinézetre kezelődik minden úgy, mintha objektum lenne, ideértve a "built-in" operátorokat is.
Legközelebb nézünk néhány standard tagfüggvényt, fókuszálva a $\mathrm{List}$ osztályra.

folytköv

10 - referenciák, case object

Scalában minden összetett típus (az $\mathrm{Int}$ , $\mathrm{Double}$, $\mathrm{Boolean}$, $\mathrm{Long}$ egyszerű típusok, ezekből a Java primitív típusai készülnek; de minden más típus) létrehozáskor a heap memóriában, dinamikusan jön létre. Vegyük például a $\mathrm{Pont}$ típust még egyszer:

case class Pont(x: Int, y: Int)

val p = Pont(2, 3)
val q = p

Ennek a kódnak a tényleges viselkedéséhez legközelebb álló C kód a következő:

typedef struct {
  int x;
  int y;
} Pont;

Pont *p = (Pont*)malloc(sizeof(Pont));
p->x = 2;
p->y = 3;
Pont *q = p;

Vagyis, amikor egy $\mathrm{Pont(2,3)}$ hívást intézünk, akkor dinamikusan, a heap memóriában lefoglalódik egy új memóriaterület, a két mezőnek megfelelő érték beáll a $2$-re ill. $3$-ra, majd ennek az újonnan létrehozott és tartalommal feltöltött memóriaterületnek végső soron a címe kerül a $p$ értékbe. 

Ezek után a $q=p$ értékadás hatására ez a cím másolódik át $q$-ba, így a két érték egy-egy "pointert" tárol, ami ugyanarra a memóriaterületre mutat.

(attól ne tartsunk, hogy nincs memória felszabadítás: a JVM mentalitása az, hogy nincs külön memória-felszabadító függvény, mint C-ben a $\mathrm{free}$, hanem a JVM mellett fut egy garbage collector, aki ha észreveszi, hogy egy memóriaterületre már nem mutat senki, felszabadítja automatikusan.)
Teljesen hasonlóan, a $\mathrm{Lista}$ case classunk is leginkább valami efféle lehetne C-ben:

typedef struct {
  int type; //0 üres, 1 nemüres
  union {
    struct UresLista *uresLista;
    struct NemuresLista *nemuresLista;
  };
} Lista;

typedef struct UresLista{
} UresLista;

typedef struct NemuresLista{
  int head;
  Lista *tail;
} NemuresLista;

// ures: egy UresLista
Lista *ures = (Lista*)malloc(sizeof(Lista));
ures->type = 0;
ures->uresLista = (UresLista*)malloc(sizeof(UresLista));

// egyelemu: NemuresLista( 3, ures )
Lista *egyelemu = (Lista*)malloc(sizeof(Lista));
egyelemu->type = 1;
egyelemu->nemuresLista = (NemuresLista*)malloc(sizeof(NemuresLista));
egyelemu->nemuresLista->head = 3;
egyelemu->nemuresLista->tail = ures;

Még egyszer: amit csak látunk és nem "primitív" típus, az mind valójában "referencia" (a különbség referencia és pointer között: a referencia nem $\mathrm{null}$, mindig egy valid objektumra mutat, nincs referencia-aritmetika, azaz nem tudjuk "eltolni" mint egy pointert, hogy egy tömbben "arrébb" indexeljünk, és szintaktikusan úgy kezeljük a referenciát, mintha egy tényleges objektum lenne - pl. ponttal és nem nyíllal hivatkozzuk a mezőit).
Ez azt is jelenti, hogy pl. egy Lista konstruálásakor valójában konstans idő alatt készül az új lista, mert nem másoljuk a farkát, csak elrakjuk a címét egy mezőbe.
Továbbá azt is jelenti, hogy az $==$ operátor először is a két oldalán lévő referenciák címét hasonlítja össze, és ha azok egyenlőek, akkor máris le tudja jelenteni, hogy $\mathrm{true}$; ha meg nem, akkor végignézi az adatmezők egyeztetését.
Mi a helyzet tehát akkor az üres listával:

case class UresLista() extends Lista

val list = UresLista()
val egyelemu = NemuresLista(5, UresLista())

Ahányszor csak létrehozunk egy $\mathrm{UresLista}$ értéket, mindig egy új rész foglalódik le neki a memóriában, ennek a címét megkapja az adott érték. Amikor meg $==$-t tesztelünk rá, és két külön helyen lévő "példányát" nézzük, hogy egyenlőek-e (azok lesznek, hiszen adattag nincs), akkor eltart egy darabig, mire rájön a JVM, hogy ezek nem ugyanazon a címen vannak, de ugyanolyan típusúak, és minden mezejük megegyezik.

Mindezt megspórolhatjuk, ha case class helyett $\mathrm{case~object}$ként deklaráljuk az üres listát:

case object UresLista extends Lista

val list = UresLista //nincs zárójel!
val egyelemu = NemuresLista(5, UresLista) //itt sincs

Egy case object lényegében egy olyan típus, aminek egyetlenegy elemű az értéktartománya (tkp ez igaz volt az $\mathrm{UresLista}$ra mint $\mathrm{case~class}$ra is, csak több helyen is létrehozhattuk a memóriában ezt az egy értéket), és ez az egy érték a program futása legelején létrejön egyetlen helyen a memóriában, és innentől kezdve minden értékadásnál ezt az egy referenciát kapja minden ilyen típusú érték. Ez többek közt azért jó, mert csak egyszer foglal helyet a memóriában és gyorsabb rá az $==$ ellenőrzés. Innen kezdve viszont nincs neki argumentumlistája (ha lenne, nem hozhatnánk létre egyetlen objectként), a zárójelek kitevése fordítási hibát is okoz.
Lényeg: ha egy típus valójában az $1$ típus, akkor azt $\mathrm{case~object}$ként hozzuk létre; ha extendelnie kell egy $\mathrm{trait}$et, azt is tudja probléma nélkül.
Az int listánk mostani implementációja tehát:

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

mintailleszteni pedig szintén tudunk case objectre, nem kell és nem is szabad kitennünk a zárójeleket, de egyébként ugyanúgy, mint korábban:

def find(list: Lista, value: Int): Boolean = list match {
  case UresLista => false
  case NemuresLista(`value`, _) => true
  case NemuresLista(_, tail) => find(tail, value)
}

Itt láthatunk egy eddig nem tárgyalt mintaillesztést: ha backtick-ek (`) közé rakunk egy azonosítót, akkor az nem egy új azonosító lesz, ami mindenre illeszkedik és behelyettesítődik jobb oldalra, hanem egy már létező azonosítóhoz tartozó érték kerül ide. Így ez a függvény azt adja vissza (farokrekurzív módon), hogy a paraméterként megadott listában előfordul-e a paraméterként megadott érték. Ha igen, akkor a második case illeszkedik akkor, amikor ahhoz a részlistához érünk, akinek a fejeleme pont a keresett elem (ekkor már mindegy, hogy mi a farok, ezért ott az underscore). Ha meg nem, akkor keresünk tovább a lista farkában (ekkor meg már nem számít, hogy mi is a fejelem; ha a harmadik case alternatívához érünk, akkor már tudjuk, hogy nem a keresett érték az). Vagyis, egy $\mathrm{case~NemuresLista}(`value`,\_)$ case egyenértékű egy $\mathrm{case~NemuresLista}(v,\_)~\mathrm{if}~v==value$ if guardos case-el.

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 :)

08 - lista, algebrai adattípus

Most, hogy van összeg típusunk és szorzat típusunk, az alaptípusainkból elkezdhetünk ezekkel a műveletekkel komplexebb típusokat építeni. Például, az előző posztban szereplő $\mathrm{Pont}$, $\mathrm{Haromszog}$ és $\mathrm{Kor}$ típusokat ha fel akarjuk írni ezekkel a jelekkel:

$$\begin{align*}\mathrm{Pont} &= \mathrm{Int}\times\mathrm{Int}\\\mathrm{Kor} &= \mathrm{Pont}\times\mathrm{Double}\\\mathrm{Haromszog} &= \mathrm{Pont}\times\mathrm{Pont}\times\mathrm{Pont}\\\mathrm{Shape} &= \mathrm{Kor}+\mathrm{Haromszog}\end{align*}$$

Mondhatjuk úgy, hogy minden típust vagy összeg típusként definiálunk (és akkor ő más típusok összegeként áll elő), vagy szorzat típusként (és akkor ő más típusok szorzataként áll elő).

Ez így elég egyértelműnek látszik, és persze sok mindent így egymásra építve is össze tudunk rakni, de igazán érdekessé akkor válik, ha az egyenletek jobboldalán akár "egymástól való függőséget" is kialakíthatunk, pl. így:

$$\begin{align*}\mathrm{Lista} &= \mathrm{UresLista}+\mathrm{NemuresLista}\\ \mathrm{UresLista} &= 1\\\mathrm{NemuresLista} &= \mathrm{Int}\times\mathrm{Lista}\end{align*}$$

Az első kérdés, hogy mi az az $1$ ott az üres lista jobb oldalán? Ez egy szorzat típus, mégpedig az üres szorzaté. Ha egy szorzat típusnak két mezője van (mint a $\mathrm{Pont}$), akkor ő ennek a két mező típusának a szorzata, ha három (mint a $\mathrm{Haromszog}$), akkor ennek a háromnak - és ha nincs neki mezője egyáltalán, akkor ő nulla darab típusnak a szorzata. Ezt a szorzat típust jelöljük $1$-gyel, egy Scala implementációja lehet pl. eddigi tudásunk szerint a következő:

case class UresLista()

//működik is:
val ures = UresLista()

A többi formailagrendben van: a $\mathrm{Lista}$ az egy összeg típus, a $\mathrm{NemuresLista}$ pedig egy szorzat típus. OK, de ezek egymásra hivatkoznak! Mit jelent ez? Először is nézzük meg, hogy ezt ha Scalában lekódoljuk az eddigi ismereteink alapján, akkor vajon fordul-e:

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

Lefordul, igen, sőt értékeket is tudunk definiálni:

val ures = UresLista()
val egyelemu = NemuresLista(7, ures)
val ketelemu = NemuresLista(2, egyelemu)
val haromelemu = NemuresLista(1, ketelemu)
val masikharmas = NemuresLista(4, ketelemu)
println(haromelemu) //NemuresLista(1,NemuresLista(2,NemuresLista(7,UresLista())))

Ezek szerint hogy mi is lehet egy $\mathrm{Lista}$? az $\mathrm{UresLista()}$ érték az $\mathrm{UresLista}$ típusnak egy értéke, a $\mathrm{Lista}$ meg egy összeg típus, tehát az értéktartományában benne van minden $\mathrm{UresLista}$ is (mind az egy),  ezért az $\mathrm{UresLista}()$ az egy lista. Ha viszont az, akkor a $\mathrm{NemuresLista}(7,\mathrm{UresLista}())$ egy $\mathrm{NemuresLista}$ , hiszen az első argumentum egy $\mathrm{Int}$, a második meg egy $\mathrm{Lista}$. De ha ő $\mathrm{NemuresLista}$, akkor $\mathrm{Lista}$ is, mert az utóbbi egy összeg típus, amiben a $\mathrm{NemuresLista}$ is benne van. Hasonlóképp, eszerint a $\mathrm{NemuresLista}(2,\mathrm{NemuresLista}(7,\mathrm{UresLista}()))$  is nemüres lista, eszerint lista is, és addig pakolhatunk további $\mathrm{Int}$eket a meglévők elé, ameddig csak akarunk (feltéve, hogy megelégszünk véges sok elemmel). Amit implementáltunk most: $\mathrm{Int}$ elemeknek egy egy irányba láncolt listáját: a lista vagy üres, vagy nem, ha nemüres, akkor van neki egy első eleme, avagy feje, $\mathrm{head}$, és van neki egy további része, avagy farka, $\mathrm{tail}$, ami szintén lista. Jelben egy listát zárójelek közé írt elem-felsorolással fogunk felírni, pl. a kód $\mathrm{masikharmas}$ listáját így: $(4,2,7)$, az üres listát pedig így: $()$. Az egyeleműt így: $(7)$. A lista fejeleme a bal oldalán szerepel.

Mindenesetre, algebrai adattípusnak nevezünk egy típust, ha definiálható a fentihez hasonló módon: ha fel tudjuk írni típusok egy rendszerét úgy, hogy minden típus vagy más típusok összege, vagy más típusok szorzata, a jobb oldalon a rendszerben deklarált típusokat és alaptípusokat használhatunk, melynek egyik eleme (most a $\mathrm{Lista}$) a kérdéses típus, akkor ez egy algebrai adattípus. Az értéktartományát pedig így határozhatjuk meg általános esetben is, mint most: kiindulva a legkisebb elemekből, iteratívan bővítve (ez oda-vissza hivatkozott típusoknál, ha van "alsó" építőkocka, végtelen iteráció lesz, de nem baj, el tudjuk képzelni, hogy ez mit jelent, csak azt, hogy "bármekkora lehet"). Egyébként ezt úgy is mondják, hogy az értéktartomány a "legkisebb fixpontja" ennek az "egyenletrendszernek".

Mivel pedig case class konstrukció, az egyenlőség vizsgálatot is megkapjuk hozzá:

println(haromelemu == masikharmas) //false
println(haromelemu == NemuresLista(1, NemuresLista(2, NemuresLista(7, UresLista())))) //true

tehát továbbra is, az $==$ tartalom szerint hasonlít össze, ha a típus is megegyezik és a mezők tartalma is (rekurzívan), akkor egyenlő a két objektum, egyébként pedig nem azok. Van hozzá továbbá kiíratás is, ugyanúgy, mint korábban a case classok esetében is volt.

A pure funkcionális programozás egyik alap módszere, hogy algebrai adattípusokon végzünk mintaillesztés alapján rekurzívan , lehetőleg persze farokrekurzívan, műveleteket. A következő posztban erre fogunk látni példákat, match kifejezésekkel.

folytköv

07 - trait, összeg típus

Mondjuk, hogy van egy geometriai formákkal dolgozó appunk. Van benne pont, háromszög (ami három pontból tevődik össze), kör (ami egy középpontból és egy sugárból), pl. így:

case class Pont(x: Int, y: Int)

case class Haromszog(p: Pont, q: Pont, r: Pont)
case class Kor(p: Pont, r: Double)

és szeretnénk valami olyan típust (pl. mert valami kollekcióba, listába, whatever, akarunk gyűjteni geometriai formákat (egyszerűség kedvéért most a pontot ne, csak köröket meg háromszögeket akarunk uniform módon kezelni) és ne kelljen ehhez két különböző típusú (mondjuk) tömböt deklaráljunk.
Vagyis: van egy $T_1$ típusunk, aminek az értéktartománya a $D_1$ halmaz, van egy $T_2$ típusunk, aminek az értéktartománya pedig a $D_2$ halmaz és ezekből szeretnénk készíteni egy olyan $T$ típust, aminek az értéktartománya a $D_1\uplus D_2$ halmaz, a két értéktartomány diszjunkt uniója. Ez azt jelenti, hogy még ha van is átfedés a két halmaz közt, akkor is minden elem "eredeti típus infóval" kerüljön bele, azaz ha van a két halmaznak közös eleme, akkor kétszer, egyszer $T_1$ típusúként, egyszer pedig $T_2$ típusúként. Pl. ha $T_1=\mathrm{Int}$ és $T_2=\mathrm{Double}$, akkor a $T$ típus értéktartományában szerepeljen a double $0$ és az int $0$ is külön-külön. Ha egy ilyen $T$ típust hozunk létre ezzel az értéktartománnyal, akkor azt úgy mondjuk, hogy a $T$ a $T_1$ és $T_2$ típusok összege, jelben $T=T_1+T_2$.

Most pont ezt szeretnénk: van egy $\mathrm{Haromszog}$ és egy $\mathrm{Kor}$ típusunk, és valami olyan típust szeretnénk készíteni, amibe bármelyiket rakhatjuk.

Ennek C-ben egy implementációja például így festhet:

typedef struct { int x; int y; } Pont;
typedef struct { Pont p; Pont q; Pont r; } Haromszog;
typedef struct { Pont p; double r; } Kor;

typedef struct {
  int type; // 0 -- haromszog 1 -- kor
  union{
    Haromszog haromszog;
    Kor kor;
  };
} Shape;

vagyis: egy olyan structot készítünk, aminek a $\mathrm{type}$ mezője tárolja, hogy most épp kör vagy háromszög amire tulajdonképp mutatunk, és ennek függvényében van vagy egy $\mathrm{Kor}$, vagy egy $\mathrm{Haromszog}$ adatmezőnk, de mivel egyszerre csak az egyik lehet valid, ezért őket unionba tesszük. Egy példa használata ennek az új típusnak:

Pont p; p.x = 1; p.y = 2;
Haromszog h; h.p = p; h.q = p; h.r = p;
Kor k; k.p = p; k.r = 1.0;
Shape shape;
shape.type = 0;
shape.haromszog = h;
  
printf( "Shape is: %s\n", shape.type ? "circle" : "triangle" );
switch( shape.type )
{
    case 0:
        printf( "Nodes: (%d,%d), (%d,%d), (%d,%d)\n",
            shape.haromszog.p.x,
            shape.haromszog.p.y,
            shape.haromszog.q.x,
            shape.haromszog.q.y,
            shape.haromszog.r.x,
            shape.haromszog.r.y
        ); break;
    case 1:
        printf( "Center: (%d,%d), radius: %lf\n",
            shape.kor.p.x,
            shape.kor.p.y,
            shape.kor.r
        );break;
    }

Világos, hogy mi történik: amikor értéket adunk egy $\mathrm{Shape}$ változónak, akkor be kell állítsuk a típusát is és a union megfelelő mezőjét állítjuk az értékre; amikor meg dolgozunk egy $\mathrm{Shape}$ változóval, akkor legelőször is le kell switchelnünk, hogy épp mi is ez, és ezután típusfüggően dolgozhatunk vele. És létrehozhatunk egy $\mathrm{Shape}$ tömböt, amibe aztán pakolhatunk háromszögeket vagy köröket vegyesen ízlés szerint, ezzel megvalósítjuk az absztrakt $\mathrm{Shape}=\mathrm{Kor}+\mathrm{Haromszog}$ adattípust.

Scalában ugyenezt elérhetjük pl. így:

case class Pont(x: Int, y: Int)

trait Shape
case class Haromszog(p: Pont, q: Pont, r: Pont) extends Shape
case class Kor(p: Pont, r: Double) extends Shape

val p = Pont(1,2)
val h = Haromszog(p,p,p)
val k = Kor(p,1.0)

val shape: Shape = h

shape match {
  case Haromszog(p,q,r) => println("Shape is: triangle\nNodes: " + p + "," + q + "," + r)
  case Kor(p,r) => println("Shape is: circle\nCenter: " + p + ", radius: " + r)
}

Ebből a $\mathrm{match}$ kifejezés egy külön poszt lesz, most a $\mathrm{trait}$re fókuszálunk a típusdeklarációban. A $\mathrm{Pont}$, $\mathrm{Haromszog}$, $\mathrm{Kor}$ típusok definíciója ugyanaz, mint az előbb, azzal, hogy utóbbi kettő kapott egy $\mathrm{extends~Shape}$-et a végére és a definíciókat megelőzi egy $\mathrm{trait~Shape}$ sor. Ez utóbbira egyelőre tekinthetünk úgy, mint egy típusdefinícióra: ha egy típust a $\mathrm{trait}$ kulcsszóval vezetünk be, akkor az még csak a nevét vezeti be a típusnak, egyelőre üres értéktartománnyal. Minden további típus, ami $\mathrm{extend}$eli ezt a traitet, pedig hozzácsapja a saját értéktartományát a traitéhez, diszjunkt unió formában - mivel most két típusunk volt, aki azt mondta, hogy ő $\mathrm{extends~Shape}$, ezért most a $\mathrm{Shape}$ típus a $\mathrm{Haromszog}$ és a $\mathrm{Kor}$ típusok összege lesz. Láthatunk példát értékadásra is, a $\mathrm{val~shape:Shape~=~h}$ értékdeklarálásnál azért írtam ki explicit a típust, mert különben a Scala fordító (mivel a $h$ az egy háromszög) háromszögnek következteti ki a $\mathrm{shape}$ érték típusát.

A kód végén pedig azt láthatjuk, hogy ha van egy, a diszjunkt összegbe tartozó értékünk, akkor hogyan tudjuk meg róla azt, hogy éppen melyik típusnak az adattartományába valósi; a match kifejezésekről egy későbbi posztban többet fogunk tudni.

A trait egy ennél sokkal sokoldalúbb konstrukció lesz - most egyelőre csak az a lényeges tulajdonsága, hogy ezzel a kulcsszóval tudunk összeg típust létrehozni. Az összeg és szorzat típusok kombinációjával pedig tudunk építeni...

folytköv

06 - case class, szorzat típus

Progalapból is volt több módszer arra, hogy "egybe tartozó adatokat" összepakoljunk egyetlen adattípusba, classic példa lehet erre mondjuk egy $\mathrm{Pont}$ típus, ami a síkon rendelkezik egy $x$ és egy $y$ koordinátával. Az egyszerűség kedvéért most csak egész koordinátákkal foglalkozunk.

C-ben valahogy így deklarálhatunk és használhatunk egy $\mathrm{Pont}$ típust:

typedef struct {
  int x;
  int y;
} Pont;
// létrehozás
Pont p;
// mezők beállítása
p.x = 1;
p.y = 3;
// függetlenek
printf( "(%d,%d)\n", p.x, p.y ); //prints (1,3)

Tehát, az összetett adattípusnak, a structnak, itt két mezője van. Matematikailag ha egy $T_1$ típus értéktartománya a $D_1$ halmaz, a $T_2$ típusé meg a $D_2$ halmaz, akkor a $T_1\times T_2$ szorzattípusé, amit C-ben a $\mathrm{struct}$ kulcsszóval hozunk létre, a $D_1\times D_2$ direkt szorzat. Magyarán: ha pl. $T_1=\mathrm{Boolean}$, akkor $D_1=\{\mathrm{true},\mathrm{false}\}$, hiszen a bool típus értéktartományába ez a két érték tartozik; ha  $T_2=\mathrm{Int}$, akkor $D_2=\{0,1,-1,2,-2,\ldots,2^{31}-1,-2^{31}\}$, hiszen a $32$-bites előjeles int típus értéktartományába ezek az egész számok tartoznak. Akkor a $\mathrm{Boolean}\times\mathrm{Int}$ típus értéktartománya pedig a $$D_1\times D_2=\{(\mathrm{true},0),~(\mathrm{false},0),~(\mathrm{true},1),~(\mathrm{false},1),~(\mathrm{true},2),\ldots,(\mathrm{false},-2^{31})\}$$ lesz: ahány féle párt csak tudunk képezni a két típus adattartományába tartozó értékekből (sorrend számít, ha a két típus véletlenül ugyanaz), az mind reprezentálható egy $\mathrm{struct}$ban, avagy szorzat típusban.

A $\mathrm{Pont}$ tehát mint "típus", az $\mathrm{Int}\times\mathrm{Int}$ típusnak felel meg, és el van nevezve $\mathrm{Pont}$nak.

Scalában a szorzat típus létrehozására a $\mathrm{case~class}$  kulcsszavak használhatók (mindaddig, amíg a célunk annyi, hogy immutable adatmezőket csoportosítsunk szorzat típusba) így:

case class Pont(x: Int, y: Int)

val p : Pont = Pont(1, 3)
val q = Pont(2, 3)
val r = Pont(x = 2, y = 3)
val s = Pont(y = 3, x = 2)

println("p.x = " + p.x + ", p.y = " + p.y) // prints p.x = 1, p.y = 3
println(s) // prints Pont(2,3)

Tehát: a typedefnek megfelelő típusdeklaráció: $\mathrm{case~class}$, a típus neve, nyitójel, mezők felsorolása név, kettőspont, típus formában, csukójel.

Ezek után létrehozhatunk pontot pl. explicit deklarált módon vagy anélkül (mint $p$ és $q$), a $p$-nél egy olyan pontot hoztunk létre, aminek az $x$ mezőjének értéke $1$, az $y$ pedig $3$, ezt az első $\mathrm{println}$ utasításnál látható módon $p.x$ és $p.y$-ként hivatkozva érjük el, pont mint egy C-beli structnál. A $q$ esetében a fordító ki tudta következtetni, hogy $q$ típusa is $\mathrm{Pont}$ lesz. Az $r$ és $s$ értékek létrehozásánál azt figyeljük meg, hogy az érték létrehozásakor a paraméterekre név szerint is hivatkozhatunk, és ekkor nem baj, ha nem pont abban a sorrendben adjuk meg a mezőket, mint ahogy a típusdeklarációban a fejlécben szerepelnek: $r$ is és $s$ is ugyanúgy az a pont, melynek $x$ mezeje a $2$, $y$ mezeje pedig a $3$ értéket veszi fel, mint ahogy $q$ is.

A példakódban még van olyan konstrukció, amit eddig nem láttunk: az első kiíratásnál stringet adunk össze számmal. Egyelőre erről elég annyit tudnunk, hogy minden értéknek (a típusától függően) van egy olyan függvénye, ami visszaadja az értéknek egy String reprezentációját: ha pl. egy $\mathrm{Int}$ünk van, akkor ez egyszerűen az értékének a tízes számrendszerbeli alakja lesz. Amikor egy Stringhez adunk hozzá (balról vagy jobbról) bármilyen értéket, akkor ennek az értéknek (ha az nem String) ez a $\mathrm{toString}$ nevű függvénye lefut, készít egy $\mathrm{String}$et a típusnak megfelelő módon, és ezt a stringet konkatenálja össze a másik stringgel, amihez hozzáadtuk. Így áll össze az első példában a négy tag összegéből, melyből kettő string, kettő int, egyetlen string, amit aztán kiíratunk.

Egy hasonló dolog történik az utolsó kifejezésben is: $\mathrm{println}(s)$, ahol $s$ nem egy string, hanem egy $\mathrm{Pont}$ típusú érték. A $\mathrm{case~class}$ kulcsszóval deklarált típusok esetében sok minden történik "rejtett" módon, az egyik az, hogy a típushoz készül egy $\mathrm{toString}$ metódus is, és ha stringgé kell konvertálnunk egy (jelen esetben) $\mathrm{Pont}$ típusú értéket, akkor ez a metódus visszaadja a típus nevét, nyitójel, majd az összes mezőjének az értékének lekéri a $\mathrm{toString}$ függvényének az értékét, ezeket a típus deklarációjában lévő sorrend szerint felsorolja vesszővel elválasztva, csukójel.
Így lett a $\mathrm{println}(s)$ kifejezés mellékhatása egy $\mathrm{Pont}(2,3)$ string kiírása a képernyőre, mert ennek az $s$ értéknek a (futásidejű - ezt nemsokára látni fogjuk, mit jelent) típusa $\mathrm{Pont}$, ami egy case class, és $s.x=2$, $s.y=3$ voltak.

Folytassuk az előző kódot:

def addOssze(p: Pont, q: Pont) =
    Pont(p.x + q.x, p.y + q.y)

val t = addOssze(p, q) // Pont(1+2,3+3) = Pont(3,6)
println(t == Pont(3,6)) // true

Itt azt láthatjuk, hogy (természetesen) függvénynek a paramétere is, visszatérési értéke is lehet custom típus, az $\mathrm{addOssze}$ függvény pl. két pontot mint "vektort" összead, az eredmény $x$ koordinátája az $x$-ek, az $y$ az $y$-ok összege lesz és ezt az új pontot adja vissza. A típusát kikövetkeztette a fordító, hogy $\mathrm{Pont}$ lesz.
Amire viszont érdemes felfigyelni: a $t==\mathrm{Pont}(3,6)$ kifejezés értéke $\mathrm{true}$ lesz. Ez azért van, mert $\mathrm{case~class}$ok esetében az egyenlőség műveletet is automatikusan elkészíti nekünk a fordító (persze ha nem tetszik az alapértelmezett, megváltoztathatjuk, később láthatjuk, hogy hogyan), mégpedig: két $\mathrm{Pont}$ pontosan akkor lesz egyenlő, ha az $x$ mezőjük is és az $y$ mezőjük is egyenlő (most ezek $\mathrm{Int}$ek, de ha valami másmilyen összetett típusú mező lenne, akkor annak az egyenlőség műveletét is hívná rekurzívan). Ez eltérés a Java-hoz képest: ott az egyenlőség operátor alapvetően csak azt ellenőrzi, hogy a memóriában ugyanott van-e tárolva a két érték, és ehelyett ott egy $\mathrm{equals}$ metódust kell hívjunk (és meg is kell írnunk), ha "érték szerinti" egyenlőséget akarunk tesztelni. Ez a hívás (Javára átírva az egészet) pl. hamisat adna, mert az $\mathrm{addOssze}$ metódus megkapja a két pontot és létrehoz egy harmadikat valahol a heap memóriában, ezt (valójában ennek a referenciáját, erről később) adja vissza, ez kerül a $t$-be; a vele összehasonlított $\mathrm{Pont}(3,6)$ meg a heapben egy másik helyen ekkor jön létre, egy teljesen másik memóriaterületen.

Javában egyébként hogy nagyjából ugyanezt kapjuk, mint amit ezzel a $\mathrm{Pont}$ osztállyal eddig kezdtünk, kb. ezt kéne kódoljuk (meg még néhány másik metódust, amit a Scala szintén megcsinál, $\mathrm{hashCode}$ot és egy factoryt az osztályhoz:

//típusdeklaráció
class Pont{
  final int x;
  final int y;
  public Pont( int x, int y ) { this.x = x; this.y = y; }
  public String toString(){ return "Pont(" + x + "," + y + ")"; } 
  public boolean equals( Object o ) {
    if( o instanceof Pont ){
      Pont p = (Pont)o;
      return ( x == p.x )&&( y == p.y );
    }
    return false;
  }
}
//összeadás metódus, egyelőre a Pont osztályon kívül "valahol"
Pont addOssze( Pont p, Pont q ) {
  return new Pont( p.x+q.x , p.y+q.y );
}
//létrehozás, formázott kiírás
Pont p = new Pont(1,3);
Pont q = new Pont(2,3);
System.out.println( p ); //prints Pont(1,3)
//egyenlőség check
System.out.println( addOssze(p,q).equals( new Pont(3,6) ) );

Sok esetben lesz még, hogy a Scala levesz a vállunkról némi "boilerplate"-et a Javához képest. Egy későbbi posztból majd azt is megtudhatjuk, hogy a $\mathrm{case}$ plusz kulcsszó miben változtat még pontosan, egyelőre immutable szorzat típus modellezésére a case class tökéletes választás lesz.

folytköv

05 - Függvények és a Unit típus

Azért is hívják a Scalát funkcionális programozási nyelvnek (is - meg OOP is), mert a függvények "first-class citizenek" a nyelvben: igaz, hogy a legtöbb imperatív nyelvben is van rá mód, hogy függvényeket adjunk oda egy másik függvénynek argumentumként, de Scalában ez nyelvi szinten úgy támogatott, hogy nagyon egyszerű a szintaxisa.

Láttuk eddig, hogy az $\mathrm{Int}$, $\mathrm{Boolean}$, $\mathrm{String}$ stb típusok léteznek Scalában. Ha pedig $\sigma$ és $\tau$ már típusok, akkor $\sigma=>\tau$ az olyan függvények típusa, melyek $\sigma$ típusú inputot várnak és $\tau$ típusú az outputjuk. Pl. egy $\mathrm{def}~ \mathrm{strlen}(~s:\mathrm{String}):\mathrm{Int}=\ldots$ szignatúrájú függvény típusa $\mathrm{String}=>\mathrm{Int}$ (a továbbiakban a szövegben összeolvasztom nyíllá ezt a két karaktert: $\mathrm{String}\Rightarrow\mathrm{Int}$). És ilyen típusú értékeket is létrehozhatunk, vagy átadhatjuk paraméterként:

def pluszHat(n: Int) = n + 6
println(pluszHat(4)) // prints 10

val f: Int => Int = pluszHat
println(f(4)) //also prints 10

val g = pluszHat _ //inferred type
println(g(4)) //also prints 10

val h = { x: Int => x + 6 }
println(h(4)) //also prints 10

val i: Int => Int = { x => x + 6 }
println(i(4)) //also prints 10

val j: Int => Int = { _ + 6 }
println(j(4)) //also prints 10

Amit fent látunk: van egy függvényünk, az "adj hozzá hatot az inputhoz" függvény, $\mathrm{pluszHat}$ a neve, nyilván $\mathrm{Int}=>\mathrm{Int}$ típusú.

• Az $f$ értéket úgy hoztuk létre, hogy explicit deklaráltuk a típusát, majd megmondtuk, hogy ez is a $\mathrm{pluszHat}$ függvény legyen. Innentől kezdve őt is teljes jogú függvényként kezelhetjük, pl. kiértékelhetjük egy int helyen, mondjuk ezt is $4$-re, és az érték $10$ lesz, hiszen ez a függvény lényegében egy aliasa a $\mathrm{pluszHat}$ függvényünknek.
• Ötletként felmerülhet, hogy vajon a fordító ki tudja-e következtetni a típusát, ha nem adjuk meg. A $\textrm{val}~g=\mathrm{pluszHat}$ értékadás fordítási hibát dob, a fordító nem jön rá, hogy most a $\mathrm{pluszHat}$ra mint függvény értékként akarunk hivatkozni, nem pedig meghívni valami argumentummal, ezt hiányolja. (Az előbb a környezetből rájött arra, hogy $\mathrm{Int}\Rightarrow\mathrm{Int}$ értékként akarjuk kezelni.) Ezt a speciális wildcard $\_$ karakterrel oldhatjuk fel: ha $f$ egy $\sigma\Rightarrow\tau$ típusú függvény neve, akkor $f~\_$ mint kifejezés magát az $f$ függvényt jelöli és $\sigma\Rightarrow\tau$ típusú. Ezért a $\mathrm{val}~g=\mathrm{pluszHat}~\_$ értékdeklarációnál már ki tudja következtetni a fordító, hogy akkor a $g$-nek is $\mathrm{Int}\Rightarrow\mathrm{Int}$ típusú értéknek kell lennie.
• A további három érték deklarálásánál arra látunk példát, hogy anonim, avagy lambda függvényt pl. hogy adhatunk meg. Mindháromban közös, hogy $\{\}$ zárójeleken belül adjuk meg a függvényt.
• A $h$ érték esetében: explicit típusdeklarációval megadtuk, hogy van egy $x$ formális paramétere a függvénynek, ami $\mathrm{Int}$ típusú, az értéke pedig az $x+6$ kifejezés értéke lesz. (Ugyanaz, mintha $\mathrm{def}~\mathrm{sumthin}(x:\mathrm{Int})=x+6$ deklaráltuk volna a függvényt, azzal, hogy nem kell ezt korábban tegyük, sem nevet kitalálnunk neki. Itt egyértelmű, hogy a kimenet típusa is $\mathrm{Int}$ lesz: ha ismert típusú az input, akkor az output típusa kiszámítható, kivéve, ha a függvény rekurzív - de anonim függvény nem lesz rekurzív, hiszen nincs neve, amivel hívni tudná magát.
• Az $i$ érték esetében: az értéknek deklaráltuk explicit, hogy $\mathrm{Int}\Rightarrow\mathrm{Int}$ típusú legyen, a kapcsoson belül, magában a lambda függvényben nem. De nem baj: a fordító rájön, hogy ha az $i$-nek egy $\mathrm{Int}\Rightarrow\mathrm{Int}$ típusú függvény az értéke, akkor ott a kapcsosban az az $x$ csak $\mathrm{Int}$ lehet. Eztán még leellenőrzi, hogy ekkor a kapcsoson belül deklarált függvény kiértékeléskor tényleg $\mathrm{Int}$et ad-e vissza és ha igen (most igen), akkor rendben, egyébként fordítási hibát kapunk.
• A harmadik esetben a $\_$ wildcarddal, $\Rightarrow$ nélkül deklaráljuk ugyanezt a függvényt. Ha így deklarálunk egy függvényt, az azt jelenti, hogy annyi paraméteres a függvényünk, ahányszor előfordul benne a $\_$ jel, az első paraméter az első $\_$ helyére, a második a másodikéra stb. helyettesítődik be. Most csak egy van, tehát ez egy egyváltozós függvény; mivel $j$ típusa explicit deklarált, ebből kijön, hogy a paraméter $\mathrm{Int}$ kell legyen.

 Persze többváltozós függvényeket is tudunk kezelni ilyen módon: ha például a függvényünk maga az összeadás, ugyenezek a módik a következőképp néznek ki:

def plusz(x: Int, y: Int) = x + y
println(plusz(4,6)) // prints 10

val f : (Int,Int) => Int = plusz
println(f(4,6)) //also prints 10

val g = plusz _ //inferred type. csak egy wildcard kell!
println(g(4,6)) //also prints 10

val h = { (x: Int, y: Int) => x + y }
println(h(4,6)) //also prints 10

val i: (Int,Int) => Int = { (x,y) => x + y }
println(i(4,6)) //also prints 10

val j: (Int,Int) => Int = { _ + _ }
println(j(4,6)) //also prints 10

Tehát a függvény formális paraméterlistájának a típus-sorozatát kerek zárójelekbe kell tenni. Erre még visszatérünk, ez a típusok "szorzata" címen fog később futni. Egy pontra érdemes figyelni: a $g$ megadásakor csak egy wildcardra van szükség, ez kell a fordítónak ahhoz, hogy értse, most a függvényről mint $(\mathrm{Int},\mathrm{Int})\Rightarrow\mathrm{Int}$ értékről akarunk beszélni és nem meghívni akarjuk.

Scalában minden kifejezés, nincs megkülönböztetve "eljárás" és "függvény". Ami egy "eljárás"hoz legközelebb áll, az egy $\mathrm{Unit}$ típusú kifejezés. A $\mathrm{Unit}$ egy elég kis értéktartományú típus, eddig a $\mathrm{Boolean}$ volt a rekorder a kételemű értéktartományával (lehet $\mathrm{true}$ vagy $\mathrm{false}$), a $\mathrm{Unit}$ ennél kisebb: egyetlen $\mathrm{Unit}$ típusú érték van, a $()$ (üres zárójelpár). A $\mathrm{println}$ függvény például $\mathrm{String}\Rightarrow\mathrm{Unit}$ típusú: kap egy $\mathrm{String}$et és garantáltan a $()$ értékre értékelődik ki.
Persze ha egy kifejezés típusa $\mathrm{Unit}$, akkor az értékét már ezek szerint kiértékelés nélkül is tudjuk (feltéve, hogy terminál a kiértékelés és nem esik végtelen ciklusba) - egy $\mathrm{Unit}$ típusú kifejezés kiértékelése vélhetően azért történik, mert van mellékhatása, amit szeretnénk. Ilyen pl. a $\mathrm{println}$ függvény részéről a konzolra kiírás.

Függvényt paraméterként is várhatunk, ezek után talán nem meglepő módon:

  def kiertekelNullaban(f: Int => Int) = f(0)

  println(kiertekelNullaban({ _ + 5 })) //prints 5

  def egymasUtan(f: Int => Int, g: Int => Int): Int => Int = {
    x => g(f(x))
  }

  val megegy_szorketto = egymasUtan({ _+1 }, { _*2 })
  println(megegy_szorketto(3)) //prints (3+1)*2 = 8

  def plusz(x: Int ): Int => Int = {
    y => x + y
  }
  //plusz kap egy x-et és visszaad egy függvényt,
  //ami ha aztán kap egy y-t, akkor visszaadja x+y-t

  val pluszHat = plusz(6)
  println(pluszHat(4)) //prints 10

az első hívásnál  kapunk egy $\mathrm{Int}\Rightarrow\mathrm{Int}$ függvényt, és behelyettesítjük a nullát, visszaadjuk az értéket; a második esetben kapunk két $\mathrm{Int}\Rightarrow\mathrm{Int}$ függvényt, $f$-et és $g$-t és visszaadunk egy harmadik függvényt, a kettő kompozícióját: ami egy input $x$-re visszaadja $g(f(x))$-et, azaz először alkalmazza rajta $f$-et, majd az eredményen $g$-t és ezt az értéket adja vissza. A harmadik esetben pedig egy $x$ számot kapunk, és visszaadjuk azt a függvényt, ami ha megkap egy $y$ számot, akkor adja vissza az $x+y$ értéket. Itt talán érdemes megfigyelni, hogy ez a kétváltozós összeadás függvény "szétbontva" két egyváltozós függvénnyé, vagy mondhatjuk úgy, hogy egy $(\mathrm{Int},\mathrm{Int})\Rightarrow\mathrm{Int}$ függvényt írtunk át $\mathrm{Int}\Rightarrow(\mathrm{Int}\Rightarrow\mathrm{Int})$ alakba. Ezt a műveletet (amit persze akárhány paraméteres függvényre el lehet végezni, végeredményben csupa egyparaméteres függvényt kapva) curryingnek nevezik (és Brooke Haskell Curry után nevezték el így).

04 - Call by value, call by name

Az előző posztban láthattuk, hogy pl. egy $\mathrm{tailSum}(4-1,5+4)$ hívást intéztünk, az futás közben előbb kiértékeli az első argumentumot: $\mathrm{tailSum}(3,5+4)$, majd a másodikat (szép sorban az összeset), $\mathrm{tailSum}(3,9)$ és miután már megvan az argumentumok értéke, ezután hívja meg a függvényt (és, a substitution modelnek megfelelően, itt épp a $3$ és a $9$ értékeket helyettesíti be a függvénytörzsben a formális paraméterek helyére).

Ha egy függvény egy paraméterére ez az eljárás, azt call-by-value, azaz CBV konvenciónak nevezzük, és a Scala esetében ez az alapértelmezett viselkedés.

Egy másik lehetőség lenne az, hogy (ennek a konkrét kifejezésnek az esetében) nem értékeljük ki a $4-1$ ill. $5+4$ kifejezések értékeit, hanem így ahogy vannak helyettesítjük be őket a formális paraméterek helyére. Ezt a konvenciót nevezik call-by-name, azaz CBN -nek.

Értékeljük ki az előző poszt $\mathrm{tailSum}(5,0)$ kifejezésének értékét úgy, hogy CBN kezeljük a paramétereket:

$\begin{align*}\mathrm{tailSum}(5,0)&\triangleright \mathrm{if}(5\leq 0)~0~\mathrm{else}~\mathrm{tailSum}(5-1,0+5)\\&\triangleright \mathrm{if}(\mathrm{false})~0~\mathrm{else}~\mathrm{tailSum}(5-1,0+5)\\&\triangleright \mathrm{tailSum}(5-1,0+5)\\&\triangleright \mathrm{if}((5-1)\leq 0)~0~\mathrm{else}~\mathrm{tailSum}((5-1)-1,0+5+(5-1)))\\&\triangleright \mathrm{if}(4\leq 0)~0~\mathrm{else}~\mathrm{tailSum}((5-1)-1,0+5+(5-1)))\\&\triangleright \mathrm{if}(\mathrm{false})~0+5~\mathrm{else}~\mathrm{tailSum}((5-1)-1,0+5+(5-1)))\\&\triangleright \mathrm{tailSum}((5-1)-1,0+5+(5-1)))\\&\triangleright\mathrm{if}((5-1)-1\leq 0)~0+5+(5-1)~\mathrm{else}~\mathrm{tailSum}(((5-1)-1)-1,0+5+(5-1)+(5-2))\\&\triangleright\mathrm{if}(4-1\leq 0)~0+5+(5-1)~\mathrm{else}~\mathrm{tailSum}(((5-1)-1)-1,0+5+(5-1)+((5-1)-1))\\&\triangleright\mathrm{if}(3\leq 0)~0+5+(5-1)~\mathrm{else}~\mathrm{tailSum}(((5-1)-1)-1,0+5+(5-1)+((5-1)-1))\\&\triangleright\mathrm{if}(\mathrm{false})~0+5+(5-1)~\mathrm{else}~\mathrm{tailSum}(((5-1)-1)-1,0+5+(5-1)+((5-1)-1))\\&\triangleright\mathrm{tailSum}(((5-1)-1)-1,0+5+(5-1)+((5-1)-1))\\&\triangleright \mathrm{if}(((5-1)-1)-1\leq 0)~0+5+(5-1)+((5-1)-1)~\mathrm{else}~\mathrm{tailSum}(((5-1)-1)-1)-1,0+5+(5-1)+((5-1)-1)+(((5-1)-1)-1))\\\end{align*}$

(itt most akkor leállunk, mert nem fér ki a képernyőre széltében) hát. Persze, sejtjük, hogy ez matematikailag ugyanaz, mint a call-by-value implementáció, de rengetegszer számolja ki ugyanazokat a kifejezéseket (ami, ha nincs mellékhatása az adott kifejezésnek, érezhetően fölösleges meló), másrészt mintha a kifejezés mérete is így, hogy nem értékeljük ki a belső részeit, növekedne.

Scalában ha egy paramétert call-by-name akarunk átadni, azt a kettőspont és a típus közé írt $=>$ jelöli. A $\mathrm{tailSum}$ függvény call-by-name hívva:

import scala.annotation.tailrec

object Main extends App {
  def tailSum(n: Int) = {
    @tailrec
    def tailSum(n: =>Int, acc: =>Int): Int =
      if (n <= 0) acc else tailSum(n - 1, acc + n)

    tailSum(n, 0)
  }

  println(tailSum(20000)) //StackOverflowError
}

és talán nem lep meg senkit: ez így ebben a formában megint kivételt fog nekünk dobni - kapunk egy $\mathrm{StackOverflowError}$t. Hogy ez pontosan miért történik, azt később érteni is fogjuk - dióhéjban, a call-by-name paramétereknél a fordító egy függvényt fog nekünk készíteni és fordítani, és ezeknek a függvényeknek az egymásba stackelése lesz az, amit nem bír el a call stack.

Felmerül a kérdés, hogy ugyan miért akarna bárki call-by-name paramétert. Amit meg tudunk spórolni: ha a paramétert a függvény törzsének kiértékelésekor maximum egyszer értékeljük ki és előfordulhat, hogy egyáltalán nem, akkor érdemes lehet call-by-name hívni, főleg, ha az adott paramétert esetleg sokáig tarhat kiértékelni (ha aztán nem is használjuk, akkor minek értékeljük ki - hacsaknem egy mellékhatást szeretnénk előhozni).

Egy példa lehet a logikai műveletek (éselés, vagyolás) gyorsított kiértékelése: ha az első argumentum már meghatározza a kifejezés értékét, a másodikat nem értékeljük ki. Erre pl. egy if-else megoldás:

object Main extends App {
  def loop: Boolean = loop //végtelen ciklus
  def myNeg(x: Boolean) = if(x) false else true
  def myAnd(x: Boolean, y: =>Boolean) = if (x) y else false
  def myOr(x: Boolean, y: =>Boolean) = if (x) true else y

  println(myAnd(false, loop)) //prints false
}

Persze Scalában a Boolean változókat a C-ben / Javában szokott módon, direktben is tudjuk a $!$, $\&\&$ és $||$ operátorokkal negálni, éselni ill. vagyolni, de példának jó ez. Figyeljük meg azt is, hogy a $\mathrm{myAnd}(\mathrm{false},\mathrm{loop})$ hívás, mivel a $\mathrm{loop}$ kifejezés végtelen ciklusban értékelődik ki és nem is terminál (sőt, mivel tail recursive, a call stacket sem tölti, ezért ha ki próbáljuk értékelni, utána kézzel ki kell lőni a programot, nem öli meg a JVM), mégis terminál, mert a második paraméter call-by-name és ennél a kifejezésnél nem lesz szükség az értékére. Ebből jó lehet a call-by-name paraméterátadás, de van overheadje is és többször kiértékelni sem biztos, hogy akarjuk a kifejezéseinket.

03 - tail recursion

Nézzük a következő két rekurzív függvényt:

def butaSum(n: Int ): Int =
  if (n <= 0) 0 else n + butaSum(n - 1)

println(butaSum(20000)) //StackOverflowError

def tailSum(n: Int, acc: Int ): Int =
  if ( n <= 0 ) acc else tailSum(n - 1, acc + n)

def tailSum(n: Int) = tailSum(n, 0)

println(tailSum(20000)) //prints 200010000

Mindkét függvény, a $\mathrm{butaSum}$ és a $\mathrm{tailSum}$ is ha megkapja az $n$ egész számot, akkor visszaadja az $1+2+\ldots+n$ összeget. Az első implementáció, ha (nálam, a default call stack mérettel)  $n=20000$-re hívjuk, elszáll egy $\mathrm{StackOverflowError}$ral, pont azért, ami az előző poszt végén áll: betelik a call stack.

Amit mindenesetre már láthatunk a kódból: Scalában nem baj, ha két függvénynek ugyanaz a neve, mindaddig, amíg a paraméterlistájuk nem egyforma hosszú, vagy legalább egy típusban nem térnek el. (tehát csak a paraméterek típusa számít, a nevük nem.) Mivel a $\mathrm{tailSum}$ függvény első változata két $\mathrm{Int}$et, a második pedig csak egy $\mathrm{Int}$et vár, így ez két különböző függvény, a fordító képes eldönteni, hogy mikor melyiket hívja a programozó.
Ezt úgy is nevezik, hogy a függvény polimorf (polymorphic) -- konkrétan, ha ugyanazon a néven több implementációja is van a függvénynek, melyek egészen eltérő paraméterekre másképp viselkednek, azt "ad hoc polymorphism"nak nevezik. Látni fogunk később másmilyen polimorfizmust is.

Értékeljük ki a $\mathrm{tailSum}(5)$ kifejezést, hogy legyen valami képünk arról, hogyan is működik és miért nem tölti a call stacket:
$\begin{align*}
\mathrm{tailSum}(5) &\triangleright \mathrm{tailSum}(5,0)\\
&\triangleright \mathrm{if}(5\leq 0)~0~\mathrm{else}~\mathrm{tailSum}(5-1,0+5)\\
&\triangleright \mathrm{if}(\mathrm{false})~0~\mathrm{else}~\mathrm{tailSum}(5-1,0+5)\\
&\triangleright \mathrm{tailSum}(5-1,0+5)\\
&\triangleright \mathrm{tailSum}(4,0+5)\\
&\triangleright \mathrm{tailSum}(4,5)\\
&\triangleright \mathrm{if}(4\leq 0)~5~\mathrm{else}~\mathrm{tailSum}(4-1,5+4)\\
&\triangleright \mathrm{if}(\mathrm{false})~5~\mathrm{else}~\mathrm{tailSum}(4-1,5+4)\\
&\triangleright \mathrm{tailSum}(4-1,5+4)\\
&\triangleright \mathrm{tailSum}(3,5+4)\\
&\triangleright \mathrm{tailSum}(3,9)\\
&\triangleright \mathrm{if}(3\leq 0)~9~\mathrm{else}~\mathrm{tailSum}(3-1,9+3)\\
&\triangleright \mathrm{if}(\mathrm{false})~9~\mathrm{else}~\mathrm{tailSum}(3-1,9+3)\\
&\triangleright \mathrm{tailSum}(3-1,9+3)\\
&\triangleright \mathrm{tailSum}(2,9+3)\\
&\triangleright \mathrm{tailSum}(2,12)\\
&\triangleright \mathrm{if}(2\leq 0)~12~\mathrm{else}~\mathrm{tailSum}(2-1,12+2)\\
&\triangleright \mathrm{if}(\mathrm{false})~12~\mathrm{else}~\mathrm{tailSum}(2-1,12+2)\\
&\triangleright \mathrm{tailSum}(2-1,12+2)\\
&\triangleright \mathrm{tailSum}(1,12+2)\\
&\triangleright \mathrm{tailSum}(1,14)\\
&\triangleright \mathrm{if}(1\leq 0)~14~\mathrm{else}~\mathrm{tailSum}(1-1,14+1)\\
&\triangleright \mathrm{if}(\textrm{false})~14~\mathrm{else}~\mathrm{tailSum}(1-1,14+1)\\
&\triangleright \mathrm{tailSum}(1-1,14+1)\\
&\triangleright \mathrm{tailSum}(0,14+1)\\
&\triangleright \mathrm{tailSum}(0,15)\\
&\triangleright \mathrm{if}(0\leq 0)~15~\mathrm{else}~\mathrm{tailSum}(0-1,15+0)\\
&\triangleright \mathrm{if}(\mathrm{true})~15~\mathrm{else}~\mathrm{tailSum}(0-1,15+0)\\
&\triangleright 15
\end{align*}$

és valóban, $1+2+3+4+5=15$.

Ha megfigyeljük a kifejezés kiértékelés lépéseit, láthatjuk azt is, hogy ez egy olyan rekurzió, amit bármekkora $n$-re is hívunk meg, a kifejezés mérete egy konstans korlát alatt marad (ha a számokat konstans méretűnek, pl $32$ bitesnek vesszük), pontosan ezért nem dobott $\mathrm{StackOverflowError}t, szemben a másik implementációval. Ha egy rekurzív függvény rendelkezik azzal a tulajdonsággal, hogy minden rekurzív hívás "végérték" pozícióban szerepel, azaz: a rekurzív hívás kiértékelése a végeredményt fogja adni, és nem csinálunk utána vele már semmit, akkor ezt farokrekurzív (tail recursive) függvénynek nevezzük és nagyon hasznos - ahogy a fenti levezetésben is látjuk, ha farokrekurzió van, az nem kell töltse a call stacket.

Legalábbis, Scalában nem tölti, mert a fordító kioptimalizálja, ezt a tevékenységét nevezik "tail call optimization"nak, TCO-nak. Mivel funkcionális programozási nyelvekben a rekurzió a fő "vezérlési szerkezet", így a funkcionális nyelvek jellemzően támogatják a TCO-t. A Java nem támogatja a TCO-t, ha Javában implementáljuk ezt az összeadó függvényt, ugyanúgy kivételt fog dobni kiértékeléskor.

Lássuk csak most, miért is működik helyesen ez a tail recursive implementáció? Nézegetve a futást, azt látjuk, hogy mintha a $\mathrm{tailSum}(n,acc)$ kifejezés értéke mindig $1+2+\ldots+n+acc$ lenne. Egy ilyen állítást, sejtést, összefüggést, whatevert például indukcióval tudunk belátni - a funkcionális nyelvek előnye, hogy nagyon sok esetben sokkal egyszerűbb reasoningolni a kód helyességéről, mint ha a kódban van mutable data is.

Az indukció pl. természetes számokra így működik: ha valamit be akarunk látni, hogy minden természetes számra igaz, akkor belátjuk $n=0$-ra, hogy igaz, majd, abból kiindulva, hogy $n$-re igaz, kihozzuk, hogy $n+1$-re is igaz lesz. Nézzük meg, ez most itt hogy megy:

• azt akarjuk bebizonyítani, hogy $\mathrm{tailSum}(n,acc)=1+2+\ldots+n+acc$ minden $n$-re és $acc$-ra.
• ezt $n$ szerinti indukcióval tesszük: minden $n$-re belátjuk, hogy bármi is $acc$, ez az összefüggés fennáll.
• először megnézzük $n=0$-ra: akkor az $\mathrm{if}(0\leq 0)~acc~\mathrm{else}~\mathrm{tailSum}(n-1,acc+n)$ kifejezés $acc$-ra értékelődik ki végül, ekkor tényleg igaz, hiszen $1+2+\ldots+0$ egy $0$-tagú összeg, $0$ lesz, így az $1+2+\ldots+0+acc=acc$.
• eztán megnézzük $n+1$-re, ami egy pozitív szám: ekkor az $\mathrm{if}(n+1\leq 0)~acc~\mathrm{else}~\mathrm{tailSum}(n+1-1,acc+n+1)$ kifejezés, mivel a feltétel hamis lesz, így $\mathrm{tailSum}(n+1-1,acc+n)$-re, azaz $\mathrm{tailSum}(n,acc+n+1)$-re íródik át. Itt most (indukció!) valid feltételezni, hogy $n$-re már tudjuk, hogy kijön, azaz ennek a kifejezésnek az értéke $1+\ldots+n+acc+n+1$ lesz. Ami ugyanaz, mint $1+\ldots+(n+1)+acc$, és pont ezt akartuk igazolni.

Tehát, a $\mathrm{tailSum}(n,acc)$ függvényt most már tudjuk, hogy mit számol ki: így a $\mathrm{tailSum}(n)=\mathrm{tailSum}(n,0)$ függvény pedig az első $n$ pozitív egész összegét, plusz $0$-t, azaz tényleg az első $n$ pozitív egész összegét adja vissza.

 Hagyhatnánk ennyiben is, de ez is ér és szebb:

import scala.annotation.tailrec

object Main extends App {
  def tailSum(n: Int) = {
    @tailrec
    def tailSum(n: Int, acc: Int): Int = 
      if ( n <= 0 ) acc else tailSum(n - 1, acc + n)
    
    tailSum(n, 0)
  }

  println(tailSum(20000)) //prints 200010000
}

Mit látunk itt? Egyrészt, Scalában szabad függvényen belül deklarálni másik függvényt. Ennek az az előnye, hogy ha a belső függvény egy "helper" függvény, mint most, amit alapvetően nem akarunk kiajánlani másoknak, hogy hívogassák, akkor berakva a függvény scope-jába elérjük, hogy ezt senki ne lássa és csak itt, ebben a függvényben létezzen, less clutter. Másrészt, a $\mathrm{@tailrec}$ egy annotáció (hogy csak így keresztnéven emlegethessük és ne az első sorban az import után látható teljes nevét kelljen kiírni, arra szolgál az import parancs föntebb; az idea ctrl-space kiegészíti nekünk a tailrec annotációt és felírja az importot automatikusan, ezzel egyelőre nem kell foglalkoznunk). A lényege: a fordítónak azt jelezzük vele, hogy itt az állt a szándékunkban, hogy egy tail recursive metódust írjunk. A fordító ennek hatására nem csak hogy lefordítja nekünk a kódot mint máskor, hanem még ellenőrzi is, hogy tényleg tail recursive-e a $\mathrm{@tailrec}$ után álló függvény, és ha nem az (pl. mert nem is rekurzív, vagy mert nem mindig végpozícióban hívja magát, hanem van legalább egy olyan pont, ahol van rekurzív hívás, de annak az értékével még utána csinálunk valamit), akkor fordítási hibát dob.
A fordítási időben előjövő hibák a legjobbak, sokkal könnyebb detektálni és általában lejavítani is őket, mint a futásidejűeket :) ezért ahol csak lehet, használni fogunk annotációkat, hogy a fordító a kezünkre üthessen még időben, ha valamit rosszul csinálunk.

Még egy részlet: ebben a $\mathrm{tailSum}$ implementációban az egyváltozós függvényen belül két kifejezés szerepel: egy függvénydeklaráció (a kétváltozós függvényé), majd egy függvényhívás-kifejezés. Ezért ide kell a kapcsos zárójel (a kétváltozós belső függvény egyetlen if-else kifejezés, aköré nem muszáj tenni). Ha több kifejezés egymás után téve alkot egy blokkot (mint most), akkor a kiszámítás úgy zajlik, hogy kiértékeljük az első kifejezést, aztán a másodikat, stb, és a végső érték az utolsó kifejezés értéke lesz. Ezért most amit kapunk értéknek, az végül a $\mathrm{tailSum}(n,0)$ hívás értéke lesz.

02 - if-else és rekurzió

Nézzük ezt a függvényt (mostantól már rendszerint nem fogom kiírni a Main objectet, ami eddig minden példában szerepelt) és egy meghívását:

def parosE(n: Int) = {
  if (n % 2 == 0) "Páros" else "Páratlan"
}
println(parosE(2))

Ha futtatjuk, kiíródik, hogy "Páros". Amit a függvény törzsében látunk: egy if-else kifejezés, szintaxisa $\mathrm{if}~(B)~E~\mathrm{else}~F$, ahol $E$ és $F$ kifejezések, $B$ pedig egy $\mathrm{Boolean}$ típusú kifejezés.

C-ben megszokhattuk, hogy az intek is jók ifbe, 0 hamis, többi igaz -- Scalában nem így megy, az if feltételébe $\mathrm{Boolean}$ kell menjen, az $\mathrm{if}( n\%2 )$ nem fordul. A százalék a C-ben megszokott módon a maradékos osztás maradékát adja eredményül, tehát pl. $n\%2$ a páros számokra $0$, a páratlanokra pedig $1$ lesz. Az if-else kifejezés kiértékelésének a szabályai:

• először kiértékeljük a feltételt, lesz belőle $\mathrm{true}$ vagy $\mathrm{false}$,
• ha $\mathrm{true}$, akkor a kifejezést $E$-re írjuk át, ha $\mathrm{false}$, akkor $F$-re,
• és folytatjuk a kiértékelést.

Tehát pl. most a $\mathrm{parosE}(2)$ hívásakor a substitution model szerint egy $\mathrm{if}( 2 \% 2 == 0 )$ "Páros" $\mathrm{else}$ "Páratlan", majd egy $\mathrm{if}( 0 == 0 )$  "Páros" $\mathrm{else}$ "Páratlan", majd egy $\mathrm{if}( \mathrm{true} )$ "Páros" $\mathrm{else}$ "Páratlan", végül a "Páros" string lesz a kifejezésünk, ez a legutóbbi lesz az értéke.

A típusról: az $\mathrm{if}(B)~E~\mathrm{else}~F$ kifejezés típusa az $E$ és $F$ kifejezések típusának "legspecifikusabb közös őse" lesz - erre még visszatérünk később, mindenesetre ha $E$ és $F$ típusa ugyanaz (mint most, mindkettő String), akkor ez a közös típus lesz az if-else kifejezés típusa is. Mivel pedig emiatt a fordító ki tudja következteni, hogy String a típusa a függvényünk törzsének, ezért nem kell megadnunk, hogy a függvény visszatérési értékének a típusa String lesz.

Amikor a fordító biztos, hogy nem tudja kikövetkeztetni a típust: ha rekurzív függvényt írunk (ami saját magát hívja meg, remélhetőleg más argumentumokkal). Erre a klasszikus példa a faktoriálist számító függvény szokott lenni, amit Scalában pl. így is implementálhatunk:

def fakt(n: Int ): Int = {
  if (n <= 1) 1 else n * fakt(n - 1)
}

Lássuk, mi történik, ha pl. kiértékeljük a $\mathrm{fakt}(5)$ kifejezést. Mostantól használni fogjuk a $\triangleright$ jelet is, amikor példa kiértékelünk: $E\triangleright F$ jelenti azt, hogy az $E$ kifejezést egy lépésben az $F$ kifejezésre írjuk át. Tehát a $\mathrm{fakt}(5)$ kifejezés kiértékelése:

$\begin{align*}\mathrm{fakt}(5)&\triangleright \mathrm{ if}(5 \leq 1)~1~\mathrm{else}~5\cdot \mathrm{fakt}(5-1)\\&\triangleright \mathrm{if}(\mathrm{false})~1~\mathrm{else}~5\cdot \mathrm{fakt}(5-1)\\&\triangleright 5\cdot\mathrm{fakt}(5-1)\\&\triangleright 5\cdot\mathrm{fakt}(4)\\&\triangleright 5\cdot \left(\mathrm{if}(4\leq 1)~1~\mathrm{else}~4\cdot \mathrm{fakt}(4-1)\right)\\&\triangleright 5\cdot\left(\mathrm{if}(\mathrm{false})~1~\mathrm{else}~4\cdot \mathrm{fakt}(4-1)\right)\\&\triangleright 5\cdot \left(4\cdot \mathrm{fakt}(4-1)\right)\\&\triangleright 5\cdot \left(4\cdot \mathrm{fakt}(3)\right)\\&\triangleright 5\cdot\left( 4\cdot \mathrm{if}(3\leq 1)~1~\mathrm{else}~3\cdot \mathrm{fakt}(3-1)\right)\\&\triangleright 5\cdot\left( 4\cdot \mathrm{if}(\mathrm{false})~1~\mathrm{else}~3\cdot \mathrm{fakt}(3-1)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \mathrm{fakt}(3-1)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \mathrm{fakt}(2)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \mathrm{if}(2\leq 1)~1~\mathrm{else}~2\cdot\mathrm{fakt}(2-1)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \mathrm{if}(\mathrm{false})~1~\mathrm{else}~2\cdot\mathrm{fakt}(2-1)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \left(2\cdot\mathrm{fakt}(2-1)\right)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \left(2\cdot\mathrm{fakt}(1)\right)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \left(2\cdot\mathrm{if}(1\leq 1)~1~\mathrm{else}~1\cdot\mathrm{fakt}(1-1)\right)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \left(2\cdot\mathrm{if}(\mathrm{true})~1~\mathrm{else}~1\cdot\mathrm{fakt}(1-1)\right)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot \left(2\cdot 1\right)\right)\right)\\&\triangleright 5\cdot\left( 4\cdot \left(3\cdot 2\right)\right)\\&\triangleright 5\cdot\left( 4\cdot 6\right)\\&\triangleright 5\cdot 24\\&\triangleright 120\end{align*}$

és így kapjuk meg végül, hogy $5!$ az bizony $120$.

Amire mindenképp fel kell figyelnünk ennél a kiértékelésnél: a kifejezés hossza egyre csak növekszik, az utolsó rekurzív hívásnál, ha $\mathrm{fakt}(n)$-t hívunk, egy $n$-nel arányos méretű kifejezéssel dolgozunk. Valójában persze a Scala ugyanúgy, mint a C vagy a Java, a függvényhívásokkor a "hívási verembe" (call stack) pusholja le az argumentumokat, és hogy hova kell majd visszaugrani a vezérlésnek, aztán átugrik a meghívott függvény belépési pontjára. Ha ott lesz még egy rekurzív hívás, további argumentumokat pushol a call stackre, majd még továbbiakat, így egy $n$ mélységű rekurziónál a call stack is $n$-nel arányos ütemben telik be - és ez azért rossz hír, mert a call stack alapból elég kicsi, néhány tízezernél nem fog tudni mélyebb hívást managelni, és ekkor dob egy $\mathrm{StackOverflowError}$t, ami miatt a JVM kilövi a programunk futását.

Ezzel valamit kezdenünk kell, mert a funkcionális programozás egyik alap építőköve az, hogy ciklusok helyett rekurzióban gondolkodunk (azt lehet immutable értékek mellett is, a ciklushoz meg well, kellene ciklusváltozó). Szerencsére van a rekurziónak egy olyan fajtája, amit "farokrekurziónak" (tail recursion) hívnak és ha sikerül így írjunk programot, akkor attól nem telik a call stack. Ez lesz a következő poszt témája.

folytköv

01 - val, def, típus kikövetkeztetés és a substitution model

A kurzus legnagyobb részében pure funkcionális programozni fogunk (amennyire lehet nagy áldozatok nélkül), ami egyebek közt azt is jelenti, hogy értékekkel (value) fogunk dolgozni, változókkal (variable) pedig csak nagyon elvétve. A kettő között az a különbség, hogy az érték csak egyszer, a deklarálásakor "kap értéket", a változó pedig futás közben mutálódhat, megváltozhat a hozzá rendelt memóriaterületen a tartalom. Ha egy változó / adatszerkezet futás közben nem képes  megváltoztatni a tartalmát (nincsenek mutátorai), akkor őt az immutable, egyébként pedig mutable jelzővel illetjük.

Értéket a val kulcsszóval deklarálunk, majd az érték neve (ez szinte bármi lehet, de azért próbáljunk ésszel nevezni el értékeket és függvényeket), eztán kettőspont, majd az érték típusa, egyenlőség, és végül a kifejezés, aminek az értéke bekerül a megadott nevű értékbe. Például:

object Main extends App {
  val welcome: String = "Hello Scala"
  println(welcome)
}

Ebben a snippetben deklaráltunk egy welcome nevű értéket, aminek a típusa String. Ez a típus megfelel a Java nyelv java.lang.String -ének, konkrétan type String = java.lang.String -ként van deklarálva a Predef nevű objektumban, ami többek közt tartalmazza a gyakran használt típusok aliasait (mint a String) és néhány kényelmi függvényt (mint pl. a println). A Predef objektum minden Scala fordítási egységbe automatikusan importálódik, ezért ezeket a típusokat és függvényeket anélkül látjuk, hogy külön importolnunk kéne bármit.

A létrehozott értéket pedig inicializáltuk a "Hello Scala" értékre.

Ezt követően a következő kifejezés egy println függvényhívás, ami egy Stringet vár és mellékhatásként kiírja a kapott Stringet a konzolra.

Ebben a nyelvben pontosvesszőre szinte soha nem lesz szükségünk: ha egy sorba egyetlen kifejezést írunk (ami ezek szerint például lehet egy érték deklaráció, vagy egy függvényhívás-kifejezés), akkor ennek a végére nem kell írjunk pontosvesszőt. Ha több kifejezést is írunk egy sorba, akkor közéjük rakjunk pontosvesszőt, de a legtöbb esetben nem indokolt soronként több kifejezést is írni.

Nézzünk egy másik példát:

object Main extends App {
  val welcome = "Hello " + "Scala"
  println(welcome)
}

Ha lefuttatjuk, látjuk, hogy ez a kód is ugyanúgy kiírja az üdvözlő szöveget, mint az előző. Két különbség is van az előzőhöz képest:

• Az értékadó egyenlőség jobb oldalán a "Hello " + "Scala" kifejezés egy összeadás: két Stringet ad össze. (Idézőjelek közt deklarált karaktersorozat a megfelelő String típusú értékké fordul.) Ennek a műveletnek az eredménye egy harmadik String, melyet a két összeadott String egymás után írásával (also called "konkatenációjával") kapunk. A lényeg: egy ilyen kifejezés típusa szintén String lesz.
• A welcome értéknek nem deklaráltunk explicit típust. Olyan esetekben, amikor egy típus kikövetkeztethető, ez nem kötelező: mivel az értékadás jobb oldalán egy String típusú érték szerepel (és ezt fordítási időben már tudjuk), így ha kihagyjuk a típus megadását, akkor a fordító kikövetkeztet ("infers") neki egyet, jelen esetben a welcome érték típusa tehát String lesz akkor is, ha ezt nem mondtuk meg explicit.

A Stringen kívül még gyakran fogjuk használni az Int, Long, Float, Double, Char és Boolean típusokat: ezek pontosan azok, amiket a nevük sugall, ha akár C-ben, akár Javában programoztunk már. Fordításkor ugyanúgy a JVM (Java Virtual Machine) számára értelmezhető bytecode készül egy Scala forrásfileból, mint a Java esetében, ezért nem is meglepő, hogy ezek a fenti típusok egy az egyben megfelelnek (legalábbis abban, hogy hány biten milyen kódolásban milyen adatot lehet bennük tárolni) a Java ugyanilyen nevű (primitív vagy objektum) típusának: az Int pl. egy 32-bites előjeles szám, a Boolean tartománya meg összesen két értékből áll, az egyik a true, a másik a false.

Függvényeket a def kulcsszóval deklarálhatunk: def, ezt követi a függvény neve, paraméterlistája, kettőspont, a "visszaadott" érték típusa, egyenlőségjel, majd a függvény kifejtése.

A paraméterlista lehet üres (ha a függvény egyáltalán nem vár paramétert), vagy zárójelek közt megadva a bejövő argumentumok listája, köztük vesszővel; egy argumentumot szintén neve, kettőspont, típusa alakban adunk meg. Így:

object Main extends App {
  def addOssze(x: Int, y: Int): Int = {
    x + y
  }
  println(addOssze(2, 3))
}

Ebben a snippetben a példa kedvéért deklaráltunk egy addOssze nevű függvényt, ami két Intet vár paraméterül, és a kimeneti típusa szintén Int; konkrétan, csak összeadja a két argmentumot. Ezek után meg is hívtuk a függvényt az x=2, y=3 értékekkel, és kiírattuk az értékét.

Vegyük észre a különbséget a C / Java nyelvek függvény szintaxisa és eközt: egy dolog a kettőspont után megadott típus, de a másik fontos különbség, hogy nincs return a függvényben! 

Ennek oka a substitution model, ami a Scala nyelvben (feltéve legalábbis, hogy a függvényeink immutable argumentumokat kapnak, ami most teljesül) a "függvényhívás" alakú kifejezések kiértékelésének módja. Egész egyszerűen a következő történik elvi szinten (valójában nem pont ez, azért a Scala fordítómotor hatékonyabb ennél, de biztosak lehetünk abban, hogy ami történik, annak hatása pont ugyanaz lesz, mint a most felvázolt módszerrel lenne): a függvényhíváskor az első formáis paraméter (most az x) helyére behelyettesítjük a függvény törzsében (most a két kapcsos közti részben) az első argumentumot (most a 2-t) mindenhol, a második formális paraméter (y) helyébe a második argumentumot (3), stb, és a függvény törzséből így kapott kifejezéssé írjuk át az eredeti függvényhívásunkat. Vagyis: egy println(addOssze(2, 3)) kifejezés kiértékelésekor első lépésben átíródik println({ 2 + 3 })-ra. Mivel itt a kapcsoson belül már csak egy kifejezés van, a kapcsost eztán elhagyja (ha nagyon formálisak akarunk lenni), átíródik println(2+3)-ra, eztán a 2+3 kifejezést írja át az értékére, println(5), és ezek után a println függvényt (hasonlóan) meghívja, annak kiértékelése közben mellékhatásként kiírodik az 5 a konzolra.

Amiért a kiírásra azt írom, hogy a println függvény hívásának egy "mellékhatása", az azért van, mert nem a kiírás az "értéke" ennek a kifejezésnek! Minden, ami "történik" kifejezés kiértékelés közben a meghívott függvényen "kívül" is látható módon, azt mellékhatásnak nevezzük, így pl a konzolra írás is, egy globális változó átírása is, adatbázisba írás is mellékhatás. A println metódus egyébként Unit típusú - erről a típusról egy későbbi posztban lesz szó, egyelőre felfoghatjuk voidként.

Függvényeknél szintén igaz, hogy ha a fordító ki tudja következtetni az eredmény típusát, akkor nem kell megadnunk, itt pedig ki tudja: az x egy Int, az y egy Int, két Int összegének típusa pedig (Scalában is) egy Int lesz, tehát a függvény fejlécében a : Int rész kihagyható. Továbbá, a függvény törzse körül a kapcsos zárójel szintén elhagyható: ha csak egy kifejezésünk van, nem kell kapcsosba tennünk. Hogy új sorba írjuk-e vagy sem, a fordító számára mindegy:

object Main extends App {
  def addOssze(x: Int, y: Int) = x + y
  println(addOssze(2, 3))
}

is pontosan ugyanarra fordul, mint az előző.

folytköv