3 ms·
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 ('thir
by Someone 13y ago
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?
- namanbharadwaj 13y agoBy 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.
- bdonlan 13y agoRepeated 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.