|
Each composite number is the product of at least two prime numbers,
and the prime numbers are {2, 3, 4, ...} with
the composite numbers removed:
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}
|
See:
L. Allison,
Circular Programs and Self-Referential Structures,
Software Practice and Experience
19(2) pp99-109
Feb 1989.
|
λ ...
:: | list cons |
nil | the [ ] list |
null | predicate |
hd | head (1st) |
tl | tail (rest) |
|
|
|