zipWithIndex

A common desire is to have access to the index of an element when using collection methods like foreach, filter, foldLeft/Right, etc... Fortunately there is a simple way.

List('a','b','c','d').zipWithIndex.

But wait!

Does that not trigger an extra iteration through the collection?. Indeed it does and that is where Views help.

List('a','b','c','d').view.zipWithIndex

When using a view the collection is only traversed when required so there is no performance loss.

Here are some examples of zipWithIndex:

1. scala> val list = List('a','b','c','d')
2. list: List[Char] = List(a, b, c, d)
4. /*
5. I like to use functions constructed with case statements
6. in order to clearly label the index.  The alternative is 
7. to use x._2 for the index and x._1 for the value
8. */
9. scala> list.view.zipWithIndex foreach {case (value,index) => println(value,index)}
10. (a,0)
11. (b,1)
12. (c,2)
13. (d,3)
15. // alternative syntax without case statement
16. scala> list.view.zipWithIndex foreach {e => println(e._1,e._2)}
17. (a,0)
18. (b,1)
19. (c,2)
20. (d,3)
22. /*
23. Fold left and right functions have 2 parameters (accumulator, nextValue) 
24. using a case statement allows you to expand that but watch the brackets!
25. */
26. scala> (list.view.zipWithIndex foldLeft 0) {case (acc,(value,index)) => acc + value.toInt + index} 
27. res14: Int = 400
29. // alternative syntax without case statement
30. scala> (list.view.zipWithIndex foldLeft 0) {(acc,e) => acc + e._1.toInt + e._2} 
31. res23: Int = 400
33. /*
34. alternative foldLeft operator.  The thing I like about this
35. syntax is that it has the initial accumulator value on the left 
36. in the same position as the accumulator parameter in the function.
38. The other thing I like about it is that visually you can see that it starts with
39. "" and the folds left
40. */
41. scala> ("" /: list.view.zipWithIndex) {                          
42.      | case (acc, (value, index)) if index % 2 == 0 => acc + value
43.      | case (acc, _) => acc                                       
44.      | }
45. res15: java.lang.String = ac
47. /*
48. This example filters based on the index then uses map to remove the index
49. force simply forces the view to be processed.  (I love these collections!)
50. */
51. scala> list.view.zipWithIndex.filter { _._2 % 2 == 0 }.map { _._1}.force
52. res29: Seq[Char] = List(a, c)

Non-strict (lazy) Collections

This topic discusses non-strict collections. There is a fair bit of confusion with regards to non-strict collections: what to call them and what are they. First lets clear up some definitions.

Pre Scala 2.8 collections have a projection method. This returns a non-strict collections. So often non-strict collections are called projections in Pre Scala 2.8
Scala 2.8+ the method was changed to view, so in Scala 2.8+ view sometimes refers to non-strict collections (and sometime to a implicit conversion of a class)
Another name for non-strict collections I have seen is "lazy collections."

All those labels are for the same thing "non-strict collections" which is the functional programming term and which I will use for the rest of this topic.

As an excellent addition to this topic please take a look at Strict Ranges? by Daniel Sobral.

One way to think of non-strict collections are pull collections. A programmer can essentially form a sequence of functions and the evaluation is only performed on request.

Note: I am intentionally adding side effects to the processes in order to demonstrate where processing takes place. In practice the collectionsshould be immutable (ideally) and the processing the collections really should be side-effect free. Otherwise almost guaranteed you will find yourself with a bug that is almost impossible to find.

Example of processing a strict collection:

1. scala> var x=0
2. x: Int = 0
4. scala> def inc = {
5.      | x += 1
6.      | x
7.      | }
8. inc: Int
10. scala> var list =  List(inc _, inc _, inc _)
11. list: List[() => Int] = List(<function0>, <function0>, <function0>)
13. scala> list.map (_()).head
14. res0: Int = 1
16. scala> list.map (_()).head
17. res1: Int = 4
19. scala> list.map (_()).head
20. res2: Int = 7

Notice how each time the expression is called x is incremented 3 times. Once for each element in the list. This demonstrates that map is being called for every element of the list even though only head is being calculated. This is strict behaviour.

Example of processing a non-strict collection with Scala 2.7.5
For Scala 2.8 change project => view.

1. scala> var x=0
2. x: Int = 0
4. scala> def inc = {
5.      | x += 1
6.      | x
7.      | }
8. inc: Int
10. scala> var list =  List(inc _, inc _, inc _)
11. list: List[() => Int] = List(<function0>, <function0>, <function0>)
13. scala> list.projection.map (_()).head
14. res0: Int = 1
16. scala> list.projection.map (_()).head
17. res1: Int = 2
19. scala> list.projection.map (_()).head
20. res2: Int = 3
22. scala> list.projection.map (_()).head
23. res3: Int = 4

Here you can see that only one element in the list is being calculated for the head request. That is the idea behind non-strict collections and can be useful when dealing with large collections and very expensive operations. This also demonstrates why side-effects are so crazy dangerous!.

More examples (Scala 2.8):

1. scala> var x=0
2. x: Int = 0
4. scala> def inc = { x +=1; x }
5. inc: Int
7. // strict processing of a range and obtain the 6th element
8. // this will run inc for every element in the range
9. scala> (1 to 10).map( _ + inc).apply(5)
10. res2: Int = 12
12. scala> x
13. res3: Int = 10
15. // reset for comparison
16. scala> x = 0
17. x: Int = 0
19. // now non-strict processing but the same process
20. // you get a different answer because only one
21. // element is calculated
22. scala> (1 to 10).view.map( _ + inc).apply(5)
23. res6: Int = 7
25. // verify that x was incremented only once
26. scala> x
27. res7: Int = 1
29. // reset for comparison
30. scala> x = 0
31. x: Int = 0
33. // force forces strict processing
34. // now we have the same answer as if we did not use view
35. scala> (1 to 10).view.map( _ + inc).force.apply(5)
36. res9: Int = 12
38. scala> x
39. res10: Int = 10
41. // reset for comparison
42. scala> x = 0
43. x: Int = 0
45. // first 5 elements are computed only
46. scala> (1 to 10).view.map( _ + inc).take(5).mkString(",")
47. res9: String = 2,4,6,8,10
49. scala> x
50. res10: Int = 5
52. // reset for comparison
53. scala> x = 0
54. x: Int = 0
56. // only first two elements are computed
57. scala> (1 to 10).view.map( _ + inc).takeWhile( _ < 5).mkString(",")
58. res11: String = 5,7
60. scala> x
61. res12: Int = 5
63. // reset for comparison
64. scala> x = 0
65. x: Int = 0
67. // inc is called 2 for each element but only the last 5 elements are computed so
68. // x only == 10 not 20
69. scala> (1 to 10).view.map( _ + inc).map( i => inc ).drop(5).mkString(",")
70. res16: String = 2,4,6,8,10
72. scala> x
73. res17: Int = 10
75. scala> x = 0                                             
76. x: Int = 0
78. // define this for-comprehension in a method so that
79. // the repl doesn't call toString on the result value and
80. // as a result force the full list to be processed
81. scala> def add = for( i <- (1 to 10).view ) yield i + inc
82. add: scala.collection.IndexedSeqView[Int,IndexedSeq[_]]
84. scala> add.head                                          
85. res5: Int = 2
87. // for-comprehensions will also be non-strict if the generator is non-strict
88. scala> x
89. res6: Int = 1