Introducing Streams

Streams are a special type of Iterable/Traversable whose elements are not evaluated until they are requested. Streams are normally constructed as functions.

A Scala List basically consists of the head element and the rest of the list. A Scala Stream is the head of the stream and a function that can construct the rest of the Stream. It is a bit more than this because each element is evaluated only once and stored in memory for future evaluations. That should be more clear after some examples.

As usual I created these examples with the Scala 2.8 REPL but I think most if not all should work in 2.7.

1. scala> import Stream.cons          
2. import Stream.cons
3. /*
4. Because streams are very functional in nature it is recommended that methods from the Stream object are used for creation
6. This is a real boring example of creating a Stream.  Anything this simple should be a list.
8. The important part is that cons take the value at the point and a function to return the rest of the
9. stream NOT another stream.  
10. */
11. scala> val stream1 = cons(0,cons(1,Stream.empty))
12. stream1: Stream.Cons[Int] = Stream(0, ?)
14. scala> stream1 foreach {print _}                 
15. 01
17. /*
18. This illustrates the similarity in design between Stream and list, again the difference is the entire list is created in a stream the second argument of cons is not evaluated until it is requested
19. */
20. scala> new ::(0, new ::(1,List.empty))
21. res35: scala.collection.immutable.::[Int] = List(0, 1)
24. /*
25. To drive home the point of the similarities.  Here is an alternative declaration of a
26. stream most similar to declaring a list
27. */
28. scala> val stream2 = 0 #:: 1 #:: Stream.empty    
29. stream2: scala.collection.immutable.Stream[Int] = Stream(0, ?)
31. scala> stream2 foreach {print _}
32. 01
34. scala> 0 :: 1 :: Nil
35. res36: List[Int] = List(0, 1)
37. /*
38. A little more interesting now.  The accessing the second element will run the function.  Notice it is not evaluated until request
39. */
40. scala> val stream3 = cons (0, {    
41.      | println("getting second element")
42.      | cons(1,Stream.empty)
43.      | })
44. stream3: Stream.Cons[Int] = Stream(0, ?)
46. scala> stream3(0)
47. res56: Int = 0
49. // function is evaluated
50. scala> stream3(1)
51. getting second element
52. res57: Int = 1
54. /* 
55. Function is only evaluated once.  
57. Important! This means that all elements in a Stream are loaded into a memory so
58. it can cause a OutOfMemoryError if the stream is large
59. */
60. scala> stream3(1)
61. res58: Int = 1
63. scala> stream3(1)
64. res59: Int = 1
66. /*
67. This creates an infinate stream then forces resolution of all elements
68. */
69. scala> Stream.from(100).force            
70. java.lang.OutOfMemoryError: Java heap space
72. // Alternative demonstration of laziness
73. scala> val stream4 = 0 #:: {println("hi"); 1} #:: Stream.empty
74. stream4: scala.collection.immutable.Stream[Int] = Stream(0, ?)
76. scala> stream4(1)
77. hi
78. res2: Int = 1

A very common way to construct a Stream is to define a recursive method. Each recursive call constructs a new element in the stream. The method may or may not have a guard condition that terminates the stream.

1. // construct a stream of random elements
2. scala> def make : Stream[Int] = Stream.cons(util.Random.nextInt(10), make)
3. make: Stream[Int]
5. scala> val infinate = make                                                
6. infinate: Stream[Int] = Stream(3, ?)
8. scala> infinate(5)                                  
9. res10: Int = 6
11. scala> infinate(0)
12. res11: Int = 3
14. // Once evaluated each element does not change
15. scala> infinate(5)
16. res13: Int = 6
18. // this function makes a stream that does terminate
19. scala> def make(i:Int) : Stream[String] = {                  
20.      | if(i==0) Stream.empty                                 
21.      | else Stream.cons(i + 5 toString, make(i-1))           
22.      | }
23. make: (i: Int)Stream[String]
25. scala> val finite = make(5)                       
26. finite: Stream[String] = Stream(10, ?)
28. scala> finite foreach print _                     
29. 109876
31. // One last demonstration of making a stream object
32. scala> Stream.cons("10", make(2))
33. res18: Stream.Cons[String] = Stream(10, ?)
35. /*
36. This method is dangerous as it forces the entire stream to be evaluated
37. */
38. scala> res18.size
39. res19: Int = 3

This is only an introduction. I hope to add a few more topics that focus on Streams because they can be very powerful but are also more challenging to recognize where they should be used instead of a standard collection.

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