Type-level merge sort in Scala

TypeLevelMergeSort.scala

// Implementation of a type-level merge sort that illustrate
// how to translate a Prolog program into a type-level computation

// Prolog:
// evenOdd([], [], []).
// evenOdd([A], [A], []).
// evenOdd([A, B | Tail], [A | TailEven], [B | TailOdd]) :-
//     evenOdd(Tail, TailEven, TailOdd).
// 
// split(Input, First, Second) :- evenOdd(Input, First, Second).
// 
// merge([], Second, Second).
// merge([FirstHead | FirstTail], [], [FirstHead | FirstTail]).
// merge([FirstHead | FirstTail], [SecondHead | SecondTail], [FirstHead |Merged]) :-
//     FirstHead =< SecondHead,
//     merge(FirstTail, [SecondHead |SecondTail], Merged).
// merge([FirstHead | FirstTail], [SecondHead | SecondTail], [SecondHead | Merged]) :-
//     FirstHead > SecondHead,
//     merge([FirstHead | FirstTail], SecondTail, Merged).
// 
// mergeSort([], []).
// mergeSort([A], [A]).
// mergeSort(Input, Sorted) :-
//     split(Input, First, Second),
//     mergeSort(First, FirstSorted),
//     mergeSort(Second, SecondSorted),
//     merge(FirstSorted, SecondSorted, Sorted).

import shapeless._
import shapeless.ops.nat._
import shapeless.nat._

trait EvenOdd[Input, Even, Odd]

object EvenOdd {
  // evenOdd([], [], []).
  implicit val emptyList = new EvenOdd[HNil, HNil, HNil] {}

  // evenOdd([A], [A], []).
  implicit def oneElement[A] = new EvenOdd[A :: HNil, A :: HNil, HNil] {}

  // evenOdd([A, B | Tail], [A | TailEven], [B | TailOdd]) :-
  //     evenOdd(Tail, TailEven, TailOdd).
  implicit def atLeastTwoElements[
      A,
      B,
      Tail <: HList,
      TailEven <: HList,
      TailOdd <: HList
  ](implicit
      ev: EvenOdd[Tail, TailEven, TailOdd]
  ): EvenOdd[A :: B :: Tail, A :: TailEven, B :: TailOdd] =
    new EvenOdd[A :: B :: Tail, A :: TailEven, B :: TailOdd] {}
}

trait Split[Input, First, Second]

object Split {
  // split(Input, First, Second) :- evenOdd(Input, First, Second).
  implicit def evenOddSplit[Input, First, Second](implicit
      ev: EvenOdd[Input, First, Second]
  ): Split[Input, First, Second] = new Split[Input, First, Second] {}
}

trait Merge[First, Second, Merged]

object Merge {
  // merge([], Second, Second)
  implicit def mergeFirstEmpty[Second] =
    new Merge[HNil, Second, Second] {}

  // merge([FirstHead | FirstTail], [], [FirstHead | FirstTail]).
  implicit def mergeSecondEmptyFirstNonEmpty[
      FirstHead <: Nat,
      FirstTail <: HList
  ] =
    new Merge[FirstHead :: FirstTail, HNil, FirstHead :: FirstTail] {}

  // merge([FirstHead | FirstTail], [SecondHead | SecondTail], [FirstHead |Merged]) :-
  //     FirstHead =< SecondHead,
  //     merge(FirstTail,[SecondHead|SecondTail],Merged).
  implicit def mergeLTeq[
      FirstHead <: Nat,
      FirstTail <: HList,
      SecondHead <: Nat,
      SecondTail <: HList,
      Merged <: HList
  ](implicit
      lteq: LTEq[FirstHead, SecondHead],
      ev: Merge[FirstTail, SecondHead :: SecondTail, Merged]
  ) =
    new Merge[
      FirstHead :: FirstTail,
      SecondHead :: SecondTail,
      FirstHead :: Merged
    ] {}

  // merge([FirstHead| FirstTail],[SecondHead| SecondTail],[SecondHead|Merged]) :-
  //     FirstHead > SecondHead,
  //     merge([FirstHead | FirstTail], SecondTail, Merged).
  implicit def mergeGT[
      FirstHead <: Nat,
      FirstTail <: HList,
      SecondHead <: Nat,
      SecondTail <: HList,
      Merged <: HList
  ](implicit
      gt: GT[FirstHead, SecondHead],
      ev: Merge[FirstHead :: FirstTail, SecondTail, Merged]
  ) =
    new Merge[
      FirstHead :: FirstTail,
      SecondHead :: SecondTail,
      SecondHead :: Merged
    ] {}
}

trait MergeSort[Input, Sorted]

object MergeSort {
  // mergeSort([], []).
  implicit def sortEmpty = new MergeSort[HNil, HNil] {}

  // mergeSort([A], [A]).
  implicit def sortOne[A] = new MergeSort[A :: HNil, A :: HNil] {}

  // mergeSort(Input, Sorted) :-
  //     split(Input, First, Second),
  //     mergeSort(First, FirstSorted),
  //     mergeSort(Second, SecondSorted),
  //     merge(FirstSorted, SecondSorted, Sorted).
  implicit def sortAtLeastTwo[
      Input,
      FirstSplit,
      SecondSplit,
      FirstSplitSorted,
      SecondSplitSorted,
      Sorted
  ](implicit
      split: Split[Input, FirstSplit, SecondSplit],
      firstSorted: MergeSort[FirstSplit, FirstSplitSorted],
      secondSorted: MergeSort[SecondSplit, SecondSplitSorted],
      merge: Merge[FirstSplitSorted, SecondSplitSorted, Sorted]
  ) = new MergeSort[Input, Sorted] {}
}

import scala.reflect.runtime.universe._

def typelevelSort[Input, Output](input: Input)(implicit
    ev: MergeSort[Input, Output],
    typeTag: TypeTag[Output]
): String = typeTag.toString

typelevelSort(_4 :: _2 :: _1 :: _3 :: _3 :: _7 :: HNil)