95

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.

4
  • These are all good responses. What am I missing from Java 'for' loops is the ability to have multiple initializers, and the ability to "iterate" using more than just increments/decrements. This is one instance where Java can be more concise than Scala.
    – snappy
    Commented Jul 26, 2011 at 21:35
  • ..."iterate" using more than just increments/decrements... In scala it is possible to iterate with step, or iterate with "if" condition in loop header. Or you're looking for something else?
    – om-nom-nom
    Commented Jul 26, 2011 at 21:44
  • 1
    /*Java*/ for(int i=0, j=0; i+j<100; i+=j*2, j+=i+2) {...} How can you do this in 1 line in Scala?
    – snappy
    Commented Jul 26, 2011 at 21:51
  • 3
    @snappy : In my opinion, the most natural translation to Scala would be a while loop. As I recall, there was a debate some years ago whether Scala should inherit Java's for(;;) loop, and it was decided that the benefit was not enough to justify the added complexity. Commented Jul 26, 2011 at 22:47

12 Answers 12

146

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)
6
  • 6
    Nice idea, only one traversal, but it also creates n pairs, even if it does not create a new collection proper.
    – snappy
    Commented Jul 26, 2011 at 16:59
  • 2
    Quite right. Well there may be a vague hope that the JVM might optimize those creation away, but I would not count on that. I do not see a solution that would not be based on iterating on indexes then. Commented Jul 26, 2011 at 17:06
  • 1
    @snappy This one should have been chosen as an answer! Accessing elements by index, which was suggested in most other answers, violates the functional nature of Scala and performs awfully on linked lists (like List, the most used collection in Scala) - and not only on them. Check out the apply operation over here. In a linked list -like collection every access to an element by index results in a traversal of the list. Commented May 28, 2012 at 13:54
  • quite a different approaches are shown here: stackoverflow.com/questions/6821194/…
    – Neil
    Commented Feb 23, 2016 at 11:43
  • Why is this efficient? it is creating a new array object, and uses an additional function (`view') so I find it hard to see why this is efficient to the developer nor the machine, aside from feeling smartly idiomatic.
    – matanox
    Commented Mar 22, 2016 at 13:19
77

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. How to optimize for-comprehensions and loops in Scala?

(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.

4
  • +1 for mentioning indices method/function as I find it way preferable due to its virtually eliminating a whole set of off-by-one programming errors. Commented Jul 27, 2011 at 12:59
  • 1
    It must be noted here that if xs is of any kind of linked list (such as the widely used List), accessing its elements by index like xs(i) will be linear and thus the for (i <- xs.indices) println(i + " : " + xs(i)) will perform way worse than even for((x, i) <- xs.zipWithIndex) println(i + " : " + x), as it will result in much more than just two traversals under the hood. Therefore the answer of @didierd suggesting to use views should be accepted as the most general one and the most idiomatic one, IMO. Commented May 28, 2012 at 13:56
  • 1
    If maximum efficiency is needed (for example, in numerical computing) it is faster to index arrays than to traverse a linked list. The nodes of a linked list are separately heap allocated, and jumping across different memory locations doesn't play well with the CPU cache. If a view is used, this even high level of abstraction will put more pressure on the heap and GC. In my experience there is often a factor of 10 in performance to be gained by avoiding heap allocation in numerical code. Commented May 28, 2012 at 18:42
  • Hi. I am new to Scala. I would like to ask why there is no "=" when you defined your printArray() function?
    – Seven
    Commented Jul 26, 2023 at 6:42
20

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
1
  • 5
    I really like your pointing out the indices method/function. It reduces complexity and virtually eliminates a whole set of "off by one" errors which is the most common programming error/bug in all of software engineering. Commented Jul 27, 2011 at 12:56
17

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
4
  • 5
    xs(i) on lists raises complexity to O(n^2)
    – Vadzim
    Commented Nov 19, 2013 at 21:35
  • @Vadzim That's true, but that would also be the case in Java in you used a for loop on the indices with a LinkedList
    – francoisr
    Commented Aug 10, 2015 at 19:33
  • 1
    In the case of xs(i) on Arrays, the above code is O(n), right? Since Arrays in scala offer near-constant time random access? Commented Nov 27, 2016 at 4:39
  • 3
    @dhfromkorea yes, should be fast for Arrays (indeed O(n))
    – om-nom-nom
    Commented Nov 27, 2016 at 22:23
6

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
5

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))
5

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);

   }
}
4

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.

3

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)
}
2
  • This is something that will definitely make sense to be added to the standard library.
    – snappy
    Commented Jul 26, 2011 at 21:41
  • 1
    I'm not so sure, since if you want to conform to the usual foreach/map APIs you're stuck with tuples anyway. Commented Jul 26, 2011 at 22:09
2

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) 
2

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
    }
0

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!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.