12 - listaműveletek

Láttuk előadáson, hogy van beépített immutable List osztály:

• az üres List a Nil object
• amit eddig Consnak neveztünk, az :: névre hallgat, pl. 1 :: 2 :: 5 :: Nil az (1,2,5) lista
• generic: List[Int] a típusa az Int listának (amink eddig volt), List[Double] a Double listának stb

Ebben a leckében a List metódusaival fogunk dolgozni, főképp a map, filter és foldLeft nevűekkel.

map, filter, fold

Írjunk egy increase függvényt, ami kap egy Int listát és egy c egész számot, és visszaad egy olyan listát, melynek minden eleme pont c-vel nagyobb, mint az eredetié!

Pl. increase( 1 :: 2 :: 3 :: Nil , 3 ) értéke 4 :: 5 :: 6 :: Nil kéne legyen.

Írjuk meg mintaillesztéssel is és valamelyik alkalmas beépített metódussal is.

Mintaillesztéssel kb hasonló a helyzet, mint korábban, csak kicsit más a szintaxis, mint amit megszoktunk:

def increase( list: List[Int], c: Int ): List[Int] = list match {
  case Nil => Nil
  case head :: tail => (head + c) :: increase(tail, c)
}

Itt a második `case` mintája olyasmi, mint amit eddig még talán nem láttunk; valójában használhatjuk a korábbi szintaxisunk szerinti `::(head, tail)` mintát is, úgy is fordul. Általában mintaillesztésnél mintaként ha egy case class a minta, akkor az osztály nevét (ami most a `::`) írhatjuk infix is: így például az eddigi `Cons( head, tail )` minták helyett **lehetett volna `head Cons tail` is**, ugyanazt kapjuk. Persze a művelet így nem tail rekurzív - a szokásos módon azzá tehetjük, de az egyik korábbi példában itt is kell egy reverse függvény, miután feldolgoztunk mindent és az eredményeket egy plusz lista argumentumba gyűjtöttük le.

Válasz mutatása

Melyik beépített metódus alkalmazható erre a kérdésre, és hogyan?

Egy listából akarunk egy **másik listát** készíteni úgy, hogy minden elemén alkalmazzuk **ugyanazt a transzformációt**, a sorrend az eredeti kell legyen - ez a **`map`**.

Hint mutatása

def increase( list: List[Int], c: Int): List[Int] = list map { _+c }

Itt élünk az * unáris metódus argumentuma körüli zárójel * és a metódus neve előtti pont elhagyásával, de írhatnánk persze `list.map( { _+c} )`-t is. A `{ _+c }` metódus pedig azért fordul így le, mert a `list`ről a paraméter típus alapján tudjuk, hogy az egy `List[Int]`, akkor a `{ _+c }` egy olyan függvény, melynek egyetlen paraméterének típusa `Int`, azaz `_` is int és `c` is (paraméterlista alapján), két int összege egy int, tehát ez egy `Int` értékeket gyártó függvény lesz, így a kimenet típusa valóban `List[Int]` lesz.

Válasz mutatása

Írjunk egy positives: List[Int] => List[Int] függvényt, mely az input listából pontosan a pozitívakat tartja meg, pl. ha list = (1, -4, 2, 0, 8, -5, -7), akkor az eredmény (1, 2, 8). Ismét írjuk meg mintaillesztéssel és valamelyik (melyik?) beépített metódussal is.

Egy listából akarunk egy **másik listát** készíteni úgy, az **eredeti elemek egy részét** tartjuk meg annak függvényében, hogy igaz-e rájuk valami predikátum (most pl az, hogy pozitívak-e), ez a **`filter`**.

Hint mutatása

Mintaillesztéssel, if guarddal:

def positives(list: List[Int]): List[Int] = list match {
  case Nil => Nil
  case head :: tail if ( head > 0 ) => head :: positives( tail )
  case _ :: tail => positives( tail )
}

Filterrel:

