如何表示要升序进行元素检查的无限列表？

Question

我有一个由以下列表理解初始化的无限素数列表：

primes = [x | x <- [2..], 0 `notElem` map (x `mod`) [2..(x `quot` 2)]]

这让我可以像 17 `elem` primes 一样进行检查以确认 17 是素数。但是，当我检查列表中是否有非素数时，程序不会停止计算。我认为这是因为它没有意识到如果在大于该数字的素数之前无法在列表中找到该数字，则无法在列表中的任何位置找到它。因此，在 Haskell 中是否有向编译器表明列表仅包含升序数字，以便 elem 检查将知道停止并且 return false 如果它达到一个数字列表大于它的第一个参数？

Answer 1

当然可以。您可以定义自己的 OrderedList 新类型，包装无限列表，定义以 OrderedList 作为参数的更有效的搜索函数。

newtype OrderedList a = OL [a]
member a (OL as) = case dropWhile (<a) as of
  []    -> False
  (x:_) -> a == x

您不能覆盖 elem 的行为，即使它是 Foldable 的 class 方法，因为 elem 的定义只需要基础元素类型是 Eq能，即：

member :: (Ord a, Eq a) => a -> OrderedList a -> Bool
elem :: (Eq a, Foldable t) => a -> t a -> Bool

您可以通过以下代码验证：

instance Foldable OrderedList where
  foldMap f (OL as) = foldMap f as
  elem = member -- error: Could not deduce `Ord a` arising from a use of `member`

注意：当你的列表不是无限的时候，你最好考虑使用树状结构（例如IntSet），它们将搜索操作的复杂度从O(n)优化到O(log (n)).

Answer 2

一种可能是使用 dropWhile:

isPrime n = (head $ dropWhile (< n) primes) == n

Answer 3

可以将其编码为折叠：

memberOrd :: (Eq a, Ord a) => a -> [a] -> Bool
memberOrd x = foldr (\y b -> y==x || y<x && b) False

|| 的惰性使得它也适用于无限列表。

（显然，我们必须假设列表不包含无限多的元素 < x。我们不会突然能够解决不可判定的问题... ;-)）

下面的 Will Ness 建议执行以下比较的变体：

memberOrd x = foldr (\y b -> y<x && b || y==x) False

如何表示要升序进行元素检查的无限列表？

How does one signify an infinite list to be ascending for elem checks?

primes

haskell

list

infinite

lazy-evaluation