2

从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中内置了短路？
4

3 回答 3

4

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

举个简单的例子，对于任何 Foldable 数据类型，您都可以编写null如下函数：

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

这个函数永远不会被多次调用，因为对于一个具有多个元素的实例，它将评估为

False && *thunk* foldr...

短路布尔值和意味着永远不会评估 thunk，因此这将很高兴地适用于无限结构。这就是为什么您不应该实施null检查以查看是否size == 0

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

至于拉姆达...

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)

希望有帮助。

编辑：如果不清楚，短路布尔值或 ||在该函数中的工作方式与上面更简单的示例相同。

于 2013-10-21T10:26:16.960 回答
1

Folds might be easy to grasp visually: 

   foldr g z [a,b,c...,x] === g a (g b (g c (g ... (g x z) ... )))

So if g p r doesn't use its 2nd arg, it won't force any further list access. Like you said, because of the short-circuit behaviour of || ("logical or").

And foldl g z [a,b,c...,x] === (g ... (g (g (g z a) b) c) ... x).

To read the function, first we notice that the fold is applied to a list of primes, [2,3,5,7,11,13,17..]. So it can be read as

isPrime n = n > 1 &&
   foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes
===
isPrime n = n > 1 &&
   (2*2 > n || (rem n 2 /= 0 &&
   (3*3 > n || (rem n 3 /= 0 &&
   (5*5 > n || (rem n 5 /= 0 && 
   -- the expansion stops when p*p > n
   -- because (True || r) === True
   ......................... && 
   (True) ... ))))))

In foldr's combining function, the second argument is for "result" of folding the rest of the list; r is a suggestive name to that effect.

于 2013-10-21T19:58:35.963 回答
0

lambda 部分看起来像这样被翻译成 pythonish 伪代码： 

def f(p, r):
  # invariant: r is True iff we have not seen a divisor of n yet.
  # we must return an updated r

  if p > sqrt(n): 
     return True # because we need a divisor less than that

  if p does not divide n and r is True:
     return True # because p is not a divisor neither we have seen one yet

  return False  # and this will become a new r and will return False forever.

至于那foldr部分，确实很棘手。foldr 首先评估列表尾部的结果（r），然后将该函数应用于头部和那个r。所以必须有一个点可以不用进一步计算尾巴。

当头部至少为 时会发生这种情况sqrt(n)，这意味着：如果有一个除数，您可以在之前找到它，但现在返回 True 并且不计算尾部。

于 2013-10-21T07:06:08.010 回答