Haskell不会惰性求值takeWhile。

Question

isqrt :: Integer -> Integer
isqrt = floor . sqrt . fromIntegral

primes :: [Integer]
primes = sieve [2..] where
 sieve (p:ps) = p : sieve [x | x <- ps, x `mod` p > 0]

primeFactors :: Integer -> [Integer]
primeFactors n = takeWhile (< n) [x | x <- primes, n `mod` x == 0]

这是我的代码。我想你已经猜到我的意图：使用无限的质数列表，给定一个数字的质因数列表。但是这个代码并不是惰性求值。

当我使用 ghci，输入:l mycode.hs和primeFactors 24时，结果是 [2, 3（光标一直闪烁在那里），没有更进一步的 Prelude>提示。我认为那里有问题。我做错了什么？

谢谢。

- D. Jones

---

请注意，列表“[x | x <- primes，10 mod x == 0]”不是“[2,5]”，而更像是“2:5:infiniteLoop”，因为在5之后会无限尝试可能通过测试的素数x。当然，我们知道它们不会通过测试，但是列表推导式不知道。然后，takeWhile被卡在循环中。 - chi

是的，我知道它将是一个无限列表，谢谢。但我认为 takeWhile 在断言不再成立时会停止评估无限列表。 - D. Jones

不是无限列表。使用 takeWhile 没有问题。尝试执行 takeWhile (<=10) [1..] 和 takeWhile (<=10) (1:2:5:let f n = f (n+1) in f 3)。其中 [1..] 是无限列表，而 1:2:5:... 不是 -- 它是一个具有未定义脊柱的列表，在其第三个元素后。在无限列表中，take n list 总是返回结果，但当脊柱未定义时不会返回。 - chi

Answer 1

takeWhile 对于复合参数永远不会终止。如果 n 是合数，它没有任何大于等于n的质因子，所以 takeWhile 只会一直停留在那里。

将 takeWhile 应用于质数列表，然后使用 n mod x 过滤结果，示例如下：

primeFactors n = [x | x <- takeWhile (<= n) primes, n `mod` x == 0]

为了最大程度的正确性，<= 被用于替代 <，这样一个质数的质因数将由该数字本身组成。

- n. m.

---

你的代码很好用，谢谢。但我不确定我理解了takeWhile的情况。它实际上在哪里停止？还是列表推导式导致了无限循环？ - D. Jones

@D.Jones 这两种情况都有可能。考虑：takeWhile p xs，如果 xs 是有限的，那么 takeWhile p xs 也是有限的，但是如果 xs 是无限的，那么 takeWhile p xs 可能 是有限的或无限的，这取决于是否存在一个有限的 xs 前缀，在该前缀中 p 变为 false。在您的情况下，列表推导式将产生一个有限的前缀，其中所有元素都使 p 为 true，并且在此之后不会再生成更多元素，但是 列表推导式仍然会一直尝试质数。 - Bakuriu

重要的是要区分“有限”（又称终止）列表和仅具有有限元素数量的列表。例如，1:2:3:[] 是有限的（终止的），而 1:2:3:infiniteLoop 虽然只有 3 个元素，但不是有限的。因此，列表推导式不会终止，即使它只产生有限数量的元素；而 takeWhile 不会终止，因为条件永远不会变为 false，并且列表参数（列表推导式）不会终止。 - n. m.

Answer 2

有一个关于发生什么的插图：

http://sketchtoy.com/67338195

- Gurkenglas

Answer 3

你的问题并不是直接与takeWhile有关，而是与列表推导有关。

[x | x <- primes, n `mod` x == 0]

对于n = 24，我们得到24 `mod` 2 == 0和24 `mod` 3 == 0，因此这个列表推导式的值从2 : 3 : ...开始。但是请考虑...部分。

列表推导式必须不断从primes中获取值并检查24 `mod` x == 0。由于24没有更多的质因数，所以没有任何值能通过测试并作为列表推导式的第三个值被发射出来。但是由于总有另一个质数需要测试，因此它永远不会停止并得出剩余列表为空的结论。

因为这是惰性求值的，如果您只询问此列表的前两个元素，则可以正常运行。但是，如果您的程序需要第三个元素（甚至只需知道是否存在第三个元素），则列表推导式将永远旋转以尝试生成一个。 takeWhile (< 24)会从其参数中不断获取元素，直到找到一个不是< 24的元素。2和3都通过了这个测试，因此takeWhile (< 24)确实需要知道列表推导式的第三个元素。

但问题并不是在于takeWhile；问题在于您编写了一个列表推导式来查找所有质因数（以及仅此而已），然后尝试对该结果使用过滤器来切断无限探索所有不能可能成为因数的更高质数。如果您停下来思考一下，这并没有真正意义上的意义；根据定义，任何不是质因数的东西都不能成为该列表的元素，因此您无法从该列表中过滤掉大于n的非因子。相反，您需要过滤该列表推导式的输入，使其不会尝试探索无限空间，如@n.m的答案所示。

- Ben