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 sumhoz 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 toStringje 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.

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 spliten 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