FOB

This is a pretty clean definition of the Sieve of Eratosthenes in Haskell. Type it at the ghci command line and evaluate it to get a large list of primes before you get bored…

let primes =
    2 : [ i | i <- [3..],
              and [i `mod` j /= 0 |
                   j <- takeWhile (<= (i `div` 2)) primes]]

Now, try "last (take 5000 primes)" and note how long it takes to complete. Then try with 10,000 instead of 5,000.

Here's the weird bit, though. Now try running the same expression again; you should be able to just back up a line and hit return. This completes instantly?! Apparently the evaluator keeps the computed portion of the list around in case you need it again.

This "sharing" explains why you can get some surprising speedups on simple-looking codes. It also explains how you can easily and inadvertently leak a lot of memory.

Laziness weirds programming.

Update 2008/7/2: It's now not clear to me that anything in this post is right.

First of all, the code given implements trial division, not Sieve of Eratosthenes. I'll produce that code later.

Second of all, the code is gratuitously inefficient on several levels. This should be fixed.

Finally, it's not clear that I am correctly understanding sharing. My colleagues and students seem confused also, so I'm not feeling so bad about this. But I'd really take my claims with a large dose of salt until I understand better.