Thursday, February 26, 2009

First!!

Welcome to the algotron, the one stop solution for the awesome things you've always wanted to do. I've been doing awesome things for awhile now so I figured I might as well start sharing. You don't need to know much about me... I'm a coder, rocker, and I'm gonna rock some code out on this blog... let's get it going:

I wrote this Haskell code that defines an infinite list of prime numbers using the Sieve of Eratosthenes... I don't think this is the most efficient way to generate primes but it's got a pretty elegant definition

primes = let sieve (x:xs) = x:sieve [y | y <- xs, y `mod` x /= 0] in sieve [2..]

So I thought I'd try to port my code over to C# 3.0 and it looks something like the following:

class Program
{
static IEnumerable From(int start)
{
while (true)
{
yield return start++;
}
}

static IEnumerable Sieve(IEnumerable sequence)
{
var x = sequence.First();
var xs = sequence.Skip(1);

return sequence.Take(1).Concat(Sieve(xs.Where(y => (y % x) != 0)));
}

static IEnumerable Primes
{
get
{
return Sieve(From(2));
}
}

static void Main(string[] args)
{
var xs = Primes.Take(10);
}
}

When I load the Haskell code into the REPL and try something like:

> take 10 primes
[2,3,5,7,11,13,17,19,23,29]

it works just fine. However, when I execute the C# program it doesn't halt and eventually overflows the stack (when I step though with the debugger I see that it is generating the right sequence it just doesn't stop when it's supposed to). I'm pretty sure the Haskell code works due to lazy evaluation but I thought that IEnumerable was also lazy... I guess it's only lazy when you aren't using it recursively.

This isn't a huge show stopper or anything... I think it would be nice if it worked in C# but I'm not gonna loose any sleep over it.

1 comment: