Skip to content

Add benchmark for type-level bubble sort #21971

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
mbovel opened this issue Nov 18, 2024 · 0 comments
Open

Add benchmark for type-level bubble sort #21971

mbovel opened this issue Nov 18, 2024 · 0 comments

Comments

@mbovel
Copy link
Member

mbovel commented Nov 18, 2024

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants