Looks like the Java (balls to the walls DSL) I write when I’m just writing Java to have fun.
It misses the point though that it takes a handful of lines to write Quicksort in a functional programming language as opposed to 50 or so lines in BASIC or FORTRAN 77. Of course most of us these days aren’t old enough to remember writing a Quicksort in languages like that and might not appreciate the difference but you might as well code it in assembly language as in an old language that doesn’t support recursion.
The entire point of quicksort is that it doesn't allocate and its inner loop is very tight (especially if you don't use Lomuto partitioning -- they teach Lomuto partitioning in school because the proof of correctness is easier).
Writing it in the naive functional-like style is fun and instructive, but it doesn't quite strike at the heart of what quicksort is about.
It's an example of an instance where the functional setting makes it harder to reason about the program.
A couple of months ago I was playing around with a similar technique, Mogensen-Scott encoding, in typescript. I was mainly interested in it as a way to express sum types without a bunch of if statements (instead a "value" of a type takes functions for each possible case branch and calls the appropriate one).
I ended up writing a little dependent type checker:
Wow, I didn't know about that. Nice to see more things about lambda calculus, I think it is the most beautiful thing in computer science, but I haven't studied it too deeply as I need to prioritize other things...
Considering that list comprehensions can be replaced by maps and filters, and they can replaced by reduces, maybe we can ever go further in that craziness and do it only using reduces!
11 comments
[ 3.3 ms ] story [ 40.9 ms ] threadIt misses the point though that it takes a handful of lines to write Quicksort in a functional programming language as opposed to 50 or so lines in BASIC or FORTRAN 77. Of course most of us these days aren’t old enough to remember writing a Quicksort in languages like that and might not appreciate the difference but you might as well code it in assembly language as in an old language that doesn’t support recursion.
Writing it in the naive functional-like style is fun and instructive, but it doesn't quite strike at the heart of what quicksort is about.
It's an example of an instance where the functional setting makes it harder to reason about the program.
I ended up writing a little dependent type checker:
https://gist.github.com/dunhamsteve/1be0cbb346d75ee1be8f67d1...