2 points by rocketnia 2773 days ago | link | parent "Is there some way to get haskell's implicit handling of empty lists?"I'm pretty sure there's no implicit handling of empty lists. I think the blog author just left out the base case.---"I actually find keep with the anonymous arg more readable than the list comprehensions."I tend to find list comprehensions unreadable anyway. Using `filter` instead of list comprehensions yields fewer tokens in Haskell, too:`````` qsort [] = [] -qsort (p:xs) = qsort [x | x<-xs, x=p] +qsort (p:xs) = qsort (filter (< p) xs) ++ [p] ++ qsort (filter (p <=) xs) `````` Note Haskell's special shorthands for currying infix operators. The expression (< p) means a function that performs (input < p), while (p <=) means a function that performs (p <= input).I know, the point wasn't to talk about Haskell....---"I spent some time trying to build qsort using anarki's partition . No luck."Here's what I found. It does have fewer tokens after all. ^_^`````` (def qsort(l) (iflet (p . xs) l - (join (qsort:keep [< _ p] xs) list.p (qsort:keep [>= _ p] xs)))) + (apply + (intersperse list.p (map qsort (partition [< _ p] xs)))))) `````` Note that 'partition returns (true-elements false-elements). It could reasonably go the other way around.---As the first blog commenter notes, "I believe that that commonly cited example of quicksort in Haskell is not really quicksort, in that it does not have the space and time complexity of quicksort." This is probably true of these Arc snippets as well. Could we get a "real" Arc quicksort?Also, none of these implementations is a stable sort.
 3 points by zck 2771 days ago | link I believe this is a "real" qsort. It's way more verbose than I expected, but I did code it on two nights hours after I should have gone to bed. I'm sure I could name some things better. Maybe I will later.`````` (def qsort (lst) (let helper (afn (start end) (if (>= start end) lst (let pivot-pos (partition lst start end) (self start (- pivot-pos 1)) (self (+ pivot-pos 1) end)))) (helper 0 (- (len lst) 1))) lst) (def partition (lst (o start 0) (o end (- (len lst) 1))) "Partitions a list in-place. This method returns the position the pivot moved to." (withs (pivot lst.start higher-num-out-of-place (+ start 1) lower-num-out-of-place end) (until (is higher-num-out-of-place lower-num-out-of-place) (until (or (> lst.higher-num-out-of-place pivot) (is higher-num-out-of-place lower-num-out-of-place)) (++ higher-num-out-of-place)) (until (or (< lst.lower-num-out-of-place pivot) (is higher-num-out-of-place lower-num-out-of-place)) (-- lower-num-out-of-place)) (unless (is higher-num-out-of-place lower-num-out-of-place) (swap lst.higher-num-out-of-place lst.lower-num-out-of-place))) (let pivot-end (if (> lst.higher-num-out-of-place pivot) (- higher-num-out-of-place 1) higher-num-out-of-place) (swap lst.start lst.pivot-end) pivot-end))) `````` examples:`````` arc> (qsort (n-of 10 (- (rand 21) 10))) ;; from -10 to 10 inclusive (-10 -9 -5 -4 -2 5 6 6 8 9) arc> (qsort (n-of 10 (- (rand 21) 10))) (-10 -10 -8 -1 3 5 6 7 8 9)``````-----
 1 point by akkartik 2771 days ago | link Why do you say they aren't stable? I need to add a comparer to test stability:`````` (def qsort(l <) (iflet (p . xs) l (+ (qsort (keep [< _ p] xs) <) list.p (qsort (rem [< _ p] xs) <)))) `````` ..but that aside I think the sort will be stable, because later equal elements always end up in the last qsort, and rem is stable.-----