Writing quicksort in pkl

[EvgSkv]

Of course there is a built-in sorting method, but I was curious about implementing quicksort to try out pkl in scenarios more challenging than basic moving of vaues between fields.

Here is what I've got:

function QuickSort(l) = (
  if (l.length <= 1)
    l
  else 
    QuickSort(l.drop(1).filter((x) -> x <= l[0])) + l.take(1) +
    QuickSort(l.drop(1).filter((x) -> x > l[0]))
);

t = QuickSort(List(
  56, 877, 285, 575, 1000, 84, 774, 252, 131, 376, 30, 42,
  853, 165, 804, 988, 856, 938, 783, 627
  ))

And it works! 😄

I know this is not in-place, which is a major selling point of quicksort, but that's OK.

However it's unnatural to have such long expressions. Can we put them to a varibale?
Here is how I could make it work.

class QuickSortBody {
  rest: List;
  left: List;
  right: List;
  result: List;
}

function QuickSort(l) = (new QuickSortBody {
  when (l.length == 0) {
    result = List()
  } else {
    rest = l.drop(1)
    left = QuickSort(rest.filter((x) -> x <= l[0]))
    right = QuickSort(rest.filter((x) -> x > l[0]))
    result = left + List(l[0]) + right
  }
}).result

t = QuickSort(List(
  56, 877, 285, 575, 1000, 84, 774, 252, 131, 376, 30, 42,
  853, 165, 804, 988, 856, 938, 783, 627
  ))

I had to create a class, because if we do it without a class like this:

function QuickSort(l) = ({
  when (l.length == 0) {
    result = List()
  } else {
    rest = l.drop(1)
    left = QuickSort(rest.filter((x) -> x <= l[0]))
    right = QuickSort(rest.filter((x) -> x > l[0]))
    result = left + List(l[0]) + right
  }
}).result

t = QuickSort(List(
  56, 877, 285, 575, 1000, 84, 774, 252, 131, 376, 30, 42,
  853, 165, 804, 988, 856, 938, 783, 627
  ))

then we get a syntax error:

–– Pkl Error ––
No viable alternative at input `({`.

9 | function QuickSort(l) = ({
                             ^
at qs (file:///content/qs.pkl, line 9)

This seems like a bug in the parser, right?

Here is CoLab with the code.

Anyway, hope this exercise is interesting. Thanks to the team for working on this language!

[holzensp]

If you feed it large enough lists, you'll see why we don't recommend Pkl as a general purpose programming language, even though it is Turing Complete ;)

I know this is not in-place, which is a major selling point of quicksort, but that's OK.

This observation once lead Lennart Augustsson to write a wonderful blogpost on why QuickSort in Haskell really isn't and Conor McBride (if memory serves; I can't find the reference right now) to demonstrate that it is really Deforested Tree Sort (which your algorithm is as well).

The syntax error that you're seeing genuinely is a syntax error (although the error message leaves something to be desired). There is no expression in Pkl that starts with {. You mean to start an object there, which requires the new operator. However, because you immediately take result out, Pkl can't decide what you want a new of, so instead of ({ you want (new Dynamic {.

[EvgSkv]

Oh, thank you!

I tried doing new Object {}, didn't figure it should be new Dynamic {} :-)

This works!

function QuickSort(l) = (new Dynamic {
  when (l.length == 0) {
    result = List()
  } else {
    rest = l.drop(1)
    left = QuickSort(rest.filter((x) -> x <= l[0]))
    right = QuickSort(rest.filter((x) -> x > l[0]))
    result = left + List(l[0]) + right
  }
}).result

[odenix]

With the help of let and the excellent IntelliJ plugin, I eventually came up with this:

function QuickSort(l: List) =
  if (l.length < 2) l
  else
    let (first = l.first)
      let (rest = l.rest)
        let (left = QuickSort(rest.filter((x) -> x <= first)))
          let (right = QuickSort(rest.filter((x) -> x > first)))
            left + List(first) + right

t = QuickSort(List(
  56, 877, 285, 575, 1000, 84, 774, 252, 131, 376, 30, 42,
  853, 165, 804, 988, 856, 938, 783, 627
))

Pretty neat!

[holzensp]

As a tiny style nit; I'd not let (first = l.first); Pkl caches these things anyway, so there's no cost to evaluating l.first a hundred times, after the first time. It's very subjective, but I find the notational cost of the let expressions to exceed that of the inlined use.

[EvgSkv]

To me new in pkl feels like something from another world. So here I've got a version that doesn't use new:

function QuickSort(l) = ((null) {
  when (l.length == 0) {
    result = List()
  } else {
    rest = l.drop(1)
    left = QuickSort(rest.filter((x) -> x <= l[0]))
    right = QuickSort(rest.filter((x) -> x > l[0]))
    result = left + List(l[0]) + right
  }
}).result

t = QuickSort(List(
  56, 877, 285, 575, 1000, 84, 774, 252, 131, 376, 30, 42,
  853, 165, 804, 988, 856, 938, 783, 627
  ))

I.e. you can achive the same effect by extending null.

I'd be interested to hear from authors intuition on why is expression ({a=1}) disallowed for creating new dynamics? We can do essentially this when defining a module, but if the object is temporary, or enters a list, then we have to use a different notation involving new or null extension.

[odenix]

Not answering your question, but let is the right tool for the job here.

[4ozyCoder]

Tell me, when you wrote your code, did you use information about syntax only from the pkl documentation?😉

[odenix]

I started from OP’s code and was aware of let from reading the language reference (it’s quite common in expression-oriented languages). The IntelliJ plugin helped with the rest.

[4ozyCoder]

Thx