def positives( list: List[Int] ): List[Int] = list filter { _>0 }

Válasz mutatása

Használva valamelyik (melyik?) beépített általános metódust, írjunk függvényt, mely összegzi egy Int lista elemeit!

* Egy listából szeretnénk **egy darab** aggregált értéket kiszámítani, szóba jöhet a `reduce` vagy a `fold`. * Mivel üres listára is működnie kéne, a `fold` az opció. * A `fold`oknak egy spéci szintaxissal meg kell adni a kezdőértéket (összegnél ez mennyi?) és magát a műveletet, amit rendre alkalmazunk az aggregált értéken. * Mivel most megegyezik a lista elemeinek típusa (`Int`) az aggregált érték típusával (összegük szintén `Int`), ezért nem kell a `foldLeft` vagy `foldRight` közül válasszunk: jó lesz most a `fold` nevű metódus.

Hint mutatása

Mintaillesztéssel, if guarddal:

def szum( list: List[Int] ): Int = list.fold(0)( _+_ )

A `fold` metódus először is a kezdőértéket várja, majd visszaad egy **függvényt**, ami ha megkap egy **műveletet** (most éppen egy `(Int,Int)=>Int` műveletet), akkor elvégzi az aggregálást, ezért a dupla zárójel egymás után: ``list.fold(0)` visszaad egy függvényt, és belehelyettesítjük a `_+_` (aka összeadás) kétváltozós függvényt.

Válasz mutatása

Az idea besárgítja ezt az implementációt, ezt rendszerint okkal teszi:

Ebből két dolgot vezethetünk le:

• jól írtuk meg a függvényt, hiszen különben nem pont a sumot ajánlaná fel, ,,még az idea is látja, hogy ez összegzés'',
• a List[T]-nek van .sum metódusa bizonyos T típusokra. Nem mindenre! Eleve az összeadás nem mindig definiált egy típus elemei közt, de még ha az is, se biztos, hogy van sum: pl. Stringek is összeadhatók egymással, de a Stringekre ugyanígy megírt foldra nem ajánlja fel az idea a cserét, mert a List[String]-nek nincs sum metódusa.

De mindig érdemes megnézni, hogy van-e olyan metódus a használt kollekciónkban, ami pont kell nekünk, ne írjuk újra a spanyolviaszt.

zip

A List[T].zip[U]( that: List[U] ): List[(T,U)] metódus (szignatúrájából is sejthető módon) egy T típusú és egy U típusú elemeket tartalmazó listát ,,zipel'' össze: az eredmény egy lista lesz, melyben (T,U) párok lesznek, az első elem a két első elem által alkotott pár, a második elem a két második elem által alkotott pár stb. Ha a listák nem egyforma hosszúak, akkor a hosszabb lista vége nem kerül be az eredménybe semmilyen formában.

Implementáljuk a zip metódust mintaillesztéssel, úgy, hogy két listát váró függvény legyen, ne member metódus!

def zip[U,T]( left: List[U], right: List[T] ): List[(U,T)] = (left, right) match {
  case (Nil,_) => Nil
  case (_,Nil) => Nil
  case ( head1 :: tail1, head2 :: tail2 ) => (head1, head2) :: zip(tail1, tail2)
}

Az eddig látottakhoz hasonlóan persze ez is impementálható tail rekurzívan (kell hozzá reverse is).

Válasz mutatása

Mi történik, ha egy head::tail listát zipelünk a farkával?

Megkapjuk a **szomszédos párok** listáját (eggyel rövidebb lesz, mint az eredeti volt); pl. az `(1,4,2,8,5,7)` listából az `((1,4), (4,2), (2,8), (8,5), (5,7))` lista lesz.

Válasz mutatása

Łealocsolás

Néhány feladatot Gercsó Márk Stepikes sorozatából is megoldhatunk ennyi listaművelettel felvértezve, az elsőben egy toronyban locsolunk virágokat:

Egy sokemeletes toronyban Łeandereket locsol a Łeanderłocsoló. A toronyban van egy lift, mely csak a földszintről egy-egy emeletre és onnan vissza tud közlekedni, és van egy vödrünk, megadott kapacitással: amit tehetünk, az az, hogy a földszinten lévő kútban megtöltjük a vedrünket, felmegyünk a lifttel valamelyik emeletre, meglocsolunk ott annyi Łeandert, amennyit csak tudunk a vederből, majd vissza a földszintre, vödör újratölt és ezt ismételjük, míg a toronyban minden Łeandert meg nem locsoltunk.

A feladat:

• inputként megkapunk egy List[Int] listát, melyben fel van sorolva, hogy hány zöldség van az egyes emeleteken,
• továbbá a vedrünknek az Int kapacitását,

adjuk vissza, hogy hányszor kell fordulnunk, mire meglocsolunk minden Łeandert. Az inputról feltehetjük, hogy ,,helyes'' as in minden emeleten nemnegatív egész a virágok száma, a kapacitás pedig pozitív egész.

példa: ha az input lista az (1,4,2,8,5,7) és a kapacitás 3, akkor az eredmény 1 + 2 + 1 + 3 + 2 + 3 = 12 kellene legyen.

Implementáljuk ezt a metódust!

Ahogy a példából látszhat is, * először érdemes lehet minden emeletre meghatározni az oda kellő fordulók számát, **ami egy `map`**, * majd összeadni a kapott számokat, **ami egy `sum`**, és persze a szükséges fordulók számát **osztással** kaphatjuk meg, egyvalamire kell figyelnünk: Scalában az `Int`ek közt egészosztás van **lefelé** kerekítéssel, pl. `8/3 = 2` és nekünk most pont felfelé kerekítés kéne. Hogy kapunk olyat?

Hint mutatása

Ha `K`-val akarunk osztani és felfelé kerekíteni, akkor adjunk a számhoz `(K-1)`-et és ezt egészosszuk le `K`-val:

def lealocsolas( list: List[Int], capacity: Int ) =
  list.map { x => (x+capacity-1)/capacity }.sum

Válasz mutatása

kőjónás

A faluban, ahol a torony is van az előző meséből, sok ember valami okból köveket gyűjt, viszont egy kőtolvaj jelent meg a faluban, számos lopást jelentettek, majd a körzeti megbízott lefülelte a gaz Kőjónást és talált a házában egy rakás követ. Kérdés, hogy megtaláltak-e annyi követ, mint amennyinek a lopását bejelentették.

• inputként megkapunk egy List[Int] listát, melyben fel van sorolva, hogy a lakosok rendre hány kő ellopását jelentették (feltehető, hogy ezek pozitív számok),
• továbbá egy Intet, amennyi követ találtak a gyanúsítottnál,

adjuk vissza, hogy volt-e legalább annyi kő a gyanúsítottnál, mint amennyit összesen jelentettek.

def kojonas( list: List[Int], foundKovex: Int ) = list.sum <= foundKovex

Válasz mutatása

hegymászó

Hegymászó ismerősünk végigmászik egy hegyláncon. Alapból a 0 magasságról indul, azt szeretné megtudni, hogy összesen mennyit mászott felfelé (a szomszédos magasságok különbségét kell mindig megtennie, ha a soron következő szám nagyobb, mint az aktuális, akkor felfelé megy, különben lefelé).

• inputként megkapunk egy List[Int] listát a magasságokkal, lehet benne negatív is,

adjuk vissza a felfelé mászások összegét.

Ezt a feladatot oldjuk meg mintaillesztéssel és beépített listaműveletekkel is.

**Mintaillesztéssel** elég, ha van egy függvényünk, ami megkapja a hátralévő listánkon kívül az aktuális magasságot is; ezt rejtsük el belső függvényben.

Hint mutatása

def hegymaszas(list: List[Int]): Int = {

  def hegymaszas(list: List[Int], current: Int): Int = list match {
    case Nil          => 0
    case head :: tail => ( if( head > current ) head - current else 0 ) + hegymaszas(tail, head)
  }

  hegymaszas(list, 0)
}

Ebben a kódban ismét talán csak az if-else **kifejezés**hez közvetlenül hozzáadott érték lehet meglepő. Persze így nem tail rekurzív - tegyük azzá a szokott módon, gyűjtve egy `total` aggregátor mezőbe az eddigi mászásösszeget:

def hegymaszas(list: List[Int]): Int = {

  @tailrec
  def hegymaszas(list: List[Int], current: Int, total: Int): Int = list match {
    case Nil          => total
    case head :: tail => hegymaszas( tail, head, ( if( head > current ) head - current else 0 ) + total )
  }

  hegymaszas(list, 0, 0)
}

Válasz mutatása

**Beépített műveletekkel** több kis lépésből rakhatjuk össze az eredményt, pl: * először zippel megkapjuk a ,,(honnan,hová)'' párok listáját (**`zip`**, figyelve a ,,`0`-ról indulunk'' részre), * ezekből megkapjuk a ,,mennyit'' különbségek listáját (**`map`**), * ebből csak a felfelé mászásokat tartjuk meg (**`filter`**), * és ezeket összeadjuk (**`sum`**).

Hint mutatása

def hegymaszas(list: List[Int]): Int = 
  ((0::list) zip list)               //megkaptuk a (honnan, hová) párok listáját
  .map { pair => pair._2 - pair._1 } //megvan, hogy mennyit másztunk fel/le
  .filter { _ > 0 }                  //megtartjuk a pozitívokat
  .sum                               //és összeadjuk őket

Azt érdemes megfigyelni és kipróbálni, hogy a `map`ben nem adhatjuk meg pl. `{ (left,right) => right-left }` alakban a függvényt, mert ez a felírás azt jelentené, hogy a függvény **kétváltozós**, mondjuk két intet kap; ezzel szemben a `map` függvény **egyváltozós** és egy tuplét kap, aminek van két int mezeje. Jó, ha észben tartjuk, hogy a `map`, `filter`, `fold`, `zip` és társaik **nem fognak** stacktracet dobni, jól vannak implementálva.

Válasz mutatása

valódi csillagrendszerek

Csillagász ismerősünk csillagrendszereket vizsgál: egy listába feljegyzi, hogy a bolygók belülről kifelé haladva kőzetbolygók (true) vagy gázbolygók (false). Viszont nem emlékszik, hogy a csillagrendszereket tényleg látta, vagy csak hallucinált. Egy egyszerű, de nagyszerű szűrő a következő: egy csillagrendszer akkor lehet valódi, ha a kőzetbolygók megelőzik a gázbolygókat. Segítsünk neki eldönteni a listáiról, hogy azok valódi csillagrendszereket kódolnak vagy sem.

• input: egy List[Boolean]

Döntsük el, hogy valódi csillagrendszert kódol-e a lista! pl. (true,false,true)-re false, (true,true,false,false,false), (true,true,true), () vagy (false,false) esetben true az elvárt visszatérési érték.

Akkor rossz az input, ha `false` után következik benne `true`. A `List[T].contains: T => Boolean` metódus visszaadja, hogy a lista tartalmazza-e a megadott értéket.

Hint mutatása

Ismét a szomszédos entryket kell egyben vizsgáljuk, erre való a `zip` metódus; miután a listát ziptük a farkával (note: *ha van neki* -- az üres listát külön kell kezeljük), az eredményben csak azt kell megnézni, szerepel-e a `(false,true)` elem.

def valodiCsillagrendszer( list: List[Boolean] ): Boolean = list match {
  case Nil => true
  case _::tail => !( (list zip tail) contains (false,true) )
}  

Válasz mutatása

---

Utolsó frissítés: 2021-01-01 20:32:04