I was thinking about what would make the list, and I couldn't come up with a complete list of topics, and two of those topics -- sorting and searching -- are a kind of black magic. Quicksort is a marvelously simple algorithm, but it's so easy to get wrong that the standard approach is to use a library implementation, or, in a worst case scenario, copy code out of a good textbook (ideally Knuth). Writing a
quicksort function from memory is almost certainly a way to introduce bugs into a program. Searching a sorted binary tree is less error prone, but still one of those algorithms that's best to reuse or copy instead of writing from memory.Why is this? Why are there fundamental ideas in computing that are best reused from a library or copied out of a textbook?
I'm not a chemist, nor am I a physicist, but I still remember a great deal from my high school chemistry and physics classes. Certain parts of the periodic table are deeply imprinted in my brain, as are Newton's laws of motion (and the calculus that relates position to velocity to acceleration). Yet there is something so complicated about quicksort and binary search that it's best not to write it down on a cocktail napkin.
Something is wrong here. The basic ideas in a profession should be so, um, basic that any professional should be able to recite them from memory on demand.
The problem isn't so much that these ideas are so arcane that they should come from a textbook whenever they are used. The problem is that our expression of these simple ideas is overly complex.
Here is a simple expression of C.A.R. Hoare's quicksort that's simple and easy to understand (optimized for clarity):
Or, optimized for terseness:qsort [] = []
qsort (x:xs) = (qsort lesser) ++ [x] ++ (qsort greater)
where
lesser = filter (< x) xs
greater = filter (>= x) xs
The problem with quicksort isn't that it's a fundamentally difficult algorithm to understand. As expressed here, the algorithm is quite simple (and fits on a cocktail napkin). As it is typically expressed in a language like C, it is optimized to have an additional property: it sorts the array in place. The typical Haskell version doesn't offer this property, but at least it highlights the algorithm, not the mechanics needed to support the typical optimization.qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x]
++ [x]
++ qsort [y | y <- xs, y >= x]
For more details, see the discussion on the Haskell wiki, which includes a canonical implementation in C for comparison.
Another classic algorithm is a search within a sorted binary tree. Binary trees are another foundation in computing that are frequently more complicated than they should be. Here is a definition that is simple, obvious and easy to remember:
data Tree a = Empty | Node (Tree a) a (Tree a)Performing a binary search on this structure should be simple, and it is:
A quick google turned up a gem from Ralf Hinze: Functional Pearl: A fresh look at binary search trees (JFP, November 2002). Ralf's paper also discusses the other necessary algorithms for dealing with binary trees: insertion, deletion, and balancing.bsearch _ Empty = False
bsearch p (Node l a r)
| p < a = bsearch p l
| p == a = True
| p > a = bsearch p r
Snippets like this are one of the reasons why I like Haskell so much. As I was driving around today, I wondered how I would write a binary search, when I visualized these two snippets of Haskell pretty much as you see them here. This is certainly something I would never do if I were still thinking in C, because the pointer manipulation and memory management issues obscure the intent behind a binary search as to render it unrecognizable.
Now I'm wondering how many fundamental, yet "complex and error prone" concepts can be expressed with a screenful of Haskell.
9 comments:
Ok, I like your post.
However, as neat and concise as the haskell code snippet for the tree is, it does make me wonder what layer of abstraction there is in Haskell. Is the tree automagically weighted? When? What are the conditions of the balancing etc?
I like my C/C++ and even Java for allowing me more control over my data-structures - even the libraries often give you sufficient flexibility.
As you were optimising for terseness, did you intend to optimise in a bug at the same time? [y | y = x] should be [y | y >= x]. (I guess it does demonstrate your point, though... and I'd also like to thank you for demonstrating that a Haskell program can be buggy and still type-check just fine!)
But it's also worth noting a few other points:
. This implementation of qsort has a horrid worst-case (nearly sorted lists); that can be improved by better pivot choice, but doing so introduces an additional layer of complexity - and the risk of more bugs
. In languages where recursion is expensive or limited, qsort usually gets rewritten iteratively, which is a really great way to introduce bugs to any algorithm
. qsort's main strength is that it sorts in-place; if that's not required, mergesort has slightly better overall performance, and doesn't have the nasty worst-case behaviour - and is even simpler to implement
. Trying to solve all of those in Haskell would probably result in an implementation significantly larger, more complicated and more error-prone than the existing one, just as it would in any other language; likewise, this "naive" implementation can be expressed as concisely in many other languages as it can in Haskell
. In any case, the fundamental idea is NOT any particular implementation of sorting, nor even sorting itself - but the recursive, divide-and-conquer approach to algorithm design, of which decent sorting and bsearch algorithms happen to be really good examples
Nice essay! I agree that quicksort is especially elegant in Haskell.
Once, just for kicks, I wrote a destructive quicksort in Haskell using the ST monad to encapsulate local state inside of a pure function.
I haven't posted it, though, because some programs are just too vile to unleash upon the world.
Quicksort is a specific example of a problem that can be solved using the fundamental ideas, like the pendulum or hydrogen atom problems in physics. If you're interested in the fundamental ideas of computing that are more analagous to high level concepts like Newton's laws, read the Computational Thinking site at CMU or read Peter Denning's Great Principles of Computing. Computing is an infant field compared to physics, so these ideas are a long way from their final forms, but at least we're starting to think about them.
The reason that we don't memorize "basic" algorithms has nothing to do with C versus Haskell. It rather has to do with the fact that the responsibility of programmers is to reuse code. In a perfect world of code reuse and interoperability, quick sort would have been written exactly once and included by reference forever after.
If I had to write Quicksort in every program I had ever written that had sorting, you can bet I'd have it memorized character for character, whether programming in Haskell, C, or assembly language.
Think of it this way: how well would people remember their multiplication tables if every test they ever took allowed calculators? Computer programmers are both calculator users and calculator builders. So we'll never be good at memorizing things. We make the tools that allow people to forget. There is no reason to be ashamed of that.
You did not mention function application. I would consider function application *the* fundamental concept of CS, perhaps it's only equal being boolean algebra.
While it's true that those are very elegant and accurate implementations of those two classic algorithms, the quicksort algorithm isn't one that you would want to use on very large lists, at least according to this Haskell wiki.
Their most efficient, unstable quicksort is still considerably more readable than any C implementation I've seen, but it is more complicated and further removed from the essence of quick-sort.
Very nice post: captures my own sentiments exactly.
However, this "optimized for terseness" seemed like a bit of a challenge! Surely it could use a bit more work to abstract out the common code:
qsort [] = []
qsort (x:xs) = rec (<) ++ x : rec (>=)
where rec (#) = qsort (filter (#x) xs)
Or even more terse (and I hesitate to post this publicly, but it does kinda take me back to my APL days):
q[]=[];q(x:y)=(\r->r(<)++x:r(>=))(\(#)->q(filter(#x)y))
Ouch! Sorry ... :) !
(Note that the where clause in the first example should be indented, I just can't get blogger to allow code or pre tags ... .)
I would consider Decidability to be the fundamental idea of the theory of computation.
Remember that questions about the nature of computation arose from the attempts to answer mathematical problems, where it was wondered first "How can we prove theorems?" and then later "Can we prove this theorem at all?"
When suitably formalized, the question can be expressed in terms of set or language membership: Does a string belong in a language or not?
Exploration of the mechanical process by which such a question may be decided (or not be capable of decision) became the basis for the theory of computation.
Post a Comment