Un-genuine Sieve of Eratosthenes in Haskell

gistfile1.txt

$ ghci sieve.hs
*Main> take 10 primes
[2,3,5,7,11,13,17,19,23,29]

sieve.hs

primes = sieve [2..]

sieve (x:xs) = x : sieve [n | n <- xs, n `mod` x > 0]

Bravo!

That being said, I was trying to avoid using modulus and implement the sieve as literally as possible, crossing off the numbers while leaving them in sequential order.

@raganwald Fair enough. I didn't actually read your post - being a Haskell programmer, I don't read anything until I think I need to.

Or, using a strict language such as Scala:

import scala.math.BigInt

object Sieve extends App {
  def sieve(stream: Stream[BigInt]) : Stream[BigInt] = stream match {
    case x #:: xs =>
      x #:: sieve(
        for {
          n <- xs
          if (n % x > 0)
        } yield n
      )
  }

  def bigIntsFrom(n: BigInt): Stream[BigInt] = n #:: bigIntsFrom(n+1)

  val primes = sieve(bigIntsFrom(2))

  primes take 10 foreach println
}

It turns out there is an authoritative explanation for why this Haskell isn't the Sieve of Eratosthenes!

Great read: The Genuine Sieve of Eratosthenes

primes take 10 foreach println is equivalent to primes.take(10).foreach(println), right? Oh, Scala.

Nice find Reg. I love that the example code is identical to the one I typed from memory (disregarding whitespace and variable identifiers).