Skip to content

Instantly share code, notes, and snippets.

@jonifreeman
Created January 30, 2012 09:16
Show Gist options
  • Save jonifreeman/1703501 to your computer and use it in GitHub Desktop.
Save jonifreeman/1703501 to your computer and use it in GitHub Desktop.
Scala type system -> Prolog

Miles Sabin implemented a nice selection sort example in Scala's type system. See:

http://www.chuusai.com/2012/01/27/type-level-sorting-in-shapeless/

To get a better understanding how that works I ported the algorithm to Prolog.

selectleast([H|T], TM, [H|TRem]):-
    selectleast(T, TM, TRem), TM < H.

selectleast([H|T], H, T).

selectionsort(L, [M|ST]):-
    selectleast(L, M, Rem), selectionsort(Rem, ST).

selectionsort(S, S).

To test it use a Prolog interpreter:

?- selectleast([3, 1, 4, 0, 2, 5], H, T).
H = 0,
T = [3, 1, 4, 2, 5] .

?- selectionsort([3, 1, 4, 0, 2, 5], Sorted).
Sorted = [0, 1, 2, 3, 4, 5] .

The implementation is perhaps not very idiomatic Prolog code but that's not the point. The nice thing is that the translation from Scala type system syntax is completely straightforward.

Breakdown

Let's start with SelectLeast rule and convert it to Prolog.

/* hlistSelectLeast3(implicit tsl : SelectLeast[T, TM, TRem], ev : TM < H): SelectLeast[H :: T, TM, H :: TRem] */

==>

selectleast([H|T], TM, [H|TRem]):-
    selectleast(T, TM, TRem), TM < H.

The return type of 'hlistSelectLeast3' is rule's head. The implicit parameters are the predicates. Lower priority 'hlistSelectLeast1' is simply a Prolog fact.

/* hlistSelectLeast1: SelectLeast[H :: T, H, T] */

==>

selectleast([H|T], H, T).

SelectionSort is converted in a same way.

/* hlistSelectionSort2(implicit sl : SelectLeast[L, M, Rem], sr : SelectionSort[Rem, ST]): SelectionSort[L, M :: ST] */

==>

selectionsort(L, [M|ST]):-
    selectleast(L, M, Rem), selectionsort(Rem, ST).

/* hlistSelectionSort1: SelectionSort[S, S] */

==>

selectionsort(S, S).
@milessabin
Copy link

Out of interest ... suppose you started from the idiomatic Prolog and worked back to a Scala implementation ... would it look any different?

@loverdos
Copy link

@jonifreeman
Copy link
Author

Miles, I did a little bit Prolog some 15 years ago. So please take my view on what is idiomatic and what is not with a grain of salt :) I think some folks would prefer to make non-recursive cases more explicit. As in this implementation:

selectleast([X], X, []).

selectleast([H|T], H, [TM|TRem]):-
    selectleast(T, TM, TRem), TM > H.

selectleast([H|T], TM, [H|TRem]):-
    selectleast(T, TM, TRem), TM < H.

selectionsort([], []).

selectionsort(L, [M|ST]):-
    selectleast(L, M, Rem), selectionsort(Rem, ST).

That translates to following Shapeless code (seems to work without prioritizing the implicits, I added GT to my Shapeless build):

object SelectLeast {
  implicit def hlistSelectLeast1[H <: Nat] =
    new SelectLeast[H :: HNil, H, HNil] {
      def apply(l : H :: HNil) : (H, HNil) = (l.head, l.tail)
    }

  implicit def hlistSelectLeast2[H <: Nat, T <: HList, TM <: Nat, TRem <: HList]
    (implicit tsl : SelectLeast[T, TM, TRem], ev : TM > H) =
      new SelectLeast[H :: T, H, TM :: TRem] {
        def apply(l : H :: T) : (H, TM :: TRem) = {
          val (tm, rem) = tsl(l.tail)
          (l.head, tm :: rem)
        }
      }

  implicit def hlistSelectLeast3[H <: Nat, T <: HList, TM <: Nat, TRem <: HList]
    (implicit tsl : SelectLeast[T, TM, TRem], ev : TM < H) =
      new SelectLeast[H :: T, TM, H :: TRem] {
        def apply(l : H :: T) : (TM, H :: TRem) = {
          val (tm, rem) = tsl(l.tail)
          (tm, l.head :: rem)
        }
      }
}

object SelectionSort {
  implicit def hlistSelectionSort1 = new SelectionSort[HNil, HNil] {
    def apply(l : HNil) : HNil = l
  }

  implicit def hlistSelectionSort2[L <: HList, M <: Nat, Rem <: HList, ST <: HList]
    (implicit sl : SelectLeast[L, M, Rem], sr : SelectionSort[Rem, ST]) =
      new SelectionSort[L, M :: ST] {
        def apply(l : L) = {
          val (m, rem) = sl(l)
          m :: sr(rem)
        }
      }
}

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