Thursday, May 27, 2010

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

8 comments:

  1. "But wait!

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

    This is a perfect example of premature optimization. Worrying about this is almost never worth it.

    ReplyDelete
  2. The latter example (with filter) I'd rather write it with for comprehensions:

    for ((value,index) <- list.zipWithIndex if index % 2 == 0) yield value

    J

    ReplyDelete
  3. The first comment is a perfect example of ideology replacing intelligence. This is a general article on iterating through a collection with an index; it is obviously the right place to mention the double iteration issue and how to solve it and it would be incompetent not to. And using views in this case is not premature optimization, it is simply a matter of understanding one's tools and using them properly; omitting the view would be amateurish -- in the real world, pointlessly doing twice as many list traversals as necessary has consequences.

    ReplyDelete
    Replies
    1. Ideology? I don't think you know what that word means.

      Delete
  4. This article more than 6 months ago was the last post on a daily blog ... wha' happened? I know the blogger is ok because he tweeted yesterday.

    ReplyDelete
  5. sad I know but I have been spending all my spare time on Scala IO. I sadly have much less free time than I would like. :(

    ReplyDelete
  6. Hope you'll get back to blogging again soon! :)

    ReplyDelete
  7. A couple years after your last post and I'm still finding your blog useful and inspiring. Perhaps instead of daily scala, you'd write about your other open source work in Scala? Regardless, thank you for the work done here.

    ReplyDelete