13 - listaműveletek II¶

Ebben a leckében a List további metódusaival fogunk dolgozni.

átlagolás¶

Írjunk függvényt, mely kiszámolja az input list: List[Double] lista elemeinek átlagát! Ha a lista üres, legyen az érték a Double.NaN (ez a ,,not a number'' érték, amit pl. nullával osztáskor is kap az ember).

Például ha az input List(1.0, 4.0, 2.0, 8.0, 5.0, 4.0), akkor az eredmény 4.0.

Hint mutatása

Van `List[T].length: Int` metódus is.

1	`def atlag( list: List[Double] ): Double = list.sum / list.length`

Mivel pont nullával osztáskor kapunk `NaN`t, ez így jó is lesz.

Válasz mutatása

csúszóátlag¶

Írjunk függvényt, mely egy 2 hosszú ablakban számol csúszóátlagot: minden két szomszédos cellának az átlagát számolja ki (így az eredmény lista hossza eggyel rövidebb lesz, mint az eredetié)! Üres vagy egyelemű listára legyen az érték Nil.

Például ha az input List(1.0, 4.0, 2.0, 8.0, 5.0, 4.0), akkor az eredmény List(2.5, 3.0, 5.0, 6.5, 4.5).

Hint mutatása

Ismét a szomszédos cellákból kell egybegyúrnunk az adatokat mondjuk `zip`pel, majd elég egy `map`. Figyeljünk az üres listára.

def csuszoatlag( list: List[Double] ): List[Double] = list match {
  case Nil       => Nil
  case _ :: tail =>
    (list zip tail)                          //megvannak a szomszédokból álló párok
    .map { pair => (pair._1 + pair._2)/2.0 } //a pár koordinátáinak átlaga
}

Válasz mutatása

prímszűrő¶

Írjunk függvényt, mely az input List[Int] listából két listát készít és ad vissza egy párban: az egyikben a listabeli prímszámok, a másikban az összetett számok szerepelnek (és a legfeljebb 1 értékű számok az eredeti listából pedig egyikben sincsenek)!

Először talán érdemes egy isPrime: Int => Boolean függvényt írni, ami visszaadja, hogy az input szám prímszám-e. Hogyan? (Ha rekurzív, legyen tail rekurzív.)

Imperatív környezetben egy **for ciklust** vinnénk talán `2`-től felfelé addig, míg elérjük a szám négyzetgyökét; ha közben találunk osztót, akkor nem prímszám, egyébként prímszám. Persze az elején teszteljük, hogy legalább `2`-e.

Hint mutatása

def isPrime( n: Int ) = {

  //a ,,for ciklus'', melynek i az egyetlen állapot-tárolója
  @tailrec
  def forLoop( i: Int ): Boolean =
    if ( i * i > n ) true       //kilépési feltétel
    else if( n % i == 0) false  //van osztó, nem prím
    else forLoop( i+1 )

  ( n >= 2 ) && forLoop( 2 )    //ez a kifejezés adja az isPrime értékét
}

Válasz mutatása

Most már meg tudjuk írni a prímszám-összetett szám particionáló függvényt:

Létezik `List[T].partition( p: T => Boolean ): (List[T], List[T])` metódus, aminek egy **predikátumot** adunk és szétszortírozza a listát két listába: az elsőbe azok kerülnek, akikre `p` igaz, a másodikba azok, akikre `p` hamis.

Hint mutatása

def primeFilter( list: List[Int] ) =
  list                    //vegyük az eredeti listát
  .filter { _ >= 2 }      //dobjuk el belőle, aki kisebb, mint 2
  .partition( isPrime )   //a maradékot meg szortírozzuk az isPrime szerint, amit az előbb írtunk

Válasz mutatása

lista prefixe a másik¶

Írjunk olyan testPrefix[T]( list: List[T], prefix: List[T] ): Boolean generic függvényt, ami visszaadja, hogy a list lista valamilyen hosszú eleje megegyezik-e a a prefix listával!

