Lambda Calculus Primes &ndash 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.

© L. Allison   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Monday, 19-Mar-2018 20:17:52 EDT.

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