Scala: iterating a sequence when changing it?

Question

I am trying to implement the Sieve of Eratosthenes in Scala.

I'll start by initializing the sequence of all odd numbers plus 2:

// (end goal is to find all prime factors of bigNumber) val largestPrime : Long = Math.ceil(Math.sqrt(bigNumber)).toLong var nums : Seq[Long] = (3L to largestPrime by 2L).toSeq nums +: 2L 

Now nums contains Seq (2,3,5,7,9,11,13,15, ..., (maximumPrime)). Then, through a sieve, I want to iterate over each element and filter all the multiples of this element from Seq. It would look something like this, but it just repeats for every odd number:

 for(i : Long <- 3L to largestPrime by 2L) { nums = nums.filter((j : Long) => j == i || j % i != 0) } 

So instead, I would like to use something like this:

 for(i <- nums) { // filter } 

But of course, it just copies the sequence into an iterator, and then iterates over each value in nums , as it did at the beginning of the for loop (so in this case it is exactly equivalent to the previous example). I want each iteration to get the next value from nums .

What is the best way to implement this? Should I use an index variable and a while loop? I am not sure how to get an element from a sequence (i.e. how to get an element x of a sequence, where x is the index). Or is there a more functional way to do this?

---

Edit: I just found the scanLeft function, I'm trying to figure out how to use it, since I suspect that it might be useful in this case ...

Answer 1

Let it begin with what I consider to be the biggest problem above. You have the following:

 for (i <- mi) { mi = something else } 

This will not change mi , which is executed by iteration. This means that mi will remain unchanged. Perhaps you can change the value of mi , but changing it will not work. By the way, the mutation may also not work.

So how do you do this? You do not use for understanding - or at least not so. You can see my own version here , which iterates through a collection other than the one that is mutated. Or here is a single line:

 (n: Int) => (2 to n) |> (r => r.foldLeft(r.toSet)((ps, x) => if (ps(x)) ps -- (x * x to n by x) else ps)) 

Now, back to what you want to do ... when you use to understand, you are actually calling the foreach , map or flatMap , so you need a collection that can handle one of these methods and not have problems replacing the "next "element from one iteration to another. As I said, I'm not sure if any of the Scala collection is suitable for counting. You would be better off using a while and keeping track of things yourself if you go this route. For instance:

 def primes(n: Int) = { import scala.collection.mutable.LinkedList val primes = LinkedList(3 to n by 2: _*) var p = primes while (p.nonEmpty) { var scanner = p while (scanner.next.nonEmpty) { if (scanner.next.head % p.head == 0) scanner.next = scanner.next.next else scanner = scanner.next } p = p.next } primes } 

Note that I keep the pointer to the start of the LinkedList , move p through each known right number, and move the scanner through all the remaining numbers to cut the unnecessary numbers.

Answer 2

Example in docs scala.collection.immutable.Stream has a sieve:

 object Main extends Application { def from(n: Int): Stream[Int] = Stream.cons(n, from(n + 1)) def sieve(s: Stream[Int]): Stream[Int] = Stream.cons(s.head, sieve(s.tail filter { _ % s.head != 0 })) def primes = sieve(from(2)) primes take 10 print } 

Answer 3

Neither a good functional solution, nor a solution that reveals hidden Scala Library treasures, but its rather simple creation of a specialized iterator.

 class ModifyingIterator(var collection: Seq[Long]) extends Iterator[Long] { var current = collection.head def next = { current = collection.find(_ > current).get current } def hasNext = collection.exists(_ > current) } val mi = new ModifyingIterator(nums) for (i <- mi) { mi.collection = mi.collection.filter((j : Long) => j == i || j % i != 0) } println(mi.collection) 

ModifyingIterator keeps track of the current item and allows you to reassign the collection that is used for iteration. The next element is always larger than the current element.

Of course, you should probably use a better data structure that does not keep track of the current value, but retains a pointer to the current element in order to get rid of a useless search each time.

Answer 4

There is an interesting article: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

I tried to translate the Haskell code referenced in this article to Scala, but I did not test the performance.

 object primes { type SI = Stream[Int] def sieve:SI = { def wheel2357:SI = Stream(4,2,4,6,2,6,4,2,4,6,6, 2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6, 6,4,2,4,6,2,6,4,2,4,2,10,2,10,2) append wheel2357 def spin(s:SI, n:Int):SI = Stream.cons(n, spin(s.tail, n + s.head)) case class It(value:Int, step:Int) { def next = new It(value + step, step) def atLeast(c:Int):It = if (value >= c) this else new It(value + step, step).atLeast(c) } implicit object ItOrdering extends Ordering[It] { def compare(thiz:It, that:It) = { val r = thiz.value - that.value if (r == 0) thiz.step - that.step else r } } import scala.collection.immutable.TreeSet def sieve(cand:SI, set:Set[It]):SI = { val c = cand.head val set1 = TreeSet[It]() ++ set.dropWhile(_.value < c) ++ set.takeWhile(_.value < c).map(_.atLeast(c)) if (set1.elements.next.value == c) { val set2 = TreeSet[It]() ++ set1.dropWhile(_.value == c) ++ set1.takeWhile(_.value == c).map(_.next) sieve(cand.tail, set2) } else { Stream.cons(c, sieve(cand.tail, set1 + It(c*c,2*c))) } } Stream(2,3,5,7,11) append sieve(spin(wheel2357,13), new TreeSet[It] + It(121,22)) } def main(args:Array[String]) { sieve.takeWhile(_ < 1000).foreach(println) } }