Tuesday, November 3, 2009

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

2 comments:

  1. Lazy is usually reserved for describing non-strict function which cache the result. So:

    val x = 0 // strict
    lazy val x = 0 // non-strict, lazy
    def x = 0 // non-strict, non-lazy

    ReplyDelete
  2. I absolutely agree but this blog has a strong focus on C/Java developers and coming from the Java world non-strict is meaningless. So I threw Lazy in so they approach the problem with the correct mind-set

    ReplyDelete