|
Note the use of "infinite" lists (e.g. from 2)
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 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}
|
|
|
λ ...
:: | list cons |
nil | the [ ] list |
null | predicate |
hd | head (1st) |
tl | tail (rest) |
|
|
|