How to implement a generic sorting function?

[TheLostLambda]

Just started with Koka this evening, so likely a lot of room for improvement, but I as I understand this sort of thing is best done using some of those implicit parameters?

Here is what I have so far (mostly copied from the Koka tests, where they are specialized to int32):

fun sort(xs : list<a>) : pure list<a>
  quicksort(xs, Nil)

fun quicksort(xs : list<a>, res : list<a>) : pure list<a>
  match(xs)
    Cons(x, xx) ->
      val (lo, hi) = qpartition(x, xx)
      quicksort(lo, Cons(x, quicksort(hi, res)))
    Nil -> res

fun qpartition(^x : a, ys : list<a>, ?(<): (a, a) -> bool) : (list<a>, list<a>)
  match(ys)
    Cons(y, yy) ->
      if(y < x) then
        val (lo, hi) = qpartition(x, yy)
        (Cons(y, lo), hi)
      else
        val (lo, hi) = qpartition(x, yy)
        (lo, Cons(y, hi))
    Nil -> (Nil, Nil)

And the error I'm struggling with (line numbers wrong here, since there is other stuff in that file):

day01.kk(23,38): type error: cannot resolve implicit parameter
  context   :                      qpartition(x, xx)
  parameter : ?(<) : ($170, $170) -> bool
  candidates: ...
  hint      : add a (implicit) parameter to the function signature?

EDIT: That pure really only needs to be a div, but I don't reckon that should really be needed for a sorting function either... Let me know if you have any clever ideas about how to get rid of that as well!

[TimWhiting]

import std/core/undiv

fun sort(xs : list<a>, ?(<): (a, a) -> bool) : list<a>
  quicksort(xs, Nil)

fun quicksort(xs : list<a>, res : list<a>, ?(<): (a, a) -> bool) : list<a>
  match(xs)
    Cons(x, xx) ->
      val (lo, hi) = qpartition(x, xx)
      quicksort(lo.pretend-decreasing, Cons(x, quicksort(hi.pretend-decreasing, res)))
    Nil -> res

fun qpartition(^x : a, ys : list<a>, ?(<): (a, a) -> bool) : (list<a>, list<a>)
  match(ys)
    Cons(y, yy) ->
      if(y < x) then
        val (lo, hi) = qpartition(x, yy)
        (Cons(y, lo), hi)
      else
        val (lo, hi) = qpartition(x, yy)
        (lo, Cons(y, hi))
    Nil -> (Nil, Nil)
  
fun main()
  [3,1,4,6,356324,123,3532324].sort()

This should work. Implicit parameters need to be explicitly propagated until they can be statically determined. In this case since quicksort and sort are also polymorphic, the implicit parameter needs to be there as well.

As far as div is concerned, you can use the std/core/undiv library to pretend that a function is not divergent. One simple way is to mark one parameter as a decreasing parameter (one that always gets smaller), then the Koka divergence analysis can dismiss the divergence effect.

[TheLostLambda]

Thanks a ton for the swift reply!

That looks like a nice way to do things! It's a shame the compiler needs to be told that the function isn't div, but it's nice to know that there is a workaround for the moment!

I'll use the community-std version for the time being, then we can hopefully get something into std proper eventually! #610