Hacker News Reader

Comment by thesz | Hacker News Reader

This is so trivial!

Actually, if you use lazy data structures, then sorting the list lazily and taking i-th element will give you the best possible complexity: http://en.wikipedia.org/wiki/Selection_algorithm#Language_su...

In Haskell, it is nothing more than "ithSmallest xs i = sort xs !! i".

View on HN

Pretty sure this is wrong. For example, what about the case where k=n? Then the lazy evaluation will have to fully sort the list before it can determine the kth element, resulting in an O(n log n) algorithm.

In the standard idiom,

   smallest = head . sort

we're only looking for the case of k=1, so we can do it in O(n) time.

Note that if you used a lazy BST, then you could probably still get the last element in O(n) run time, but your example code doesn't do that. AFAIK, no standard library routine exists for this.

If your sort is lazy enough, the `(sort xs) !! k` approach will work fine. Haskell's default sort isn't lazy enough, but you could certainly make it so.

You don't have to fully sort the list before determining the kth element (again assuming a sufficiently lazy implementation). Once you know the element is in the second half of the list, the sort simply will never sort the first half.

It should be noted that the additional overhead from performing lazy quicksort (all those additional thunks) make it an unlikely choice for the standard sort function; you'd suffer a large constant factor overhead in the typical case of processing the entire list in sorted order.

Yep, definitely should have noted that. It's an interesting mental exercise though.

I don't see how that follows from lazy evaluation. Here's my logic (corrections welcome):

- That 'sort' will produce the items of the list in some order ('third item is 2nd largest, 17th item is 34th largest,...).

- Lazy evaluation cannot stop before the sort produces 'x is i-th'.

- 'sort' does not know what is done with its output (i.e. it does not know the value of i)

If these are true, Evie can pick i in such a way that it is produced last, that is: such that sort must sort the complete list. That requires O(n log n) time.

The only way around this I can see is if the language recognizes the idiom and special-cases it to pick a sort algorithm, based on both the sequence xs and the requested index i. Does Haskell contain such a special case?

By lazy, thesz is referring to a property of the data structure, not lazy evaluation.

`sort xs` evaluates to a data structure which contains the original unsorted sequence.

When asked for the ith element, the datastructure uses quickselect to produce the ith smallest element, while also partially sorting the sequence.

Repeated requests for the ith element will become faster and faster, as the sequence becomes more and more sorted.

Repeated requests for the i-th element will not become 'faster and faster' but instead would simply be Θ(i) - they'd traverse i list pairs, then read the memoized data component.

Reply on news.ycombinator.com