如何判断一个列表是无限的？ [英] How to tell if a list is infinite?
问题描述
length 之类的函数应用到无限列表中。 对未知列表应用 length 通常是一个坏主意，实际上是由于无限列表，并且在概念上，因为通常情况下，实际上关心的是长度。
您在评论中说：
我对Haskell很新，所以现在，没有无限的结构会让我的程序非常脆弱？
并非如此。虽然我们中的一些人希望有更好的方法来区分必要的有限数据和必然无限的数据，但当您创建，过程和检查惰性结构递增。计算长度显然不是递增的，但检查长度是高于还是低于某个临界值是，并且通常这就是你想要做的所有事情！
一个微不足道的情况是测试非空列表。 isNonEmpty xs ==长度xs> 0 是一个糟糕的实现，因为它检查了无数个元素，当检查一个元素就足够了！比较：
isNonEmpty [] = False
isNonEmpty（_：_）= True
code> 这不仅适用于无限列表是安全的，而且在有限列表上也更加高效 - 它只需要常量时间，而不是列表长度的时间线性。这也是标准库函数 null 已被实现。
为了概括这个长度测试的相对截止点，您显然需要检查与您比较的长度一样多的列表。我们可以做到这一点，而不再使用标准库函数 drop ：
longerThan :: Int - > [a] - > Bool
longerThan n xs = isNonEmpty $ drop n xs
给定长度 n 和一个（可能是无限的）列表 xs ，这将删除第一个 n 如果它们存在，则检查 xs 的元素，然后检查结果是否为非空。因为如果 n 大于列表的长度， drop 会产生空列表，这对所有正 n （可惜，在标准库中没有非负整数类型，例如自然数）
关键在于，在大多数情况下，将列表视为迭代流而不是简单的数据结构会更好。在可能的情况下，您希望执行诸如转换，累加，截断等操作，并生成另一个列表作为输出或仅检查已知有限数量的列表，而不是一次尝试处理整个列表。
如果您使用这种方法，您的函数不仅可以在有限的和无限列表上正常工作，还可以从懒惰和GHC的优化器，并可能运行得更快，使用更少的内存。
Is there a way to tell if a list in Haskell is infinite? The reason is that I don't want to apply functions such as length to infinite lists.
Applying length to unknown lists is generally a bad idea, both practically due to infinite lists, and conceptually because often it turns out that you don't actually care about the length anyway.
You said in a comment:
I'm very new to Haskell, so now, don't infinite structures make my programs very vulnerable?
Not really. While some of us wish there were better ways to distinguish between necessarily finite and necessarily infinite data, you're always safe when you create, process, and examine lazy structures incrementally. Computing the length is clearly not incremental, but checking to see if the length is above or below some cut-off value is, and very often that's all you wanted to do anyway!
A trivial case is testing for nonempty lists. isNonEmpty xs == length xs > 0 is a bad implementation because it examines an unbounded number of elements, when examining a single one would suffice! Compare this:
isNonEmpty [] = False
isNonEmpty (_:_) = True
Not only is this is safe to apply to an infinite list, it's also much more efficient on finite lists--it takes only constant time, instead of time linear in the length of the list. It's also how the standard library function null is implemented.
To generalize this for length testing relative to a cut-off, you'll obviously need to examine as much of the list as the length you're comparing to. We can do exactly this, and no more, using the standard library function drop:
longerThan :: Int -> [a] -> Bool
longerThan n xs = isNonEmpty $ drop n xs
Given a length n and a (possibly infinite) list xs, this drops the first n elements of xs if they exist, then checks to see if the result is non-empty. Because drop produces the empty list if n is larger than the length of the list, this works correctly for all positive n (alas, there's no non-negative integer type, e.g. natural numbers, in the standard libraries).
The key point here is that it's better in most cases to think of lists as iterative streams, not a simple data structure. When possible you want to do things like transform, accumulate, truncate, etc., and either produce another list as output or examine only a known-finite amount of the list, rather than trying to process the entire list in one go.
If you use this approach, not only will your functions work correctly on finite and infinite lists both, but they'll also benefit more from laziness and GHC's optimizer, and be likely to run faster and use less memory.
这篇关于如何判断一个列表是无限的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
