Lambda Calculus Primes – Sieve of Eratosthenese.

LA home
   Y (lazy)
   Y (strict)
   Thue seqs.
Note the use of "infinite" lists,  e.g.,  from 2 = 2, 3, 4, 5, ... , 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}


Also see compositeQ.
www #ad:

↑ © L. Allison,   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Thursday, 02-Feb-2023 14:28:49 UTC.

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