scala / scala3

The Scala 3 compiler, also known as Dotty.
https://dotty.epfl.ch
Apache License 2.0
5.88k stars 1.06k forks source link

Add benchmark for type-level bubble sort #21971

Open mbovel opened 4 days ago

mbovel commented 4 days ago

Once the new benchmarks infrastructure is finished, add a benchmark for type-level bubble sort:

import scala.compiletime.ops.int.*

object TupleOps:
  import Tuple.*

  type Reduce[T <: NonEmptyTuple, F[_, _]] =
    Fold[Tuple.Tail[T], Tuple.Head[T], F]

  infix type Maximum[T <: NonEmptyTuple] = Reduce[
    T,
    [A, B] =>> (A, B) match
      case (Int, Int) => Max[A, B]
  ]

  type IndexOfRec[T <: Tuple, Elem, I <: Int] = Tuple.Elem[T, I] match
    case Elem => I
    case _    => IndexOfRec[T, Elem, I + 1]

  infix type IndexOf[T <: Tuple, Elem] = IndexOfRec[T, Elem, 0]

  type DropLargest[T <: NonEmptyTuple] =
    T IndexOf Maximum[T] match
      case Int =>
        Concat[Take[T, (T IndexOf Maximum[T])], Drop[T, (T IndexOf Maximum[T]) + 1]]

  type BubbleSort[T <: Tuple] = T match
    case EmptyTuple => EmptyTuple
    case NonEmptyTuple =>
      Concat[BubbleSort[DropLargest[T]], (Maximum[T] *: EmptyTuple)]

@main def main =
  println(compiletime.constValueTuple[(TupleOps.BubbleSort[(2, 3, 5, 4, 1)])])
  // (1,2,3,4,5)

Originally posted by @mbovel in #16463