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
quicksortfunction 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)
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]
++ 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:
That is, a tree is a node with a value and two sub-trees, or it is an empty node. Let's assume that the contents of a tree are always in sorted order. That is, the left subtree contains nodes that are strictly smaller than the current node, and the right subtree contains nodes that are strictly greater than (or equal to) the current node.
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.