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 短路逻辑会停止正在求值的函数链，即使该逻辑位于函数内部。

作为一个简单的示例，对于任何可折叠数据类型，您可以编写一个 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 值或 || 的工作方式与上面的例子比较简单。