Lambda Calculus Example: Composite and Prime Numbers

LA home
Computing
FP
 λ-calc.
  Intro
  Syntax
  Examples
   Ints
   Bools
   Lists(1)
   arithmetic
   Y (lazy)
   Y (strict)
   Lists(2)
   Trees
   Primes(1)
   Fibonacci(1)
   Unique
   Hamming#s
   Composites
   Fibonacci(2)
   Thue seqs.
   Edit-dist.
   Composites
Each composite number is the product of at least two prime numbers, and the prime numbers are {2, 3, 4, 5, 6, ...} 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,

first = lambda n. lambda l.
  if n <= 0 then nil else hd l :: first (n-1) tl l

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

in first 10 primes

{\fB Composites and Primes. \fP}

See: L. Allison, Circular Programs and Self-Referential Structures, Software Practice and Experience, 19(2), pp.99-109, Feb 1989, doi:10.1002/spe.4380190202.



If the first prime is 2, the first composite must be 4=2×2 and hence 3 is the second prime, the second composite must be 6=2×3 and the third prime is 5, and so on.

www:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Tuesday, 07-Jul-2020 07:41:30 EDT.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.