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

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: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}

[Previous Page] [Next Page] [Index] © L. Allison, Dept. of Computer Science, Monash University