Lambda Calculus Primes – Sieve of Eratosthenese.

LA home
Computing
FP
 λ-calc.
  Intro
  Syntax
  Examples
   Ints
   Bools
   Lists(1)
   arithmetic
   Y (lazy)
   Y (strict)
   Lists(2)
   Trees
   Primes(1)
   Fibonacci(1)
   Unique
   Hamming#s
   Composites
   Fibonacci(2)
   Thue seqs.
   Edit-dist.
   primes
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, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Friday, 29-Mar-2024 13:32:46 UTC.

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