Instantly share code, notes, and snippets.

# jonifreeman/scalatoprolog.md Created Jan 30, 2012

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

### milessabin commented Jan 30, 2012

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

### loverdos commented Jan 30, 2012

 !!!! You certainly got @dcsobral very excited: https://twitter.com/#!/dcsobral/status/163968981059899392
Owner

### jonifreeman commented Jan 30, 2012

 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) } } } ``````