惰性求值在无限素数列表生成器中如何工作？哈斯克尔

Question

primes :: [Int]
primes = sieve [2..]

sieve :: [Int] -> [Int]
sieve (n:ns) = n : sieve [n' | n' <- ns, mod n n' /= 0]

所以我明白了。这行代码将为我生成一个无限的素数列表，但我很难理解一件事，当我尝试从无限列表中过滤掉 2 的所有倍数时，它们的数量也是无限的，那么我们如何制作过滤掉 2 的所有倍数之前的递归调用。因为我试图生成一个无限列表，所以所有素数因此在我们进入下一个素数之前首先需要删除 2 的所有倍数？

Answer 1

因此，在我们进入下一个质数之前，首先需要删除所有 2 的倍数？

不，过滤也很懒。事实上，过滤操作（列表理解的作用）实现为：

filter :: (a -> Bool) -> [a] -> [a]
filter p = go
  where go [] = []
        go (x:xs) | p x = x : go xs
                  | otherwise = go xs

因此，这也将充当生成器：您始终可以询问下一个项目，它将返回下一个不能被二、三、五等整除的项目。

因此，列表理解不会急切地首先过滤掉所有项目。它传递一个将处理过滤后的项目的生成器。因此，这意味着如果我们将一个无限列表 [2, 3, 4, ...]

, it will return 2` 作为第一项传递给它，并递归所有不可被 2 整除的项目的列表。但该列表也很懒惰。如果我们随后请求下一个项目，它将返回 3，并且我们在一个生成器上递归，该生成器将另一个生成器作为输入，并将返回除以 3 的项目。