The first time I saw this quicksort in Haskell was an eye opening moment,
qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)The first line reads: “When you sort an empty list (
[]), the result is another empty list”. The second line reads: “To sort a list whose first element is namedxand the rest of which is namedxs, sort the elements ofxsthat are less thanx, sort the elements ofxsthat are greater than or equal tox, and concatenate (++) the results, withxsandwiched in the middle.”
The code is so concise, yet clear (even with cryptic variable names like xs). The day my professor wrote it on the whiteboard was the first time I internalized that there might be something good about the alien world of functional programming.
The biggest revelation to me was, filter (< x) xs . It’s amazing that (< x) builds a temporary, unnamed, function equivalent to C++,
bool lessThanX(AnyOrderedType y){
return y < X;
}
//plus the definition of X somewhere...
Building a function! It’s still profound stuff to me. And clearly it really uses fewer lines of code. Amazingly, using list comprehension syntax is not more concise,
qsort (x:xs) = qsort [i | i <- xs, i < x] ++ [x] ++ qsort [i | i <- xs, i <= x]
compared to the original,
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
I hope this is an ah-ah moment for someone else too. I’d love to know what made you interested in functional programming; or if you know of a more elegant quicksort implementation.
This got me thinking. I haven’t touched Haskell, but I’ve studied both Scheme and Prolog. This was nicer than my scheme implementation: rather than implement filter, I just created
(greater x L)and(smaller x L). It always annoyed me that I had to pass through the list twice, though.(define (qsort L)
(define (qsort_ L1 L2)
(cond ((null? L1) L2)
(else (qsort_ (smaller (car L1) (cdr L1))
(cons (car L1) (qsort_ (bigger (car L1) (cdr L1)) L2))))))
(qsort_ L ‘()))
I did something cleverer to only visit the elements of the list once each time I needed to partition with my prolog sort:
qsort(List, Sorted):- qsort(List, [], Sorted),
qsort([], Sorted, Sorted).
qsort([H|Tail], OtherList, Sorted) :-
partition(H, Tail, L, G),
qsort(G, OtherList, Gs),
qsort(L, [H|Gs], Sorted).
The first one is a helper that takes two arguments, and sorts the first one into the second one using qsort/3.
The next line is a rough equivalent of saying that an empty list is sorted: the next argument is effectively an accumulator.
The final clause takes a non-empty list, and an already sorted accumulator, and sorts them. It partitions, and the recursively sorts the two halves.
(There’s also a naive version that appends sorted lists rather than using an accumulator, but that is not nearly as clever.)
The partition function is a little tricky:
partition(_, [], [], []).
partition(X, [X|List], L, G) :- partition(X, List, L, G).
partition(X, [E|List], [E|L], G) :- E < X, partition(X, List, L, G).
partition(X, [E|List], L, [E|G]) :- E > X, partition(X, List, L, G).
This states that an empty list partitions into two empty lists.
The second clause states that we strip out any duplicates of the pivot.
The final two clauses actually partition the list.
Granted, this isn’t quite as nice as the Haskell version, but for me, having this (and the Scheme solution detailed above) really switched me onto FP. We had previously coded quicksort and mergesort in Java (and I had then done the same in C, and Python, just for good measure), and the pure beauty of the code here compared to the vulgar mess of Java made me a fan.
Comment by Matt Schinckel — May 31, 2009 @ 4:06 am