Lambda Calculus Primes - Sieve of Eratosthenese.

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}
      if null l then nil        {of f from l     }
      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}

 

NB. The applet above needs Java on.