你能认出Haskell程序中的无限列表吗？

Question

可能重复:
如何判断列表是否无限？

例如,在Haskell中,您可以定义无限列表[1..].Haskell中是否有内置函数来识别列表是否具有有限长度？我不认为可以编写用户提供的函数来执行此操作,但Haskell的列表的内部表示可能能够支持它.如果没有标准的Haskell,是否有提供这种功能的扩展？

Answer 1

不,这是不可能的.编写这样的函数是不可能的,因为你可以拥有有限性可能未知的列表:考虑一个递归循环,生成一个可以找到的所有双素数的列表.或者,为了跟进Daniel Pratt在评论中提到的内容,您可以列出通用图灵机在执行过程中所采取的所有步骤,在机器停止时结束列表.然后,您可以简单地检查这样的列表是否是无限的,并解决停机问题!

实现可以回答的唯一问题是列表是否是循环的:如果其尾指针之一指向列表的前一个单元格.但是,这是特定于实现的(Haskell没有指定实现必须如何表示值的任何内容),不纯(编写相同列表的不同方式会给出不同的答案),甚至依赖于诸如传入的列表之类的内容这样的功能已被评估.即便如此,在一般情况下,它仍然无法区分有限列表和无限列表!

(我提到这是因为,在许多语言中(例如Lisp族的成员),循环列表是唯一的无限列表;没有办法表达类似"所有整数列表"的东西.所以,在这些语言中,你可以检查列表是否有限.)

Answer 2

没有任何方法可以测试列表的有限性,除了迭代列表以[]在我知道的任何实现中搜索final .一般来说,无法确定列表是有限的还是无限的,而不是实际寻找结束(这当然意味着每次得到答案时,都表示有限).

Answer 3

您可以在列表周围编写一个包装类型来跟踪无限,并将自己限制为"可判断"操作(以某种方式类似NonEmpty,避免空列表):

import Control.Applicative

data List a = List (Maybe Int) [a]

infiniteList (List Nothing _) = true
infiniteList _ = false

emptyList = List (Just 0) []
singletonList x = List (Just 1) [x]
cycleList xs = List Nothing (cycle xs)
numbersFromList n = List Nothing [n..] 
appendList (List sx xs)  (List sy ys) = List ((+) <$> sx <*> sy) (xs ++ ys)
tailList (List s xs) = List (fmap pred s) (tail xs)
...