Lambda Calculus

Sieve of Eratosthenese.

A favourite functional programming example is the sieve of Eratosthenes. This particular version prints primes up to a limit and stops.

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}

The function call `from 2' produces the infinite list [2, 3, 4, ...]. Sieve takes the first value off the input list, which it knows must be prime, and returns this as the start of its output list. It then removes (filters) multiples of p from the rest (tl) of the input list and sieves the result. This is just the algorithm of Eratosthenese expressed in FP. Its behaviour can be visualized as an expanding network of processes:
[diagram]