Haskell 不延迟计算 takeWhile
Haskell Does Not Evaluate Lazily takeWhile
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>提示。我认为那里有问题。我做错了什么？
谢谢。
takeWhile 永远不会因复合参数而终止。如果 n 是合数，它没有质因数 >= n，所以 takeWhile 会坐在那里。
将takeWhile应用于素数列表，然后用n mod x过滤结果，如下所示：
primeFactors n = [x | x <- takeWhile (<= n) primes, n `mod` x == 0]
（使用 <= 而不是 < 以获得最大的正确性，因此素数的质因数将由该数组成）。
举例说明会发生什么：
你的问题不直接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 并不是真正的问题；问题是你已经写了一个列表理解来找到所有的主要因素（没有别的），然后试图在 results 上使用过滤器来切断无限探索所有不可能成为因子的更高素数。如果你停下来想一想，那真的没有意义；根据定义，任何不是主要因素的东西都不能成为该列表的元素，因此您不能从该列表中过滤掉大于 n 的非因素。相反，您需要将 输入 过滤为该列表理解，这样它就不会尝试探索无限的 space，如@n.m 的答案所示。
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>提示。我认为那里有问题。我做错了什么？
谢谢。
takeWhile 永远不会因复合参数而终止。如果 n 是合数，它没有质因数 >= n，所以 takeWhile 会坐在那里。
将takeWhile应用于素数列表，然后用n mod x过滤结果，如下所示：
primeFactors n = [x | x <- takeWhile (<= n) primes, n `mod` x == 0]
（使用 <= 而不是 < 以获得最大的正确性，因此素数的质因数将由该数组成）。
举例说明会发生什么：
你的问题不直接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 并不是真正的问题；问题是你已经写了一个列表理解来找到所有的主要因素（没有别的），然后试图在 results 上使用过滤器来切断无限探索所有不可能成为因子的更高素数。如果你停下来想一想，那真的没有意义；根据定义，任何不是主要因素的东西都不能成为该列表的元素，因此您不能从该列表中过滤掉大于 n 的非因素。相反，您需要将 输入 过滤为该列表理解，这样它就不会尝试探索无限的 space，如@n.m 的答案所示。