Kihagyás

10 - list match

Az aktuális int lista implementációnk: 

1
2
3
sealed trait IntList
case object Empty extends IntList 
case class Cons( head: Int, tail: IntList ) extends IntList

length

Írjunk egy length metódust, ami hosszú listákra is működve adja vissza a listánk hosszát! Alkalmazzuk a korábbi tapasztalatainkat. Az elindulásban segíthet az alábbi hint.

A `sum`hoz hasonlóan `@tailrec` implementált privát helper függvénnyel megoldhatjuk a kérdést. Hint mutatása 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
sealed trait IntList {
  def length: Int
}
case object Empty extends IntList {
  override val length = 0
}
case class Cons( head: Int, tail: IntList ) extends IntList {
  override def length: Int = length(0)
  @tailrec
  private def length( n: Int ): Int = tail match {
    case Empty => 1 + n
    case t : Cons => t.length( 1 + n )
  }
}
Válasz mutatása

reverse

Írjunk egy reverse metódust, mely elkészíti a listánk megfordítottját!

Szintén privát helper függvénnyel: írjunk olyan `reverse: IntList => IntList` metódust, melyre igaz, hogy `list1.reverse( list ) == list.reverse ::: list`! Hint mutatása 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
sealed trait IntList {
  def reverse: IntList
}
case object Empty extends IntList {
  override val reverse = Empty //üres lista fordítva is üres
}
case class Cons( head: Int, tail: IntList ) extends IntList {
  override def reverse = reverse( Empty ) //helper metódus hívása

  @tailrec
  private def reverse( list: IntList ): IntList = tail match {
    case Empty => Cons(head, list)
    case t: Cons => t.reverse( Cons(head, list) )    
  }
}
Válasz mutatása

Bizonyítsuk be, hogy a fenti implementáció tényleg teljesíti a hintben írt tulajdonságot!

Ez az, amikor is **indukciót** tudunk használni: * ha a listánk `list = Cons(head, Empty)`, azaz egyelemű, akkor a `list.reverse( list2 )` függvény értéke a match kifejezés szerint `Cons(head, list2)` lesz, ami pont ugyanaz, mint `list.reverse ::: list2`, hiszen egyelemű lista megfordítottja önmaga lesz. * ha pedig `list = Cons(head, t)` alakú, ahol `t` is `Cons`, akkor **indukciós feltevésünk szerint** (mivel `t` egy rövidebb lista, így ér indukciót használni) `t.reverse( Cons(head, list) ) == t.reverse ::: Cons(head, list) `, ami tényleg ugyanaz, mint `list.reverse ::: list`, hiszen egy lista megfordítottjában előbb a tail megfordítottja, majd a head jön sorrendben. Emiatt pedig a `reverse` is jó lesz, hiszen `list.reverse(Empty) == list.reverse ::: Empty == list.reverse`. Válasz mutatása

toString

Írjunk egy toString: String metódust, ami a listánkat (1,2,3,4) alakban írja ki, azaz kerek zárójelek közt vesszővel felsorolja sorrendben az elemeket! Szintén elvárás, hogy működjön hosszú listákra is.

Készítsünk a `Cons` osztályba egy privát helper metódust, ami ezúttal egy Stringet kap paraméterként, amiben a lista eddig feldolgozott részének `toString`je kerül! A szeparátor vesszőkre figyeljünk oda. Hint mutatása 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
sealed trait IntList {
  def toString: String
}
case object Empty extends IntList {
  override def toString: String = "()" // üres lista toStringje
}
case class Cons( head: Int, tail: IntList ) extends IntList {
  override def toString: String = toString("(")  //ez a prefix, amit kiteszünk
  @tailrec
  private def toString( prefix: String ): String = tail match {
    case Empty => s"$prefix$head)"  //ha vége a listának, kirakjuk az utolsó elemet és )
    case t: Cons => t.toString( s"$prefix$head,") //ha még nincs vége, kiírjuk a fejet, vessző, többit
  }
}
Ha a `s"$prefix$head,"` stringet nem tudjuk, mi lehet, ez csak a `prefix + head + ","`-re egy úgynevezett ,,string interpolációs'' szintaxis, bővebben lásd [ezt az előadás fejezetet](../../eloadas/19). Válasz mutatása

mergesort