(Ha pl. prefix = Nil, akkor mindenképp true lesz, ha list = List(1,4,2,8,5,7) és prefix = List(1,4,2), akkor szintén true).

* **Mintailleszthetünk** is: ha a fejelemek megegyeznek, akkor a maradékot kell ugyanígy prefixtesztelni, míg az egyik lista el nem fogy. * **`zip`elhetünk** is: ekkor hasznos lehet a `List[T].forall( p: T=>Boolean ): Boolean` metódus, ami akkor ad igazat, ha a lista **minden** elemére igaz a `p` predikátum. * Kereshetünk alkalmas beépített listafüggvényt is, hátha szerencsénk lesz.

Hint mutatása

Mintaillesztéssel:

@tailrec
def testPrefix[T](list: List[T], prefix: List[T]): Boolean = (list,prefix) match {
  //ha a Nil-t keressük, az biztos prefix
  case (_,Nil) => true

  //ha nem a Nil-t keressük (azt lekezelte az előző eset), de a lista üres, akkor nem prefix
  case (Nil,_) => false

  //ha két nemüres listánk van és a fejelemeik megegyeznek, akkor a farkaikat kell tovább prefixtesztelni
  case (head::tail, prefixHead::prefixTail) if (head == prefixHead) =>
    testPrefix(tail,prefixTail)

  //ha nem egyeznek a fejelemek, akkor nem prefix
  case _ => false
}

Zipve: akkor prefix, ha egyrészt a `lista` legalább olyan hosszú, mint a `prefix`, másrészt ha összezippeljük őket, akkor minden pár amit kaptunk, megegyező értéket tartalmaz a két koordinátáján.

def testPrefix2[T]( list: List[T], prefix: List[T] ): Boolean = {
  ( list.length >= prefix.length ) &&
  (list zip prefix).forall( pair => pair._1 == pair._2 )
}

Built-in: `startsWith` lol

1	`def testPrefix[T](list: List[T], prefix: List[T] ): Boolean = list startsWith prefix`

Válasz mutatása

toSet¶

Vegyük a korábbi keresőfa adatszerkezetet. Írjunk olyan toSet: List[Int] => Tree függvényt, mely kap egy int listát és sorban beszurkálja a listabeli értékeket egy kezdetben üres fába, majd visszaadja a kapott fát! Melyik listaművelet lehet erre használható?

Alapvetően * egy listából akarunk készíteni egyetlen **aggregált** értéket (ami most egy `Tree` objektum), ennyiből vagy `reduce` lesz, vagy `fold`; * üres listára is működnie kéne, ezért csak a `fold` jön szóba; * a kimeneti típusnak (`Tree`) nem altípusa a listaelem típus (`Int`), ezért maga a `fold` nem lesz jó, vagy a `List[Int].foldLeft[Tree]`, vagy a `List[Int].foldRight[Tree]` lesz a jó, a generikus paraméter onnan jön, hogy `Tree`-be fogjuk gyűjteni az értéket menet közben; * mivel az volt a kérés, hogy balról jobbra sorban szurkáljuk be a listaelemeket, **a `foldLeft[Tree]` lesz a jó választás.

Hint mutatása

A `foldLeft` először is meg kell kapja az aggregátor iniciális értékét, ez persze ahogy a szöveg is írja, az `Ures` fa lesz. Eztán az eredmény, ami egy függvény, meg kell kapja azt, hogy hogyan készüljön az eddig aggregált értékből, ami egy `Tree`, és a lista soron következő eleméből, ami egy `Int`, egy újabb `Tree` - most be kell szúrnunk, ezt írja a feladat is. Tehát a függvény a `(tree, value) => tree.inserted(value)` lesz:

1 2	`def toSet( list: List[Int] ): Tree = list.foldLeft[Tree]( Ures ) { (tree,value) => tree.inserted(value) }`

Válasz mutatása

Utolsó frissítés: 2021-01-02 00:28:17