Comments on Froth & Java: Sieve of Eratosthenes

What do you think about this stream based implemen...

2009-06-30T07:29:15.227Z

What do you think about this stream based implementation?

def primes: Stream[Int] = {
import scala.collection.SortedSet
import scala.collection.immutable.TreeSet
def ps(tuple:(Int,SortedSet[Int])):Stream[(Int, SortedSet[Int])] = {
def np(n:Int):(Int, SortedSet[Int]) =
if (tuple._2.takeWhile(p => p*p <= n).exists(n % _ == 0)) np(n+2)
else (n, TreeSet(n) ++ tuple._2)
Stream.cons(tuple, ps(np(tuple._1 + 2)))
}
Stream.cons((2, TreeSet(2)),ps((3, TreeSet(2,3)))).map(_._1)
}

Instead of first/drop, use head/tail. You are usin...

2009-06-29T18:49:42.834Z

Instead of first/drop, use head/tail. You are using a list, after all, and first, for one, is scheduled for deprecation.

You can test xs.head*xs.head < xs.last as the if condition instead of xs.isEmpty, and that will give you proper Sieve implementation without any trouble. That will cause the list to be traversed at each recursion, which isn't nice. Instead, since nomults is internal, you should add a third parameter, and pass "n" in it at sieve's call to nomult.

I agree with Daniel. Besides not implementing the ...

2009-06-29T18:18:04.509Z

I agree with Daniel. Besides not implementing the s.o.e. it also performs worse. Oh and runs out of heap space quickly. Have a look at the LtU link. Quite enlightening.

That example on scaladoc is not actually a Sieve o...

2009-06-29T18:05:42.712Z

That example on scaladoc is not actually a Sieve os Eratosthenes. See http://lambda-the-ultimate.org/node/3127.

The scaladoc page for Stream has an implementation...

2009-06-29T16:05:28.459Z

The scaladoc page for Stream has an implementation using streams, for comparison.
http://www.scala-lang.org/docu/files/api/scala/Stream.html