A mergesort egy rekurzív (és gyors) rendező algoritmus listákon, a következőképp működik:

  • ha a lista legfeljebb egyelemű, akkor rendezve van, visszaadhatjuk.
  • különben:
    • szétosztja a listát két kb egyforma méretű listára (mindegy, hogyan)
    • rendezi a két részlistát
    • eztán összefésüli, mergeli a két rendezett részlistát
  • a mergelés pedig sorra mindig a két mergelendő lista fejelemeit hasonlítja össze, és a kisebb fejet veszi le.

A mostani lecke egy nagyobb lélegzetvételű feladata megírni egy mergesort függvényt, ezt nem kell tagfüggvényként implementálni: kapjon egy int listát paraméterben, és rendezze ezt a fenti módon. Minden részfeladatra vannak tesztek (kivéve a függvények fejléceinek megírását), próbáljuk megoldani őket és csak szükség esetén elolvasni a hinteket! Ha sikerült az alfeladat, vagy a hint ellenére sem sikerül, nézzük meg a mintamegoldásokat is, és ha van különbség, gondoljuk át, lényeges-e.

Első lépésként írjuk meg a merge és a mergesort függvények fejléceit!

1
2
def merge( left: IntList, right: IntList ): IntList = ???
def mergesort( list: IntList ): IntList = ???
Válasz mutatása

Folytassuk mondjuk a mergesort implementálásával: mintaillesztéssel kezeljük le azokat az eseteket, mikor a lista max egyelemű!

1
2
3
4
5
def mergesort( list: IntList ): IntList = list match {
  case Empty         => list       //üres lista
  case Cons(_,Empty) => list       //egyelemű lista
  case _ => ???
}
Válasz mutatása

Írjunk egy split függvényt, mely két nagyjából egyforma méretű részlistára osztja az input listát! Mi lesz a fejléce?

Hint mutatása Két listát akarunk visszaadni, erre a célra a legjobb egy **tuple**. 
1
def split( list: IntList ): (IntList, IntList) = ??? //így egy két listából álló pár lesz a visszatérési érték típusa
Válasz mutatása

Folytassuk a mergesort implementálását: írjuk le az utolsó case jobb oldalára, hogy mit is kellene tennünk (ha a többi függvény már kész lenne)!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def mergesort( list: IntList ): IntList = list match {
  case Empty         => list       //üres lista
  case Cons(_,Empty) => list       //egyelemű lista
  case _             => {          //többi eset
    val (left, right) = split( list )   //szétosztjuk a listát ketté
    val sortedLeft  = mergesort(left)   //rekurzió: egyik részlista rendezve
    val sortedRight = mergesort(right)  //rekurzió: másik részlista rendezve
    merge( sortedLeft, sortedRight )    //a mergelt lista lesz az érték, amit visszaadunk
  }
}
Itt **két** rekurzív hívás is van belül, ez nem lesz tail rekurzív. Szerencsére most ez nem baj: minden rekurzív hívás nagyjából **felezni fogja** a lista hosszát, ha ügyesen vágjuk ketté, így ha pl. egymillió elemű is a listánk, eggyel mélyebben már csak félmilliós, még eggyel mélyebben 250k, stb, mintegy 20 mélységű rekurzió lesz ebben az esetben; ha a rekurzió az input méretéhez képest **logaritmikus mélységű**, mint most is, akkor nem fog betelni a call stack. Persze ehhez az kell, hogy a `split` tényleg nagyjából felezze a lista hosszát. Válasz mutatása

Első körben nem baj, ha nem tail rekurzívan tesszük, de implementáljuk a split függvényt is! Hogyan tűnik egyszerűnek egy lista kettéosztása?

Hint mutatása A fejet tegyük az egyik, a rákövetkező elemet a másik oldalra (ha vannak ilyenek) és jöhet a rekurzív hívás. Ismét mintaillesztésben érdemes gondolkodni. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def split( list: IntList ): (IntList, IntList) = list match {
  //egy üres lista kettéosztva két üres lista lesz
  case Empty                            => (Empty, Empty) 

  //ha egyelemű a lista, akkor jöjjön vissza ő a bal és az üres lista a jobb oldalban
  case Cons(head, Empty)                => (list, Empty)  

  case Cons(first, Cons(second, tail) ) => {
    //szétosztjuk a tailt kettőbe
    val (left, right) = split( tail )
    //beszúrjuk az első és második elemet egyik ill. másik elé, és ezt a párt adjuk vissza
    ( Cons(first,left), Cons(second,right) )
  }
}
Ez a függvény viszont **nem logaritmikus mélységben** rekurzál! Minden hívásnál csak kettővel csökken a lista hossza, így kb negyvenezer elemnél már elszáll a call stackünk. Válasz mutatása

