Haskell - 这个素数测试中的 lambda 是什么意思，它是如何工作的？

Question

来自 http://www.haskell.org/haskellwiki/Testing_primality ，有这段代码:

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

其中 primes 是一个素数列表(可能是无限的)。

两个问题:

1. 如何读取传递给 foldr 函数的 lambda
2. 既然 foldr 从右边开始，为什么这个函数在传递一个无限的素数列表时会起作用？我猜 lambda 内部有短路？

Answer 1

懒惰求值意味着 bool 短路逻辑会停止正在求值的函数链，即使逻辑在函数内部也是如此。

作为一个简单的例子，对于任何 Foldable 数据类型，您可以像这样编写一个 null 函数:

null t = foldr (\x b -> False && b) True t

这个函数永远不会被调用超过一次，因为对于一个具有多个元素的实例，它的计算结果为

False && *thunk* foldr...

短路 bool 值 and 意味着 thunk 永远不会被计算，所以这将愉快地处理无限结构。这就是为什么您不应该实现 null 作为检查是否 size == 0

这不适用于严格的语言； foldr 的每个迭代将依次评估并传递给下一个。

至于 lambda...

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

可以这样写:

isPrime n = n > 1 &&
    foldr f True primes
    where
        f p r = p*p > n || ((n `rem` p) /= 0 && r)

希望对您有所帮助。

编辑:如果不清楚，该函数中的短路 bool 值或 || 的工作方式与上面的简单示例。