Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Forward Is Not Enough
You know what I don't like? Emperors clad in boxers. Consider:
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x]
++ qsort (filter (>= x) xs)
Code like the above has been used up and down the tubes to demonstrate the superiority of functional languages. It's a functional-style quicksort written in Haskell that can be understood, at least according to some, without any prior exposure. First line: qsort of the empty list is the empty list. Second line (broken to fit in a narrow space): qsort for a list starting with x followed by some more xs is a concatenation ('++') of three lists: all stuff in xs that's smaller than x sorted, x itself, and all stuff in xs that's greater than or equal to x, again sorted. Try defining quicksort in two lines in your Blub language!
As much as I like Haskell, I look at that example with a mix of admiration and indignation, same as I'd look at an example illustrating C's virtues by means of a buffer overrun exploit. Both cases inspire awe, but I think they illustrate something bad rather than something good, and I could never bring myself to write or use that kind of trick.
There are a few things about qsort that don't quite cut the mustard. For starters, qsort is not really quicksort. Quicksort, as defined by Hoare in his seminal paper [8], is an in-place algorithm. Hoare's in-place partition is his paper's main contribution and a quintessential part of quicksort. qsort is not in-place, so it could be at best considered an exercise inspired by quicksort. (And not a great exercise at that. It does so much ancillary work it's not even funny—did you think that those two passes through the list and all those concatenations come for free?) Second, qsort makes a patently bad choice of pivot by selecting the first element of the sequence, thus nicely guaranteeing quadratic performance for almost sorted data. And the thing is, in reality, input data is seldom really random. It might have been sorted at some point, then augmented with additional elements, to be sorted again later. Choosing a random pivot is the correct solution, but you see, that would make qsort quite a lot longer than three lines, because selecting one element at random from a singly-linked list is a non-trivial undertaking.
This finally brings me to the third issue I have with qsort, and to the subject of this article: qsort sends a subtler message: Singly-linked lists and forward iteration are everything you need. They aren't, and they shouldn't be made to seem like they are.
Lisp has pioneered ubiquitous use of singly-linked lists ("S-lists"). S-lists connect together data and reference-to-next-element pairs in arbitrary shapes. In fact, S-lists enjoy the closure property [1] (not to be confused with function closures), meaning that they can represent any data structure, no matter how complex, by encoding it as directed graphs. That seems quite powerful, were it not for the unfortunate addendum—at a potential polynomial blowup in algorithmic complexity.
Such matters as a polynomial slowdown were too mundane to hinder the power of S-lists, so some functional programmers got imbued with an attitude of contempt toward arrays and associative arrays, data structures essential to many algorithms. Lisp and other functional languages do offer arrays, but almost invariably as second-class citizens that don't enjoy the level of language support that S-lists do. I've read many texts on functional languages and also written quite a bit of functional code, and I noticed a pattern—a lot of designers go with linear search at the core of the core algorithms without so much as thinking about it. In fact, "Structure and Interpretation of Computer Programs" [1], a highly revered Scheme-based programming textbook (and one of my personal favorites) uses linear search wherever anything is to be searched, and only bothers to mention arrays once, specifically to note that arrays do not enjoy the closure property, so they are not worthwhile.
I'm not sure what Alan Perlis had in mind when he quipped, "Lisp programmers know the value of everything and the cost of nothing," but in my humble opinion, functional languages' over-reliance on singly-linked lists and relative neglect of arrays and associative arrays are weaknesses, not strengths.
Unfortunately, iteration restricted to forward access, stilted as it is, has propagated into the object era.