Instantly share code, notes, and snippets.

# fogus/scalatoprolog.md forked from jonifreeman/scalatoprolog.md Created Feb 1, 2012

What would you like to do?
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).
``````

``````?- 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

``````/* 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).
``````