Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Incrementing the for loop (loop variable) in scala by power of 5

Tags:

loops

scala

I had asked this question on Javaranch, but couldn't get a response there. So posting it here as well:

I have this particular requirement where the increment in the loop variable is to be done by multiplying it with 5 after each iteration. In Java we could implement it this way:

for(int i=1;i<100;i=i*5){}

In scala I was trying the following code-

var j=1
for(i<-1.to(100).by(scala.math.pow(5,j).toInt))
{
  println(i+" "+j)
  j=j+1
}

But its printing the following output: 1 1 6 2 11 3 16 4 21 5 26 6 31 7 36 8 .... ....

Its incrementing by 5 always. So how do I got about actually multiplying the increment by 5 instead of adding it.

like image 927
MohamedSanaulla Avatar asked Nov 16 '10 12:11

MohamedSanaulla


1 Answers

Let's first explain the problem. This code:

var j=1
for(i<-1.to(100).by(scala.math.pow(5,j).toInt))
{
  println(i+" "+j)
  j=j+1
}

is equivalent to this:

var j = 1
val range: Range = Predef.intWrapper(1).to(100)
val increment: Int = scala.math.pow(5, j).toInt
val byRange: Range = range.by(increment)
byRange.foreach {
  println(i+" "+j)
  j=j+1
}

So, by the time you get to mutate j, increment and byRange have already been computed. And Range is an immutable object -- you can't change it. Even if you produced new ranges while you did the foreach, the object doing the foreach would still be the same.

Now, to the solution. Simply put, Range is not adequate for your needs. You want a geometric progression, not an arithmetic one. To me (and pretty much everyone else answering, it seems), the natural solution would be to use a Stream or Iterator created with iterate, which computes the next value based on the previous one.

for(i <- Iterator.iterate(1)(_ * 5) takeWhile (_ < 100)) {
  println(i)
}

EDIT: About Stream vs Iterator

Stream and Iterator are very different data structures, that share the property of being non-strict. This property is what enables iterate to even exist, since this method is creating an infinite collection1, from which takeWhile will create a new2 collection which is finite. Let's see here:

val s1 = Stream.iterate(1)(_ * 5) // s1 is infinite
val s2 = s1.takeWhile(_ < 100)    // s2 is finite
val i1 = Iterator.iterate(1)(_ * 5) // i1 is infinite
val i2 = i1.takeWhile(_ < 100)      // i2 is finite

These infinite collections are possible because the collection is not pre-computed. On a List, all elements inside the list are actually stored somewhere by the time the list has been created. On the above examples, however, only the first element of each collection is known in advance. All others will only be computed if and when required.

As I mentioned, though, these are very different collections in other respects. Stream is an immutable data structure. For instance, you can print the contents of s2 as many times as you wish, and it will show the same output every time. On the other hand, Iterator is a mutable data structure. Once you used a value, that value will be forever gone. Print the contents of i2 twice, and it will be empty the second time around:

scala> s2 foreach println
1
5
25

scala> s2 foreach println
1
5
25

scala> i2 foreach println
1
5
25

scala> i2 foreach println

scala> 

Stream, on the other hand, is a lazy collection. Once a value has been computed, it will stay computed, instead of being discarded or recomputed every time. See below one example of that behavior in action:

scala>     val s2 = s1.takeWhile(_ < 100)    // s2 is finite
s2: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> println(s2)
Stream(1, ?)

scala> s2 foreach println
1
5
25

scala> println(s2)
Stream(1, 5, 25)

So Stream can actually fill up the memory if one is not careful, whereas Iterator occupies constant space. On the other hand, one can be surprised by Iterator, because of its side effects.

(1) As a matter of fact, Iterator is not a collection at all, even though it shares a lot of the methods provided by collections. On the other hand, from the problem description you gave, you are not really interested in having a collection of numbers, just in iterating through them.

(2) Actually, though takeWhile will create a new Iterator on Scala 2.8.0, this new iterator will still be linked to the old one, and changes in one have side effects on the other. This is subject to discussion, and they might end up being truly independent in the future.

like image 67
Daniel C. Sobral Avatar answered Sep 25 '22 01:09

Daniel C. Sobral