Scala program for my CS 113 class that generates tracing for QuickSort in HW #14

hw14_2.scala

import cats._, cats.data._, cats.syntax.all._
import scala.annotation.tailrec

object Main2 {
  
  sealed trait Trace {
    def show: String
  }
  object Trace {
    implicit val showTrace: Show[Trace] = Show.show(_.show)
  }
  case class Sort[A: Show](vector: Vector[A], start: Int, end: Int) extends Trace {
    override def show: String = s"sort(${vector.mkString_("[", ", ", "]")}, $start, $end)"
  }
  case class PivotIndex(ind: Int) extends Trace {
    override def show: String = s"pivIndex: $ind"
  }
  case class Table[A: Show](vector: Vector[A]) extends Trace {
    override def show: String = s"table: ${vector.mkString_("[", ", ", "]")}"
  }

  def main(args: Array[String]): Unit = {
    val vector: Vector[Int] = Vector(55, 50, 10, 40, 80, 90, 60, 100, 70, 80, 20, 50, 22)
    val traces = sort[Int].runL((), vector).value
    println(traces.mkString_("\n"))
  }

  def sort[A: PartialOrder : Show]: ReaderWriterState[Unit, Vector[Trace], Vector[A], Unit] =
    ReaderWriterState.get[Unit, Vector[Trace], Vector[A]].flatMap { vector =>
      quickSort[A](0, vector.size - 1)
    }

  def quickSort[A: PartialOrder : Show](start: Int, end: Int): ReaderWriterState[Unit, Vector[Trace], Vector[A], Unit] = {
    val entry = ReaderWriterState.get[Unit, Vector[Trace], Vector[A]].flatMap(vector => ReaderWriterState.tell(Vector(Sort(vector, start, end))))
    if(start < end) {
      entry >> (for {
        pivIndex <- partition[A](start, end)
        _ <- ReaderWriterState.tell[Unit, Vector[Trace], Vector[A]](Vector(PivotIndex(pivIndex)))
        _ <- quickSort(start, pivIndex - 1)
        _ <- quickSort(pivIndex + 1, end)
      } yield ())
    } else {
      entry
    }
  } >> ReaderWriterState.get[Unit, Vector[Trace], Vector[A]].flatMap(vector => ReaderWriterState.tell(Vector(Table(vector))))

  def partition[A: PartialOrder](first: Int, last: Int): ReaderWriterState[Unit, Vector[Trace], Vector[A], Int] =
    ReaderWriterState {
      case ((), vector) =>
        val pivot = vector(first)

        @tailrec def go(vec: Vector[A], up: Int = first, down: Int = last): (Vector[A], Int, Int) = {
          var tUp = up
          while(tUp < last && vec(tUp) <= pivot) tUp += 1
          val nUp = tUp

          var tDown = down
          while(tDown > first && vec(tDown) > pivot) tDown -= 1
          val nDown = tDown

          if(nUp < nDown) {
            go(vec.updated(nUp, vec(nDown)).updated(nDown, vec(nUp)))
          } else {
            (vec, nUp, nDown)
          }
        }

        val (result, up, down) = go(vector, first, last)

        (Vector(), result.updated(first, result(down)).updated(down, result(first)), down)
    }

}