Wednesday, 14 October 2009

Scala, lazy evaluation and the Sieve of Eratosthenes

I found a Scala algorithm for the Sieve of Eratosthenes here

Since that was written, the #:: object has been added to Stream and can be used instead of Stream.cons. Also as of a recent nightly build, #:: now object works in Stream pattern matching which means the Sieve of Eratosthenes can be even closer to the haskell implementation. (Presumably a good thing as it broadens your choices)


object Primes {

/* Haskell...
primes = sieve [2..]
sieve (p : xs) = p : sieve [x | x <− xs, x `mod` p > 0]
*/

def primes = {
def sieve(is: Stream[Int]): Stream[Int] = is match {
case p #:: xs => p #:: sieve(for (x <- xs if x % p > 0) yield x)
}
sieve(Stream from 2)
}

def main(args: Array[String]) {
primes take 100 foreach println
}
}


Nice!
Post a Comment