Re:Lambdasort: Quicksort written in Python only using lambdas
by dunham on Tuesday January 02, 2024 @07:37PM
(#38849194)
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:
Re:Lambdasort: Quicksort written in Python only using lambdas
by lucasoshiro on Wednesday January 03, 2024 @05:47PM
(#38860894)
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...
Re:Lambdasort: Quicksort written in Python only using lambdas
by PaulHoule on Tuesday January 02, 2024 @07:11PM
(#38849010)
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.
Re:Lambdasort: Quicksort written in Python only using lambdas
by qsort on Tuesday January 02, 2024 @08:07PM
(#38849424)
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.
Re:Lambdasort: Quicksort written in Python only using lambdas
by lucasoshiro on Wednesday January 03, 2024 @05:42PM
(#38860846)
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!
I ended up writing a little dependent type checker:
https://gist.github.com/dunhamsteve/1be0cbb346d75ee1be8f67d1...
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.
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.