在Haskell中测试单例列表内容的最有效或最习惯的方法

Question

这个问题现在对我来说是严格的学术问题，但我可以看到它有一天会有实际应用。通过Haskell自我教育，我成功地构建了无限素数列表。其中一部分是这个函数:

isPrime n
    | n < 2                         = False
    | head (primeFactorsOf n) == n  = True
    | otherwise                     = False

其中primeFactorsOf按升序返回一个数字的质因数列表。1不是素数，所以一个素数n的素数因子是单元素列表[n]。因此，第二个保护大小写可以这样替换:

    | primeFactorsOf n == [n]       = True

其中一个比另一个更有效吗?如果没有，有没有一种更好的风格?我的直觉是，调用head并比较两个简单的数字比调用cons并比较两个单例列表要快，所以我已经得到的是最好的。但如果没有区别，我认为替代方案看起来要干净得多。

Answer 1

如果速度真的很重要，那么唯一确定的方法就是对它进行基准测试，我建议采用标准。哪一种能提供更好的性能还不完全清楚。如果primeFactorsOf被内联，那么编译器可能会注意到在第二种情况下您正在比较两个列表，并自动删除装箱。也可能不是，在这种情况下，你的预感很可能是正确的。

至于哪种形式更好，第二种形式是。像head这样的部分函数在大多数情况下最好避免使用。然而，也许你可以做得更好?

isPrime n = case primeFactorsOf n of
  [n'] | n == n' && n >= 2 -> True
  _ -> False

或者你可以把n >= 2的支票放在外面。或者，如果您知道primeFactorsOf返回n < 2的空列表，则可以完全省略它。

编辑:golfed to

isPrime n = case primeFactorsOf n of
  [_] -> n > 1
  _ -> False

Answer 2

(total rewrite)是的，你的第一个变体更好。它相当于

isPrime n = n > 1 && head fs == n
    where
       fs = primeFactorsOf n

第二个变体是

isPrime n = n > 1 && fs == [n]
    where
       fs = primeFactorsOf n

相当于

isPrime n = n > 1 && head fs == n && null (tail fs)
    where
       fs = primeFactorsOf n

对于合数，两者的行为相同，但对于素数，后一种变体将执行不必要的额外测试。

我们可能会试图"简化和改进"最后一个变体

isPrime n = n > 1 && null (tail fs)
    where
       fs = primeFactorsOf n

将省去对素数的数字比较操作，但对于合数，它实际上会强制计算n的第二个因子，这可能是不必要的，这可能非常昂贵(例如n = 2 * p与p是一些大素数)。您的第一个变量将找到第一个因子并立即返回False。

---

为了纠正这个问题，我们可以手动"融合"isPrime和primeFactors。假设它被定义为

primeFactors n = factor n primes
    where
        factor n (p:ps) 
            | p*p > n        = [n]
            | n `mod` p == 0 = p : factor (n `div` p) (p:ps)
            | otherwise      = factor n ps

与上一个版本融合，变成

isPrime n = n > 1 && hasOneFactor n primes  -- (null . tail . primeFactorsOf)
    where                                   --   == hasOneFactor
        hasOneFactor n (p:ps) 
            | p*p > n        = True
            | n `mod` p == 0 = False
            | otherwise      = hasOneFactor n ps

现在是这里最有效的代码。它可以进一步重写为(同样，rem比mod更快)

isPrime n = n > 1 && hasOneFactor primes    -- no need to pass `n` around
    where
        hasOneFactor (p:ps) = p*p > n ||
                              ( n `rem` p /= 0 && 
                                hasOneFactor ps )

或

isPrime n = n > 1 && foldr (p r-> p*p > n || (rem n p /= 0 && r))
                           undefined primes