Haskell 的评估速度比我想象的要快得多(没有提示)

Question

我写了下面的代码来检查一个数是否是质数:

factorsOf :: Int -> [Int]
factorsOf n = [factor | factor <- [2..sqrtOfN], n `rem` factor == 0]
    where sqrtOfN = round . sqrt $ fromIntegral $ n+1

isPrime :: Int -> Bool
isPrime n
    | factorsOf n == [] = True
    | otherwise = False

它有效，但我注意到一些奇怪的事情。如果我对一个大数(比如 100000001)运行 factorsOf，计算所有因子需要几秒钟。如果我在同一个数字上运行 isPrime，如果它找到一个因子，它几乎会立即返回。 Haskell 是否真的跟踪函数将返回以支持(我假设)惰性评估的条件？如果这是真的，那就太棒了。

Answer 1

如注释中所述，isPrime 只需要足够深入地评估 factorsOf 的结果以确定它是否为空列表。您可以像这样更惯用地编写 isPrime:

isPrime = null . factorsOf

null 就是

null (_:_) = False
null _ = True

请注意，一旦 null 可以在 (:) 构造函数上进行模式匹配，它就会返回一个结果，而不会评估列表的其余部分。

这意味着只有 factorsOf 只需要计算返回的 isPrime 的第一个因子，而 factorsOf 本身将计算整个列表.