Lambda Calculus

Composites.

A more unusual primes program is an extension of the Hamming numbers program. The set of primes is the complement of the set of composite numbers in the integers. A composite number is a product of at least two primes. This can be used to define two mutually recursive lists - primes and composites. It is necessary to specify the first prime, 2. The first composite is therefore 4. This means the second prime is 3, the second composite 6, the third prime 5 and so on.

let rec
merge = lambda a. lambda b.
  {assume a and b infinite and disjoint}
  let a1=hd a, b1=hd b
  in if a1 < b1 then a1::(merge (tl a) b)
     else {a1 > b1}  b1::(merge a (tl b)),

mult = lambda a. lambda b. (a * hd b)::(mult a tl b),
 
remove = lambda a. lambda b.
  { a-b, treat lists as sets. PRE: a & b ascending }
  if hd a < hd b then (hd a)::(remove tl a b)
  else if hd a > hd b then  remove a tl b
  else remove tl a tl b,

from = lambda n. n::(from (n+1)),
       { n::(n+1)::(n+2):: ... }

products = lambda l.           { PRE: l ascending }
  let rec p = (hd l * hd l) :: {   & elts coprime }
              (merge (mult  hd l  (merge  tl l  p))
                     (products  tl l))
  in p

in let rec
   composites = products primes,
   primes = 2 :: (remove (from 3) composites)   { ! }

in primes

{\fB Composites and Primes. \fP}

In case the reader is sceptical about the viability of this program, the start of its output follows.

(2::
(3::
(5::
(7::
 ...etc...

 Output from Composites/Primes Program.

Also see `circular lists' in [Allison (1993)].