begin quoting Tracy R Reed as of Wed, Jun 27, 2007 at 04:29:06PM -0700: > Christopher Smith wrote: > >On Jun 27, 2007, at 12:15 PM, Stewart Stremler wrote: > >>Unexpected truncation? > >Huh? > > Stewart is not used to such short code and probably assumed that there
See? All ya'll must be psychic. I want my psychic super-powers! Wah! > must be more. Nope, that's it. You can plug that into hugs or similar > haskell system and start sorting. How can you _tell_ that it's all there? > >>Plus, it needs comments. > >I disagree here. You need to know the language to interpret it, but even > > Yeah, this is a tiny snippet of code. It implements quicksort. Everyone > knows how quicksort works. Not the sort of thing that needs comments. Except... it chooses the first element as a pivot. That's just *terrible*. It's not even worth implementing such a quicksort... so there obviously must be a pivot-selection bit that's been lost. ...and there's where you need a comment. "We're choosing the first element as a pivot, even though that's really dumb." When you do something unexpected and contrary to "what everyone knows", you need a comment, no matter how short the code. I would hold that there is often an inverse relationship: shorter the code (for a given functionality), the longer the comment should be. [snip] > Exactly. Written as a teaching tool not for actual high performance use. Teaching tools have pedagogical concerns beyond the simplest case. They need to scale gracefully with complexity... and I find that Andrew's example downthread to be very enlightening in this regard. [snip] > >>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 > > Indeed, I wasn't aware of that. I just searched google for java > quicksort and found something with source I could conveniently link to. Ah. Actually, the Arrays.sort implementation *is* a head-scratcher. But it's the sort of code one would /actually/ want to use, and successively revise the naive quicksort into when teaching about quicksort. > >Seriously, you're missing the point of the post. > > Indeed and wouldn't be the first time someone on this list has missed > the point. :) In both directions even. > >>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 quicksort function I pasted takes one argument which is a list so > that matches the (p:xs) but and the p is given the value of the first > element (the car of the list to use Lisp nomenclature) and the xs > becomes the rest (the cdr of the list). So now you can do comparisons > using the p and recurse on the xs part which is like cdr'ing down a list > in lisp. That's not _quite_ I was asking for. > Here is some more info on quicksort in haskell: [snip] How about a mergesort instead? I like mergesort. /me searches http://en.literateprograms.org/Merge_sort_(Haskell) Hm. That's not as short as I thought it would be. -- Let's go with the classic examples. Stewart Stremler -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
