## Lambda Calculus Primes - Sieve of Eratosthenese.

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

FP
Lambda
Introduction
Examples

Note the use of "infinite" lists (e.g. from 2) in the functional-programming Sieve of Eratosthenese algorithm.

 ```let rec first = lambda n. lambda l. if n=0 then nil else (hd l)::(first (n-1) tl l), from = lambda n. n::(from (n+1)) in let rec filter = lambda f. lambda l. { remove multiples of f from l } if null l then nil else if hd l/f*f = hd l then filter f tl l else hd l :: filter f tl l, sieve = lambda l. if null l then nil else let p = hd l { prime } in p :: sieve (filter p tl l) in first 10 ( sieve (from 2) ) {\fB Sieve of Eratosthenes. \fP} ``` let rec first = lambda n. lambda l. if n=0 then nil else (hd l)::(first (n-1) tl l), from = lambda n. n::(from (n+1)) in let rec filter = lambda f. lambda l. { remove multiples of f from l } if null l then nil else if hd l/f*f = hd l then filter f tl l else hd l :: filter f tl l, sieve = lambda l. if null l then nil else let p = hd l { prime } in p :: sieve (filter p tl l) in first 10 ( sieve (from 2) ) {\fB Sieve of Eratosthenes. \fP}
 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, 02-Feb-2023 05:31:54 AEDT.