Subject: Haskell Question

From: Shlomi Fish <[email-masked]>
Date: Sun, 3 Dec 2000 16:54:11 +0200 (IST)

Hello all,

I encountered the following Haskell program that can be used to compute
all the primes on the web:

primes = sieve [2.. ] where
         sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ]

This program nicely translates into the following perl program:

@primes=(2);
for($a=3;$a<2000;$a++) {
    push @primes, $a unless (grep {$a % $_ == 0} @primes);
}

The "$a<2000" limit can be replaced by any other condition.

Now, there is an alternative methodology of generating primes, and this
is by keeping a vector of booleans, which is initialized to all trues, and
whenever a true is encountered, all the numbers starting from p*p and
above at steps p are marked as false. p is the position in which the true
was encountered in the vector. (vector == array, and not a VB one).

A perl program that implements this is given below:

#!/usr/bin/perl

use strict;

my $start = time();

my (@map);

my $limit = 100000;

@map=((1) x ($limit+1));

my $a = 2;
my $step = $a;
my $mark;
for($mark=$a*$a;$mark < $limit; $mark += $step)
{
    $map[$mark] = 0;
}

my $a_to = int(sqrt($limit));
for($a++;$a<=$a_to;$a++)
{
    if ($map[$a])
    {
        $step = $a<<1;
        for($mark = $a*$a; $mark < $limit; $mark+=$step)
        {
            $map[$mark] = 0;
        }
    }
}

my $end = time();

print $end-$start, "\n";

####################################################

Now, how do I implement this methodology in Haskell, without and I repeat
_without_ losing my mind. I tried to do that, with Haskell arrays, and I
came with a long and messy code. Not only that, but I couldn't scale
beyond 10,000 without getting an out-of-stack error from the hugs
interpreter, using either Int's (32-bit machine integers) or Integers
(unbounded integers). Maybe I should have used Booleans but I don't think
it would have made such a difference. 

If anybody can post here a working Haskell code, please do.

Regards,

	Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish        [email-masked] 
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

The prefix "God Said" has the extraordinary logical property of 
converting any statement that follows it into a true one.