懒惰评估及其效率的澄清

Question

我在 Real World Haskell 上遇到了以下句子：

懒惰的评估有一些令人毛骨悚然的效果。假设我们要查找未排序列表的 k 个最小值元素。在传统语言中，显而易见的方法是对列表进行排序并取前 k 个元素，但这很昂贵。为了提高效率，我们将编写一个特殊的函数，一次性获取这些值，并且它必须执行一些中等复杂的簿记。在 Haskell 中，先排序再取的方法实际上表现良好：懒惰确保列表只会被排序到足以找到 k 个最小元素。

他们为此提供了一个代码实现：

minima k xs = take k (sort xs)

但真的是这样吗？我认为即使在 Haskell 中，它也应该做一个完整的列表来取出k元素。（想象一下在列表末尾有最小的数字）。我在这里错过了什么吗？

Answer 1

（只是将我的评论放在这里回答）遍历整个列表并不等于对其进行排序。假设进行快速排序，您围绕枢轴对列表进行分区，然后递归地对列表的左半部分和右半部分进行排序。如果您只要求左半部分的元素，则无需对右半部分进行排序。这个论点可以递归地应用。因此，如果您在排序后从长度列表中获取k元素n，则复杂度为O(n + klog k)，而不是O(n log n)。正如 @MoFu 所指出的，Heinrich在这里有一篇很好的博客文章。