Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

If I understand correctly, this code has a bug.

The list is the sorted list of lesser items, then the pivot, then the sorted list of greater items. But since the list of greater items is defined with ">=" rather than just ">", the list of greater items will also contain the pivot. That will put the pivot in the sorted list twice (for each recursive call).



Note that the argument, the list to be sorted, is pattern matched as

    (p:xs)
which means that p is the first element of the list, and xs is the rest of the elements (i.e., xs does not contain p). In the definition of "greater":

    greater = filter (>= p) xs
, the filter is applied to xs, which means that p will not be included.


Ah, I see. Thanks!


If I'm reading the code correctly: given the list [5,5,2,3] and the match (p:xs), p will match to the first 5 and xs will match to [5,2,3].

Once the matching is done, the pivot is no longer in the list xs, and therefore it won't be included twice.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: