为什么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

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

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

但是,在您的情况下,您知道列表已经排序.这使得它成为排序无限列表的特殊情况,即对排序列表进行排序.这种情况是可以解决的.