8. gyakorlat

Pure funkcionális programozás Scala-val¶

Emlékeztetőül

A gyakorlat során pure funkcionális programok írása a cél, ezért az imperatív programozásból megismert megközelítések használata nem megengedettek.

A mutable (azaz a var-ral deklarált) változók helyett használjuk a val kulcsszót.
Az imperatív ciklusok (pl. while) használata helyett az iterációkat rekurzióval vagy magasabb rendű függvényekkel oldjuk meg.
A funkcionális programozásban a return használata is mellékhatásosnak tekinthető, mivel explicit módon megszakítja a metódus végrehajtását. Scala-ban a metódusok az utolsó kifejezés értékét automatikusan visszaadják, így a kód tisztább és könnyebben olvasható, tehát a return utasításra nincs szükség.

Az if kifejezés¶

Funkcionális megközelítésében az if egy kifejezés és nem egy vezérlési szerkezet, tehát mindig visszaad egy értéket. Ha nincs else ág, akkor a kifejezés Unit típust ad vissza. Ezért fontos, hogy ninden kifejezésnek legyen egyértelmű visszatérési értéke, azaz ne írjunk else ág nélküli if kifejezést.

  def noparam(): Boolean = {
    true
  }

  def doubled(num: Double): Double = {
    num + num
  }

  def combined(num: Double): Double = {
    if (noparam())
      1.5 + doubled(num)
    else
      2.5 + doubled(num)
  }

A `math` csomag¶

A math a Scala standard könyvtárában található, így számos hasznos matematikai függvényt biztosít, amelyek közvetlenül is elérhetők (nem kell külön importálni őket).

  val pi: Double = math.Pi
  val neg = -5.7

  println(math.min(neg, pi))
  println(math.max(neg, pi))
  println(math.abs(neg))
  println(math.sqrt(pi))
  println(math.pow(2, 3))
  println(math.round(pi)) // legközelebbi egész számra kerekít
  println(math.floor(neg)) // legközelebbi egész számra kerekít lefelé
  println(math.ceil(neg)) // legközelebbi egész számra kerekít felfelé
  println(math.random()) // 0 és 1 közötti lebegőpontos szám
  println(math.signum(-5)) // 1 ha pozítv, -1 ha negatív, 0 ha nulla a szám

  println(-7 % 3) // -1, megtartja az előjelet
  println(math.floorMod(-7, 3)) // mindig nemnegatív és kerekít a floor szerint

Rekurzió és mintaillesztés¶

A más, imperatív nyelvekből megismert ciklusok mutálható állapotokat használnak (pl. a ciklusváltozót), ezért funkcionális programozásban kerülni kell a használatukat, és rekurzióval kell megvalósítanunk a ciklusokat és az ismétlődő műveleteket.

  def factorial(num: Int): Long = {
    if (num <= 1)
      1
    else
      num * factorial(num - 1)
  }

Az if kifejezés helyett használhatunk mintaillesztést (pattern matching) is, amely lehetővé teszi, hogy a bemeneti értéket különböző mintákhoz illesszük, és minden egyes illeszkedéshez hozzárendeljük a megfelelő kódot. Ez elsőre hasonlíthat más nyelvekből már megismert switch-case szerkezetekhez, viszont a mintaillesztéssel sokkal komplexebb adatstruktúrákat (pl. listákat) is tudunk majd vele kezelni.

  def factorial2(num: Int): Long = {
    num match {
      case 0 | 1 => 1
      case n => num * factorial2(num-1)
    }
  }

Mintaillesztés esetén számít az egyes minták sorrendje, mivel az első illeszkedéshez tartozó kódrészlet fog lefutni. Bizonyos esetekben szükség lehet mintaillesztésnél egy else logika implementálása, ezt a wildcard (case _ => utasitasok) biztosítja (hiszen bizonyos esetekben nem érdemes minden lehetséges illeszkedést felsorolni).

Továbbá minden egyes minta kiegészíthető egy úgynevezetett guard-dal, ami lehetővé teszi, hogy egy adott mintát csak akkor vegyünk figyelembe, ha a feltétel teljesül: case n if n > 0 => utasítasok. A pipe (|) mintaillesztésben arra használható, hogy egyes eseteket összevonjunk, vagyis egyetlen case ágon több mintát is figyelembe vegyünk.

Tail-recursive függvények¶

Rekurzió esetén külön figyelmet kell fordítanunk arra, hogy az ismétlődő függvényhívások a hívási verem (call stack) túlcsordulását okozhatják. Ennek veremnek a mérete ugyan növelhető, alapvetően egy több tízezres mélységű rekurzív hívás olyasmi, amit el szeretnénk kerülni. Emiatt a rekurzió használatakor különösen fontos, hogy a függvény ún. tail-recursive legyen, ami lehetővé teszi a fordítónak, hogy a rekurziót hatékonyabb módon kezelje, és ne növelje feleslegesen a verem méretét. Nézzünk meg először egy függvényt, ami nem tail-recursive és hívjuk meg sum(15_000):

  def sum(num: Int): Long = {
    if ( num <= 0)
      0
    else 
      num + sum(num-1)
  }

A stack szerepe