Hogyan tegyük tail rekurzívvá ezt a metódust? Nem probléma, ha a működése egy kicsit megváltozik.

Hint mutatása A `split`en belül deklarálhatunk egy helper metódust, ami **plusz két paraméterben** tárolja az eddigi elemek feldolgozásakor előállt két listát. A ,,kicsi változás'' az lesz, ha így tesszük, hogy a részlisták **elejére** kerülnek a **későbbi** elemek - de ez nem baj, ha nem kötelező tartsuk az eredeti sorrendet. (Akkor egyébként is problémákba ütköznénk a mergeléskor, logolnunk kéne az eredeti pozíciókat is magukon az elemeken kívül.) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def split( list: IntList ): (IntList, IntList) = {

  @tailrec
  def split( list: IntList, left: IntList, right: IntList ): (IntList, IntList) = list match {
    case Empty => (left, right)
    case Cons(head, Empty) => (Cons(head,left), right)
    case Cons(first, Cons(second, tail) ) => split(tail, Cons(first,left), Cons(second,right) )
  }

  split( list, Empty, Empty )
}
Válasz mutatása

Már csak a merge függvény hiányzik, mely két rendezett listát kell összefésüljön. Oldjuk meg mintaillesztéssel! Nem baj, ha elsőre nem tailrec.

Hint mutatása Itt érdemes if guardokat használni a matchben. Párra is lehet matchelni: a `(left, right) match { ... }` egy teljesen valid opció. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def merge( left: IntList, right: IntList ): IntList = (left, right) match {

  case (Empty, _) => right //ha a bal oldali lista üres, akkor mergelve őket a jobb oldalit kapjuk
  case (_, Empty) => left  //fordítva

  //különben mindkét listának van fejeleme => if guarddal össze tudjuk őket hasonlítani
  case ( Cons(leftHead, leftTail), Cons(rightHead, rightTail) ) if ( leftHead <= rightHead ) => 
    //ha a bal oldali a kisebb, levesszük, mergeljük a többit, eredmény elé kerül leftHead
    Cons( leftHead, merge( leftTail, right ) )

  //különben meg a jobb oldaliról vesszük le a fejelemet
  case ( _, Cons(rightHead, rightTail) ) => 
    Cons( rightHead, merge( left, rightTail ) )  
}
Válasz mutatása

Működni fog-e ez a fenti kód hosszú listára? Ha nem, alakítsuk át.

Hint mutatása Nem fog, a `merge` nem tail rekurzív és nem is csökkenti szignifikánsan az argumentumok méretét. Az átalakításnál a splithez hasonló trükk működhet, plusz egy lista bevezetésével, ahova az eddig feldolgozott fejelemekből építünk listát, de így fordítva fog felépülni a listánk, csökkenőbe rendezve! Hogy oldjuk ezt meg?
Válasz mutatása 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def merge( left: IntList, right: IntList ): IntList = {

  @tailrec
  def merge( left: IntList, right: IntList, result: IntList ): IntList = (left, right) match {

    //ha elfogytak az elemek
    case (Empty, Empty) => result

    //ha csak az egyik oldalról fogytak még el, nincs implementált ::: operátorunk,
    //meg el is rontaná a sorrendet, egyesével fűzzük fel őket
    case (Empty, Cons(head, tail) ) => merge( left, tail, Cons(head, result) )

    case (Cons(head, tail), Empty ) => merge( tail, right, Cons(head, result) )

    //különben mindkét listának van fejeleme => if guarddal össze tudjuk őket hasonlítani megnt
    case ( Cons(leftHead, leftTail), Cons(rightHead, rightTail) ) if ( leftHead <= rightHead ) => 
      //ha a bal oldali a kisebb, levesszük, mergeljük a többit, eredmény elé kerül leftHead
      merge( leftTail, right, Cons( leftHead, result ) )

    //különben meg a jobb oldaliról vesszük le a fejelemet
    case ( _, Cons(rightHead, rightTail) ) => 
      merge( left, rightTail, Cons( rightHead, result ) )
  }

  //ha meghívjuk, akkor fordítva építi fel a listát => de van reverse metódusunk
  merge( left, right, Empty).reverse
}

Kész is vagyunk. Ha eddig nem tettük, futtassunk le minden tesztet.

Utolsó frissítés: 2021-02-07 23:06:47