begin quoting Tracy R Reed as of Wed, Jun 27, 2007 at 01:16:51AM -0700: > [snip] > And learning some interesting things and really starting to get my head > around purely functional programming. One of the things that attracts me > to this style is the succinctness and the idea of specifying the > mathematical formula which describes *what* you want done and not so > much the implementation of the algorithm which describes *how* to do it.
Which is great in some cases, and no so great in others. > A neat example is to compare quicksort in haskell: > > quicksort :: (Ord a) => [a] -> [a] > quicksort [] = [] > quicksort (p:xs) = quicksort [ x | x <- xs, x <= p ] ++ [ p ] ++ > quicksort [ x | x <- xs, x > p ] Unexpected truncation? Plus, it needs comments. Also, as it seems to be a standard implementation of quicksort, it's going to have _lousy_ worst-case performance. Where's the insertion-sort for small arrays? Where's the best-of-three pivot selection logic? How easy is it to add such things? And where did the unit-test/example run go? > to this fairly typical seeming example of quicksort implemented in Java: > > http://www.augustana.ab.ca/~mohrj/courses/2004.winter/csc310/source/QuickSort.java.html Um, that doesn't seem typical, except so far as "typical" means "everyone publishes their student programs". It's pretty ugly, really... Oh, and it's broken -- the pivot is *always* the lowest element in the array, which means it's a pretty sad (and slow) quicksort. Better to look at Arrays.sort, which is part of Java, and generally implemented with a good quicksort...and as this is what's used in the standard library, it arguably counts as "typical" (but it's not so succinct as the Haskell version, but it probably runs a hell of a lot ...quicker... than the Haskell version too). > Once you read up on the fundamentals of haskell you realize (I did, > anyway) that the haskell code expresses the idea that you have a pivot > point and you put everything greater than the pivot on one side and > everything less than the pivot on the other side...and then you do it > again. Until you have the whole list sorted. How about an exploded description of the syntax. I see most of it, except that I don't see how the pivot is selected, which is really the key to quicksort. > The java code seems to > offer more places to screw up, more loops, and more head scratching > while we figure out all of the manual incrementing and decrementing that > goes on. Well, you're not comparing apples to apples; pick equivalent algorithms. Provide an ugly and broken haskell implementation for comparison... :-P -- I don't buy "You gotta drink the koolaid" arguments. Stewart Stremler -- KPLUG-LPSG@kernel-panic.org http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
