## Lambda Calculus Example Composite and Prime Numbers

 home  Bib Algorithms Bioinfo FP Logic MML Prog.Lang and the mmlist

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.

 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}
window on the wide world:
 The Darwin Awards V: Next Evolution

 Linux  Ubuntu free op. sys. OpenOffice free office suite, ver 3.4+ The GIMP ~ free photoshop Firefox web browser FlashBlock like it says!

λ ...
 :: 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 Tuesday, 20-Aug-2019 12:03:12 AEST.