2

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?
Will Ness
  • 70,110
  • 9
  • 98
  • 181
hgcrpd
  • 1,820
  • 3
  • 19
  • 32

3 Answers3

4

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.

itsbruce
  • 4,825
  • 26
  • 35
  • This is a good explanation of the fold, but I think the answer that I've accepted is a better illustration of how exactly the fold and the lambda work in this case. – hgcrpd Oct 21 '13 at 23:01
  • Well, I started out by saying it's about short circuit boolean logic and there's a big `||` slap in the middle of that lambda ;) – itsbruce Oct 22 '13 at 09:17
  • And before your update, it wasn't at all clear what you meant by "how does the lambda work?". Updated. – itsbruce Oct 22 '13 at 10:06
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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • I've accepted this answer because it gives a clearer explanation of how the fold and the lamdba work in this function. Thanks! – hgcrpd Oct 21 '13 at 23:01
0

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.

bereal
  • 32,519
  • 6
  • 58
  • 104
  • 1
    I'd prefer `if p does not divide n: return r`. -- About `foldr`: Haskell is lazy, so actually `r` is not computed prior to calling the combining function for the first time. An attempt to compute `r`'s value will only be made if `r`'s value is requested. – Will Ness Oct 21 '13 at 19:27