Efficient iteration with index in Scala
ScalaIterationScala Problem Overview
Since Scala does not have old Java style for loops with index,
// does not work
val xs = Array("first", "second", "third")
for (i=0; i<xs.length; i++) {
println("String #" + i + " is " + xs(i))
}
How can we iterate efficiently, and without using var's?
You could do this
val xs = Array("first", "second", "third")
val indexed = xs zipWithIndex
for (x <- indexed) println("String #" + x._2 + " is " + x._1)
but the list is traversed twice - not very efficient.
Scala Solutions
Solution 1 - Scala
Much worse than traversing twice, it creates an intermediary array of pairs.
You can use view. When you do collection.view, you can think of subsequent calls as acting lazily, during the iteration. If you want to get back a proper fully realized collection, you call force at the end. Here that would be useless and costly. So change your code to
for((x,i) <- xs.view.zipWithIndex) println("String #" + i + " is " + x)
Solution 2 - Scala
It has been mentioned that Scala does have syntax for for loops:
for (i <- 0 until xs.length) ...
or simply
for (i <- xs.indices) ...
However, you also asked for efficiency. It turns out that the Scala for syntax is actually syntactic sugar for higher order methods such as map, foreach, etc. As such, in some cases these loops can be inefficient, e.g. https://stackoverflow.com/questions/6146182/how-to-optimize-for-comprehensions-and-loops-in-scala/6146626#6146626
(The good news is that the Scala team is working on improving this. Here's the issue in the bug tracker: https://issues.scala-lang.org/browse/SI-4633)
For utmost efficiency, one can use a while loop or, if you insist on removing uses of var, tail recursion:
import scala.annotation.tailrec
@tailrec def printArray(i: Int, xs: Array[String]) {
if (i < xs.length) {
println("String #" + i + " is " + xs(i))
printArray(i+1, xs)
}
}
printArray(0, Array("first", "second", "third"))
Note that the optional @tailrec annotation is useful for ensuring that the method is actually tail recursive. The Scala compiler translates tail-recursive calls into the byte code equivalent of while loops.
Solution 3 - Scala
One more way:
scala> val xs = Array("first", "second", "third")
xs: Array[java.lang.String] = Array(first, second, third)
scala> for (i <- xs.indices)
| println(i + ": " + xs(i))
0: first
1: second
2: third
Solution 4 - Scala
Actually, scala has old Java-style loops with index:
scala> val xs = Array("first","second","third")
xs: Array[java.lang.String] = Array(first, second, third)
scala> for (i <- 0 until xs.length)
| println("String # " + i + " is "+ xs(i))
String # 0 is first
String # 1 is second
String # 2 is third
Where 0 until xs.length or 0.until(xs.length) is a RichInt method which returns Range suitable for looping.
Also, you can try loop with to:
scala> for (i <- 0 to xs.length-1)
| println("String # " + i + " is "+ xs(i))
String # 0 is first
String # 1 is second
String # 2 is third
Solution 5 - Scala
How about this?
val a = Array("One", "Two", "Three")
a.foldLeft(0) ((i, x) => {println(i + ": " + x); i + 1;} )
Output:
0: One
1: Two
2: Three
Solution 6 - Scala
Looping in scala is pretty simple. Create any array of your choice for ex.
val myArray = new Array[String](3)
myArray(0)="0";
myArray(1)="1";
myArray(2)="2";
Types of loops,
for(data <- myArray)println(data)
for (i <- 0 until myArray.size)
println(i + ": " + myArray(i))
Solution 7 - Scala
I have the following approaches
object HelloV2 {
def main(args: Array[String]) {
//Efficient iteration with index in Scala
//Approach #1
var msg = "";
for (i <- args.indices)
{
msg+=(args(i));
}
var msg1="";
//Approach #2
for (i <- 0 until args.length)
{
msg1 += (args(i));
}
//Approach #3
var msg3=""
args.foreach{
arg =>
msg3 += (arg)
}
println("msg= " + msg);
println("msg1= " + msg1);
println("msg3= " + msg3);
}
}
Solution 8 - Scala
Indeed, calling zipWithIndex on a collection will traverse it and also create a new collection for the pairs. To avoid this, you can just call zipWithIndex on the iterator for the collection. This will just return a new iterator that keeps track of the index while iterating, so without creating an extra collection or additional traversing.
This is how scala.collection.Iterator.zipWithIndex is currently implemented in 2.10.3:
def zipWithIndex: Iterator[(A, Int)] = new AbstractIterator[(A, Int)] {
var idx = 0
def hasNext = self.hasNext
def next = {
val ret = (self.next, idx)
idx += 1
ret
}
}
This should even be a bit more efficient than creating a view on the collection.
Solution 9 - Scala
There's nothing in the stdlib that will do it for you without creating tuple garbage, but it's not too hard to write your own. Unfortunately I've never bothered to figure out how to do the proper CanBuildFrom implicit raindance to make such things generic in the type of collection they're applied to, but if it's possible, I'm sure someone will enlighten us. :)
def foreachWithIndex[A](as: Traversable[A])(f: (Int,A) => Unit) {
var i = 0
for (a <- as) {
f(i, a)
i += 1
}
}
def mapWithIndex[A,B](in: List[A])(f: (Int,A) => B): List[B] = {
def mapWithIndex0(in: List[A], gotSoFar: List[B], i: Int): List[B] = {
in match {
case Nil => gotSoFar.reverse
case one :: more => mapWithIndex0(more, f(i, one) :: gotSoFar, i+1)
}
}
mapWithIndex0(in, Nil, 0)
}
// Tests....
@Test
def testForeachWithIndex() {
var out = List[Int]()
ScalaUtils.foreachWithIndex(List(1,2,3,4)) { (i, num) =>
out :+= i * num
}
assertEquals(List(0,2,6,12),out)
}
@Test
def testMapWithIndex() {
val out = ScalaUtils.mapWithIndex(List(4,3,2,1)) { (i, num) =>
i * num
}
assertEquals(List(0,3,4,3),out)
}
Solution 10 - Scala
Some more ways to iterate:
scala> xs.foreach (println)
first
second
third
foreach, and similar, map, which would return something (the results of the function, which is, for println, Unit, so a List of Units)
scala> val lens = for (x <- xs) yield (x.length)
lens: Array[Int] = Array(5, 6, 5)
work with the elements, not the index
scala> ("" /: xs) (_ + _)
res21: java.lang.String = firstsecondthird
folding
> for(int i=0, j=0; i+j<100; i+=j*2, j+=i+2) {...} can be done with recursion:
def ijIter (i: Int = 0, j: Int = 0, carry: Int = 0) : Int =
if (i + j >= 100) carry else
ijIter (i+2*j, j+i+2, carry / 3 + 2 * i - 4 * j + 10)
The carry-part is just some example, to do something with i and j. It needn't be an Int.
for simpler stuff, closer to usual for-loops:
scala> (1 until 4)
res43: scala.collection.immutable.Range with scala.collection.immutable.Range.ByOne = Range(1, 2, 3)
scala> (0 to 8 by 2)
res44: scala.collection.immutable.Range = Range(0, 2, 4, 6, 8)
scala> (26 to 13 by -3)
res45: scala.collection.immutable.Range = Range(26, 23, 20, 17, 14)
or without order:
List (1, 3, 2, 5, 9, 7).foreach (print)
Solution 11 - Scala
A simple and efficient way, inspired from the implementation of transform in SeqLike.scala
var i = 0
xs foreach { el =>
println("String #" + i + " is " + xs(i))
i += 1
}
Solution 12 - Scala
The proposed solutions suffer from the fact that they either explicitly iterate over a collection or stuff the collection into a function. It is more natural to stick with the usual idioms of Scala and put the index inside the usual map- or foreach-methods. This can be done using memoizing. The resulting code might look like
myIterable map (doIndexed(someFunction))
Here is a way to achieve this purpose. Consider the following utility:
object TraversableUtil {
class IndexMemoizingFunction[A, B](f: (Int, A) => B) extends Function1[A, B] {
private var index = 0
override def apply(a: A): B = {
val ret = f(index, a)
index += 1
ret
}
}
def doIndexed[A, B](f: (Int, A) => B): A => B = {
new IndexMemoizingFunction(f)
}
}
This is already all you need. You can apply this for instance as follows:
import TraversableUtil._
List('a','b','c').map(doIndexed((i, char) => char + i))
which results in the list
List(97, 99, 101)
This way, you can use the usual Traversable-functions at the expense of wrapping your effective function. Enjoy!