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 NaNt, 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 zippel, majd elég egy map. Figyeljünk az üres listára.

1
2
3
4
5
6
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

1
2
3
4
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.
  • zipelhetü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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
@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.

1
2
3
4
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