haskell - 为什么 ghc 评估我的无限列表？

Question

作为我的第一个 haskell 程序，我正在尝试这样做 - 这是获得 1 到 10 的艰难方法。我正在构建一个无限的整数列表，并对它们进行排序，然后取前 10 个。我的目的是说服自己我可以使用无限列表，而不会导致对它们的评估超出所需结果的严格要求（咳咳）。

我的代码是..

module Main where

import Data.List

minima n xs = take n (sort xs)

main = do
    let x = [1..] 
    print (minima 10 x)

使用 ghc 编译并运行生成的可执行文件..它坐在那里分配直到被杀死。

有什么提示吗？

Answer 1

问题是您正在尝试对无限列表进行排序。在列表中的所有元素都已知之前，列表永远无法完全排序，这就是它挂起的原因。您的程序适用于有限列表。

此外，作为次要问题，您可以将最小值重写为

minima n = take n . sort

由于部分应用，minima n将返回一个期望列表的函数。

Answer 2

在有限时间内对无限列表进行排序是不可能的。

作为证明，考虑排序包括找到最小元素，并且要找到无限列表的最小值，您必须检查列表中的每个元素，这将花费无限时间。

但是，在您的情况下，您知道列表已经排序。这使它成为对无限列表进行排序的特殊情况，即对已排序列表进行排序。这个案子是可以解决的。

Answer 3

您正在尝试对无限列表进行排序。