Programming Languages 2020/21 fall

Scala kogumi implementeerimine

Selles praktikumis implementeerime oma järjekorra (queue) kogumi, mis on funktsionaalne ja immutable, ja lisame selle Scala kogumite hierarhiasse.

Kasutame järgmisi import-e, et hiljem kogemata vale AbstractSeq jm ei impordiks.

import scala.collection.{IterableFactoryDefaults, SeqFactory, mutable}
import scala.collection.immutable.{AbstractSeq, LinearSeq, LinearSeqOps}

Defineerime järgmise liidesega järjekorra operatsioonid:

trait JärjekordOps[+A, +CC[_], +C] {
  def onTühi: Boolean
  def lisaLõppu[B >: A](elem: B): CC[B]
  def võtaAlgusest: (A, C)
}

Selle tüübiparameetrid on samasugused nagu Scala kogumite liidestel.

Järjekorra operatsioonide implementeerimine

Kõigepealt implementeerime lihtsa järjekorra andmestruktuuri, mis realiseerib eelmist liidest. Funktsionaalset järjekorda esitame kahe standardse listiga, et kõik järjekorra operatsioonid oleksid efektiivsed.

case class Järjekord[+A](private val algus: List[A], private val lõpp: List[A])
  extends JärjekordOps[A, Järjekord, Järjekord[A]] {

  override def onTühi: Boolean = ???

  override def lisaLõppu[B >: A](elem: B): Järjekord[B] = ???

  override def võtaAlgusest: (A, Järjekord[A]) = ???
}

object TestJärjekord1 {
  def main(args: Array[String]): Unit = {
    val a = Järjekord[Int](List(), List())
    assert(a.onTühi)
    val a2 = a.lisaLõppu(1)
    assert(!a2.onTühi)
    assert(a2 == Järjekord(List(), List(1)))

    val b = Järjekord(List(1, 2, 3), List(6, 5, 4))
    val b2 = b.lisaLõppu(7)
    assert(b2 == Järjekord(List(1, 2, 3), List(7, 6, 5, 4)))

    val (x1, c1) = b.võtaAlgusest
    assert(x1 == 1)
    assert(c1 == Järjekord(List(2, 3), List(6, 5, 4)))
    val (x2, c2) = c1.võtaAlgusest
    assert(x2 == 2)
    assert(c2 == Järjekord(List(3), List(6, 5, 4)))
    val (x3, c3) = c2.võtaAlgusest
    assert(x3 == 3)
    assert(c3 == Järjekord(List(), List(6, 5, 4)))
    val (x4, c4) = c3.võtaAlgusest
    assert(x4 == 4)
    assert(c4 == Järjekord(List(5, 6), List()))
  }
}

Companion objekti lisamine

Järjekordade mugavamaks loomiseks lisame eelmisele klassile companion objekti.

object Järjekord {
  def apply[A](xs: A*): Järjekord[A] = ???
}

object TestJärjekord2 {
  def main(args: Array[String]): Unit = {
    val a = Järjekord[Int]()
    assert(a == Järjekord[Int](List(), List()))

    val b = Järjekord(1, 2, 3, 4, 5, 6)
    assert(b == Järjekord(List(1, 2, 3, 4, 5, 6), List()))
  }
}

Seq implementeerimine LinearSeq kaudu

Täiendame oma järjekorda, et see oleks Scala järjenditüüp, st realiseeriks Seq liidest. Antud juhul on kõige lihtsam implementeerida selle alamliidese LinearSeq meetodid isEmpty, head ja tail. Nende kaudu on LinearSeq-is defineeritud järjendi jaoks vajalik iterator, mille tulemusena saame oma järjekorra andmestruktuuril kasutada kõiki Scala järjendite meetodeid ilma neid ise implementeerimata.

case class Järjekord[+A](private val algus: List[A], private val lõpp: List[A])
  extends AbstractSeq[A] // lisatud
    with LinearSeq[A] // lisatud
    with JärjekordOps[A, Järjekord, Järjekord[A]] {

  // eelnevad onTühi, lisaLõppu, võtaAlgusest

  override def isEmpty: Boolean = ???

  override def head: A = ???

  override def tail: Järjekord[A] = ???

  override def toString: String = s"Järjekord($algus,$lõpp)"
}

object TestJärjekord3 {
  def main(args: Array[String]): Unit = {
    val a = Järjekord(6, 7, 8, 9)

    assert(a.head == 6)
    assert(a.tail == Järjekord(7, 8, 9))
    assert(a.tail.tail == Järjekord(8, 9))

    assert(a.forall(_ < 10))
    assert(!a.forall(_ < 7))
    assert(a.exists(_ == 7))
    assert(!a.exists(_ == 5))

    assert(5 +: a == Järjekord(5, 6, 7, 8, 9))
    assert(a :+ 10 == Järjekord(6, 7, 8, 9, 10))

    assert(a.reverse == Järjekord(9, 8, 7, 6))
    assert(a.map(_ + 10) == Järjekord(16, 17, 18, 19))
  }
}