Minden alkalommal, amikor egy programban függvényt hívunk, az alábbi információk kerülnek a stack-be, amely egy LIFO (Last In, First Out) típusú adatstruktúra:

A függvény paraméterei
A függvény scope-jában használt változók
A visszatérési cím, amely lehetővé teszi, hogy a program a függvény végrehajtása után tudja, honnan folytassa a végrehajtást.

Mivel minden egyes rekurzív hívás új frame-et (keretet) hoz létre a stack-en, egy túl mély rekurzió stack overflow-hoz vezethet.

Tail-recursive-nak nevezzük a függvényt, ha a rekurzív hívás az utolsó művelet a függvényben. Ez azt jelenti, hogy a függvénynek nem kell további műveletet elvégezni a rekurzív hívást követően. Ilyen esetben a Scala fordító tail call optimization-t (TCO) alkalmazhat, amely a rekurziót egy egyszerű ciklussá alakítja. Ennek eredménye, hogy a stack mérete nem növekszik. Az előbbi függvény tehát azért nem teljesíti a feltételt, mert a sum(num - 1) meghívását követően még végre kell hajtani egy összeadást is: num + ....

TCO esetén a rekurzió nem hoz létre új stack frame-et minden egyes hívásnál, hanem egyszerűen újrafuttatja (újrafelhasználja) a függvényt anélkül, hogy megőrizné a hívott függvény korábbi állapotát.

Egy tetszőleges függvényt úgy tudunk tail-recursive-vá alakítani, hogy az elvégzendő műveletet "bevisszük" a függvény argumentumai közé. Egy általános megközelítés lehet a következő:

Oldjuk meg a problémát hagyományos rekurzió segítségével, ellenőrizzük "kis" bemeneteten, hogy helyesen működik a függvény
Gyűjtsük ki a "változókat", amelyeket az eredeti függvény használ
Hozzunk létre egy segédfüggvényt, amely az eredeti paramétereken kívül további paramétereket, az előző pontban meghatározott változókat is várja bemenetként is vár, ezeket az új paramétereket fogjuk a számítási állapot megtartására használni
Ezek az új paraméterek fogják a számítási állapotot tárolni, így itt, a rekurzív hívás következő iterációjának meghívásakor végezzük el a műveletet

  def sum(num: Int): Long = {

    @tailrec
    def sum(num: Int, res: Long): Long = {
      if (num <= 0)
        res
      else
        sum(num - 1, num + res)
    }

    sum(num, 0)
  }

Itt továbbá alkalmazunk function overloading-ot is (megegyező nevű függvény, amelynek a paraméterlistája eltérő), illetve nested function-t. A beágyazott függvény csak annak a függvénynek a belsejében létezik, amelyben definiáltuk, és egyfajta segédfüggvényként funkcionál, amely hozzáfér a külső függvény paramétereihez.

Továbbá érdemes használni a @scala.annotation.tailrec annotációt is, így a fordító figyelmeztet (fordítási hibát kapunk), ha a függvény nem tail-recursive.

Gyakorló feladatok¶

Feladat

Készíts egy pure függvényt, amely kiszámolja az N. Fibonacci-számot ( 0, 1, 1, 2, 3, 5.. ). A kiindulási rekurzív függvény csak az N értékét várja paraméterben. Egy segédfüggvény segítségével alakítsd tail-recursive-vá a megoldásodat. A rekurziót valósítsd meg if kifejezéssel és mintaillesztés segítségével is.

Feladat

Készíts egy pure függvényt, amely kiszámolja az 1 és a paraméterben kapott N szám által határolt intervallumban található számok négyzetösszegét (1^2 + 2^2 + .. + N^2). Egy segédfüggvény segítségével alakítsd tail-recursive-vá a megoldásodat. A rekurziót valósítsd meg if kifejezéssel és mintaillesztés segítségével is.

Feladat

Készíts egy pure függvényt, amely két szám szorzását végzi el úgy, hogy csak összeadással és rekurzióval dolgozik. Egy segédfüggvény segítségével alakítsd tail-recursive-vá a megoldásodat. A rekurziót valósítsd meg if kifejezéssel és mintaillesztés segítségével is.

Feladat

Készíts egy pure függvényt, amely egy egész számot kap, és visszatér a számjegyek összegével. Egy segédfüggvény segítségével alakítsd tail-recursive-vá a megoldásodat. A rekurziót valósítsd meg if kifejezéssel és mintaillesztés segítségével is.

Feladat

Készíts egy pure függvényt, amely eldönti, hogy három adott oldalhosszúsággal szerkeszthető-e háromszög (két oldal összege mindig nagyobb kell legyen a harmadiknál). A számokat lebegőpontos számként kezeljük.

Feladat

Készíts egy pure függvényt, amely három oldal alapján kiszámítja a háromszög területét a Heron-képlet segítségével. A számokat lebegőpontos számként kezeljük.

Utolsó frissítés: 2025-04-07 08:30:21

8. gyakorlat

Pure funkcionális programozás Scala-val¶

Az if kifejezés¶

A math csomag¶

Rekurzió és mintaillesztés¶

Tail-recursive függvények¶

Gyakorló feladatok¶

A `math` csomag¶