begin quoting Christopher Smith as of Wed, Jun 27, 2007 at 01:19:31PM -0700: > On Jun 27, 2007, at 12:15 PM, Stewart Stremler wrote: > > >begin quoting Tracy R Reed as of Wed, Jun 27, 2007 at 01:16:51AM > >-0700: > >>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? > > Huh?
How you can tell if the example was truncated or not? I know, I know, my problem is that I'm not psychic like all ya'll. > >Plus, it needs comments. > > I disagree here. You need to know the language to interpret it, but > even without that, if you have a familiarity with the quicksort > algorithm, it is very easy to see what is happening here. And _that's_ one of the reasons I would stay the hell away from such languages -- it's not about the language, so much as it is about the arrogance of the adherents. There are some communities I do not wish to be a part of. > >Also, as it seems to be a standard implementation of quicksort, it's > >going to have _lousy_ worst-case performance. > > Sure. I don't believe this was meant to be an example of "best sort > EVAR!". Simply how easy it is to write. Mergesort would be a better example then. > >How easy is it to add such things? > > Again, one can reasonably extrapolate from the code sample just how > difficult this is. So... it's a royal PITA then. KTHNX. > >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. > > Statistically, it will be just as efficient as any other single pivot > sample based selection process. Yes, it has a really crappy corner > case, but so did the Haskell example. It is an apples to apples > comparison. Ah, I see. That *was* the sucky Haskell example. The problem with quicksort is that the sucky variants aren't at all representative of what one is likely to actually use (thus my preference for mergesort). > >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). > > If only Haskell had a fast and efficient sort algorithm... oh wait. ;-) > > Seriously, you're missing the point of the post. "You don't agree with me! You must be missing the point!" Bah. [chop] > >I don't buy "You gotta drink the koolaid" arguments. > > Hey, functional programming has fairly obvious gotchas, but it > clearly has some advantages and you don't have to drink the koolaid > to recognize that. Oh, indeed. There are no doubt some problems for which it is well suited. Even COBOL is useful, in the correct problem domain. :-O -- I need block terminator indicators. Stewart Stremler -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
