Lambda Calculus Example Composite and Prime Numbers

home1 home2
 Bib
 Algorithms
 Bioinfo
 FP
 Logic
 MML
 Prog.Lang
and the
 Book

FP
 Lambda
  Introduction
  Examples

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.


Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite
The GIMP
~ free photoshop
Firefox
web browser

λ ...
:: list cons
nil the [ ] list
null  predicate
hd head (1st)
tl tail (rest)

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Thursday, 28-Mar-2024 22:24:49 AEDT.