Skip to content

Instantly share code, notes, and snippets.

@Pet3ris
Forked from jonifreeman/scalatoprolog.md
Created September 15, 2012 16:33
Show Gist options
  • Save Pet3ris/3728718 to your computer and use it in GitHub Desktop.
Save Pet3ris/3728718 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).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment