Haskell - What does the lambda in this primality test mean and how does this work?

Question

From http://www.haskell.org/haskellwiki/Testing_primality, there is this code:

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

Where primes is a list of prime numbers (possibly infinite).

Two questions:

1. How would one read the lambda passed to foldr function
2. Since foldr starts from the right, why does this function work when it is passed an infinite list of primes? I'm guessing there is a short circuit built into the lambda?

Answer 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.

Answer 2

Lazy evaluation means boolean short-circuit logic stops a chain of functions being evaluated, even where the logic is inside the functions.

As a simple example, for any Foldable data type, you can write a null function like this:

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

This function will never be called more than once, because for an instance with more than one element it will evaluate to

False && *thunk* foldr...

The short-circuit boolean and means that the thunk is never evaluated, so this will happily work with infinite structures. Which is why you shouldn't implement null as a check to see if size == 0

This doesn't work in a strict language; each iterations of foldr would be evaluated in turn and passed to the next.

As for the lambda...

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

could be written like this:

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

Hope that helps.

EDIT: If it wasn't clear, the short-circuit boolean or || in that function works in the same way as the simpler example above.

Answer 3

The lambda part looks like this being translated into pythonish pseudocode:

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.

As for the foldr part, that's tricky indeed. foldr first evaluates the result for the tail of the list (r) then applies the function to the head and that r. So there must be a point where the tail can be computed without going further.

That will happen when the head is at least sqrt(n), which means: if there's a divisor, you can find it before, but for now return True and don't evaluate the tail.