Christopher Smith wrote:
Are we constructing or reusing lists?
Haskell is a purely functional language. :-)
Ignoring the obvious non sequitur ...
Unfortunately, I'm pretty sure that the algorithm is O(n^2) time *and*
o(n^2) space in *all* cases because of the requirement to copy the lists
around.
This reference seems to agree:
http://en.literateprograms.org/Quicksort_(Haskell)
and needs to use this code to get O(n log n) time with O(n) space:
qsort3' (x:xs) y = part xs [] [x] []
where
part [] l e g = qsort3' l (e ++ (qsort3' g y))
part (z:zs) l e g
| z > x = part zs l e (z:g)
| z < x = part zs (z:l) e g
| otherwise = part zs l (z:e) g
Doesn't look so clean or obvious anymore. (Aside: this accumulator
approach in which you explicitly manage the environment state to short
circuit copying is a fairly standard pattern required for functional
languages. Go check out Okasaki's "Purely Functional Data Structures")
In fact, what you described is the *classic* pitfall of functional
languages. It is very easy to write code that performs absolutely
horribly because of all the implied copying.
In this instance, someone spent the extra time to do a functional-style
mergesort that would be matched in performance (and better in space!) by
someone who wrote a stupid shell sort ( O(n^2) time, O(n) space) in
imperative style.
Worse, a naive Haskell programmer would actually have been more
successful with writing a shell sort even in Haskell (which would give
the expected O(n^2) time, O(n) space)!
Looking "just like the textbook algorithm" and then executing in the
wrong O() bounds is hardly a good example of where functional
programming shines.
I suggest finding a better example.
-a
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