Seq implementeerimine üldkujul

Üldjuhul Seq liidese implementeerimiseks pole LinearSeq kõige efektiivsem viis. Kuigi siin pole see otseselt vajalik, harjutame ka üldjuhul Seq implementeerimist, milleks on vaja defineerida length, apply ja iterator.

case class Järjekord[+A](private val algus: List[A], private val lõpp: List[A])
  extends AbstractSeq[A]
    with LinearSeq[A]
    with JärjekordOps[A, Järjekord, Järjekord[A]] {

  // eelnevad onTühi, lisaLõppu, võtaAlgusest
  // eelnevad isEmpty, head, tail, toString

  override def length: Int = ???

  override def apply(i: Int): A = ???

  override def iterator: Iterator[A] = ???
}

object TestJärjekord4 {
  def main(args: Array[String]): Unit = {
    val b = Järjekord(List(1, 2, 3), List(6, 5, 4))
    assert(b.length == 6)
    assert(b(0) == 1)
    assert(b(1) == 2)
    assert(b(2) == 3)
    assert(b(3) == 4)
    assert(b(4) == 5)
    assert(b(5) == 6)

    //val c: Järjekord[Int] = b.map(_ + 10) // tulemus vale tüüpi
  }
}

Seq meetodite tagastustüübi täpsustamine

Eelmistest testidest võib märgata, et meie järjekorra map, +:, :+ jt meetodid ei tagasta Järjekord-a vaid hoopis LinearSeq-i. Selle parandamiseks peame eelmise lihtsa compation objekti asendama keerukama SeqFactory implementatsiooniga, et andmestruktuuri tagastavad meetodid oskaks meie defineeritud Järjekord isendeid luua.

case class Järjekord[+A](private val algus: List[A], private val lõpp: List[A])
  extends AbstractSeq[A]
    with LinearSeq[A]
    with LinearSeqOps[A, Järjekord, Järjekord[A]] // lisatud
    with IterableFactoryDefaults[A, Järjekord] // lisatud
    with JärjekordOps[A, Järjekord, Järjekord[A]] {

  // eelnevad onTühi, lisaLõppu, võtaAlgusest
  // eelnevad isEmpty, head, tail, toString
  // eelnevad length, apply, iterator

  override def iterableFactory: SeqFactory[Järjekord] = Järjekord
}

object Järjekord extends SeqFactory[Järjekord] {
  override def from[A](source: IterableOnce[A]): Järjekord[A] = ???

  override def empty[A]: Järjekord[A] = ???

  override def newBuilder[A]: mutable.Builder[A, Järjekord[A]] = new mutable.Builder[A, Järjekord[A]] {
    private var list = List[A]()

    override def clear(): Unit = ???

    override def result(): Järjekord[A] = ???

    override def addOne(elem: A): this.type = {
      ???
      this
    }
  }
}

object TestJärjekord5 {
  def main(args: Array[String]): Unit = {
    val b = Järjekord(List(1, 2, 3), List(6, 5, 4))
    val c: Järjekord[Int] = b.map(_ + 10) // tulemus õiget tüüpi
    assert(c == Järjekord(11, 12, 13, 14, 15, 16))
  }
}

Seq meetodite optimeerimine

Kuigi nüüd on nende meetodite tagastustüübid õiged, siis pole nende vaikimisi implementatsioonid kõige efektiivsemad. Näiteks +: ja :+, mis lisavad elemendi algusesse või lõppu, kopeerivad äsjadefineeritud SeqFactory abil ümber kogu järjendi, selle asemel, et järjekorra sisemisi liste otse muuta.

Nende optimeerimiseks saame ise defineerida mõistlikumad prepended ja appended meetodid. Lisaks saame defineerida paremini reverse, map, forall ja exists.

case class Järjekord[+A](private val algus: List[A], private val lõpp: List[A])
  extends AbstractSeq[A]
    with LinearSeq[A]
    with LinearSeqOps[A, Järjekord, Järjekord[A]]
    with IterableFactoryDefaults[A, Järjekord]
    with JärjekordOps[A, Järjekord, Järjekord[A]] {

  // eelnevad onTühi, lisaLõppu, võtaAlgusest
  // eelnevad isEmpty, head, tail, toString
  // eelnevad length, apply, iterator
  // eelnev iterableFactory

  override def appended[B >: A](elem: B): Järjekord[B] = ???

  override def prepended[B >: A](elem: B): Järjekord[B] = ???

  override def reverse: Järjekord[A] = ???

  override def map[B](f: A => B): Järjekord[B] = ???

  override def forall(p: A => Boolean): Boolean = ???

  override def exists(p: A => Boolean): Boolean = ???
}