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?
- 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?