Lambda the Ultimate

inactiveTopic Calculating the Sieve of Eratosthenes
started 4/19/2004; 5:11:28 AM - last post 4/19/2004; 8:24:34 AM
Ehud Lamm - Calculating the Sieve of Eratosthenes  blueArrow
4/19/2004; 5:11:28 AM (reads: 9659, responses: 3)
Calculating the Sieve of Eratosthenes
There is a well-known "folklore" functional program for the Sieve of Eratosthenes. I presented a calculational derivation, based on the universal property of streams.

Nice slides by Lambert Meertens.

Posted to functional by Ehud Lamm on 4/19/04; 5:16:56 AM

Dan Shappir - Re: Calculating the Sieve of Eratosthenes  blueArrow
4/19/2004; 6:51:20 AM (reads: 323, responses: 1)
Some time ago I implemented this function in JavaScript using BeyondJS. Obviously not as nice as Haskell, but still ...

function sieve(ns) {
 return ns.head(1).extend(sieve.using(ns.tail().filter("%".curry([,ns.head()]))));
var primes = sieve((2).lazy());

Ehud Lamm - Re: Calculating the Sieve of Eratosthenes  blueArrow
4/19/2004; 6:55:43 AM (reads: 322, responses: 0)
How does the lazy thing work?!

Dan Shappir - Re: Calculating the Sieve of Eratosthenes  blueArrow
4/19/2004; 8:24:34 AM (reads: 300, responses: 0)
Well ... in BeyondJS lazy lists are objects that wrap a generator function. The generator functions take a state and return a value and a state, which is used in the next invocation. The wrapper exposes the value through a generalized collection API (the same API is supported by Array objects for example). Thus (2).lazy() returns an object that represents the list of numbers 2..

The lazy list object implement an extend() method that takes another lazy list as an argument and appends it to the original. Internally it creates a new generator that uses the original two generators. Since the generators are just functions, they can be recursive so that the list provided as an argument to extend can be dependent on the original list, as in this case.

Actually it's a little bit more complex. Note that I'm not calling sieve() when passing it as an argument to extend(). Instead I use sieve.using(). This returns a function this when called, invokes sieve() with that argument (thing of it as a function for whom all the arguments have been curried but the function hasn't been called yet - a freeze-dried function). This is really how you do lazy evaluation in JavaScript: instead of passing the result of a calculation pass a reference to a function that performs the calculation.

I've written this off-the-cuff so I hope it's clear.