Iterator.Sliding

This topic requires Scala 2.8 or higher.

Iterator and Iterable have most of the most useful methods when dealing with collections. Fold, Map, Filter are probably the most common. But other very useful methods include grouped/groupBy, sliding, find, forall, foreach, and many more. I want to cover Iterator's sliding method.

The def sliding[B >: A](size : Int, step : Int) : GroupedIterator[B] method provides a sliding window on the iterator. The first parameter is the size of the window and the second is the number of elements to skip each time the window is moved. If step == size then this method is the same as grouped. Step defaults to one

Examples:

1. // notice resulting lists are all 3 long and increases by 1
2. scala> (1 to 5).iterator.sliding(3).toList
3. res18: List[Sequence[Int]] = List(List(1, 2, 3), List(2, 3, 4), List(3, 4, 5))
5. // step is 3 so now there are only 2 groups
6. scala> (1 to 5).iterator.sliding(4, 3).toList
7. res19: List[Sequence[Int]] = List(List(1, 2, 3, 4), List(4, 5))
9. // withPartial(false) makes the partial group be ignored
10. scala> (1 to 5).iterator.sliding(4, 3).withPartial(false).toList
11. res21: List[Sequence[Int]] = List(List(1, 2, 3, 4))
13. scala> val it2 = Iterator.iterate(20)(_ + 5)
14. it2: Iterator[Int] = non-empty iterator
16. // withPadding fills in the partial group
17. // notice with padding is by-name (it is executed each time it is called)
18. scala> (1 to 5).iterator.sliding(4, 3).withPadding(it2.next).toList
19. res23: List[Sequence[Int]] = List(List(1, 2, 3, 4), List(4, 5, 20, 25))

Introduction to Actors

The support for Actors is one of the features that attracts many new developers to Scala. It is not the only concurrancy construct in Scala but it is one of the most recognized.

An actor is essentially an active object. Instead of calling methods on the actor messages are passed to the actor and the message will be handled in a thread. Resources about actors can be found all over the internet a couple pages to look at are:

• Scala Actors: A Short Tutorial
• Event-Based Programming without Inversion of Control (PDF)
• Actors That Unify Threads and Events

This is a big topic about how threads are scheduled and so on but for now we will write a simple little program that downloads several webpages in parallel.

1. scala> import scala.actors.Actor
2. import scala.actors.Actor
4. scala> import Actor._
5. import scala.actors.Actor._
7. scala>  val collector = actor {
8.      |   var count = 3
9.      |   var data = ""
10.      |   loop {
11.      |   react { 
12.      |    case payload:String => {
13.      |      reply ("thank you")
14.      |      data += payload + "\n\n"
15.      |      count -= 1
16.      |      if (count == 0) {
17.      |        println (data)
18.      |        exit()
19.      |     }
20.      |    }
21.      |  }
22.      | }
23.      | }
24. collector: scala.actors.Actor = scala.actors.Actor$$anon$1@2bbef4c6
26. scala> import scala.io.Source
27. import scala.io.Source
29. scala> class Downloader(url:String) extends Actor {
30.      |  def act = {
31.      |   val source = Source.fromURL(new java.net.URL(url))
32.      |   val data = source.getLines.mkString("\n")
33.      |   collector ! data
34.      |   receive { case s => println("Done with "+url) }
35.      |  }
36.      | }
37. defined class Downloader
39. scala> List("http:/daily-scala.blogspot.com/2009/11/using-objects-as-functions.html",
40.      |      "http:/daily-scala.blogspot.com/2009/10/boolean-extractors.html",
41.      |      "http:/daily-scala.blogspot.com/2009/08/java-vs-scala-control-structures.html",
42.      |      "http:/www.blogger.com/profile/07600430363435495915")
43. res0: List[java.lang.String] = List(http:/daily-scala.blogspot.com/2009/11/using-objects-as-functions.html, http:/daily-scala.blogspot.com/2009/10/boolean-extractors.html, http:/daily-scala.blogspot.com/2009/08/java-vs-scala-control-structures.html, http:/www.blogger.com/profile/07600430363435495915)
45. scala> for (url <- res0) { 
46.      | new Downloader(url).start
47.      | }
49. [snip... lots of output]

Update:
If this program is put into a file and executed it will not finish is because the program exits. What is happening is there are 6 "actors" the main thread, collector and the 4 Downloaders. The main thread completes and shutdown the system taking all the Actors with it.

Just add link(collector) as the last line to make the main trhead wait for collector.

Also important to realize is that in Scala 2.7 an actor is lightweight. IE the application can exit while actors are still alive. In Scala 2.8 that is changed. For Scala 2.7 semantics you must use a DaemonActor instead of Actor.

Using objects as functions

A fun but easily overlooked fact is that many classes inherit from a Function class and therefore can be used where "normal" functions can be used.

1. scala> List(1,2) map (Map(1->"one",2->"two"))
2. res0: List[java.lang.String] = List(one, two)
4. scala> List(3,3,2) map (List('a', 'b', 'c','d'))
5. res2: List[Char] = List(d, d, c)

BigInt in Scala

One of the best examples of why it is so great to use Scala for API design is BigInt. Using BigInt in Java is a real headache because of the limitations of Java with regards to API design. Scala in comparison makes using BigInt no different than using Ints (with execution that there is not a BigInt literal).

1. // BigInt objects can be created from ints
2. scala> val x = BigInt(1500)
3. x: BigInt = 1500
5. // or longs
6. scala> val y = BigInt(8839200231L)
7. y: BigInt = 8839200231
9. // or strings
10. scala> val z = BigInt("1234566789008723457802308972345723470589237507")
11. z: BigInt = 1234566789008723457802308972345723470589237507
13. // then thanks to scala you can multiply/divide/add/subtract etc...
14. // as if it was a Scala literal
15. scala> x * y * z
16. res0: BigInt = 16368874569886254973831932331037537269641764816982396175500
18. // by importing implicits you can also directly multiply big ints with integers and longs
19. // however remember to put the big in first so that the int is converted to big int
20. // because you cannot do Int * BigInt.  It must be BigInt * Int
21. scala> import BigInt._
22. import BigInt._
24. scala> x * y * z * 124
25. res1: BigInt = 2029740446665895616755159609048654621435578837305817125762000

Function._

If you have not looked at the Function object I would recommend you do. It contains several useful methods for combining and converting functions.

Examples:

1. cala> def twoParamFunc( i:Int, j:String) = println(i,j)
2. twoParamFunc: (i: Int,j: String)Unit
4. // the tupled method converts the function with n parameters into
5. // a function that takes one tupleN
6. scala> val tupled = Function tupled twoParamFunc _
7. tupled: ((Int, String)) => Unit = < function1>
9. scala> tupled (1 -> "one") 
10. (1,one)
12. // A practical use-case is to convert an existing method
13. // for use with a Map
15. // Example with out using the tupled method
16. scala> Map( 1 -> "one", 2 -> "two") map (entry => twoParamFunc(entry._1, entry._2)) 
17. (1,one)
18. (2,two)
19. res5: scala.collection.immutable.Iterable[Unit] = List((), ())
21. // example using tupled
22. scala> Map( 1 -> "one", 2 -> "two") map (tupled)  
23. (1,one)
24. (2,two)
25. res7: scala.collection.immutable.Iterable[Unit] = List((), ())
27. // and for balance the opposite
28. scala> val untupled = Function untupled tupleParamFunc _
29. untupled: (Int, String) => Unit = < function2>
31. scala> untupled(1, "one") 
32. tuple = (1,one)
34. // Chain is for chaining together an arbitrary number of functions
36. scala> def inc(i:Int) = i + 1 
37. inc: (i: Int)Int
39. scala> def double(i:Int) = i*i
40. double: (i: Int)Int
42. scala> def decr(i:Int) = i - 1
43. decr: (i: Int)Int
45. scala> (Function chain List(inc _, double _, decr _, double _, inc _, inc _))(3)
46. res10: Int = 227
48. // Now examples curries two methods then chains them together
50. // define basic methods
51. scala> def inc(step:Int,i:Int) = i + step 
52. inc: (step: Int,i: Int)Int
54. scala> def multiply(i:Int, j:Int) = i * j
55. multiply: (i: Int,j: Int)Int
57. // Convert them to methods where the first argument is 3
58. scala> val inc3 = (Function curried inc _)(3)
59. inc3: (Int) => Int = < function1>
61. scala> val multiplyBy3 = (Function curried multiply _)(3)
62. multiplyBy3: (Int) => Int = < function1>
64. // chain the resulting Function1 objects together and execute chain with parameter 3
65. // (3 + 3)*3 = 18
66. scala> chain(List(inc3, multiplyBy3))(3)
67. res12: Int = 18

Access modifiers (public, private, protected)

By default classes, objects and class members (fields, methods) are all public.
IE:

1. object PublicObject {
2.   val publicVal
3.   var publicVar
4.   def publicMethod = 1
5. }

In this example everything is public. Similar to Java there is private and protected (there is no public because that is default). Private works as it does in Java but protected is dramatically different.

• The first difference is that protected can have two forms: protected and protected[foo]. Where foo can be a class, package or object.


• The second difference is that the non-parameterized protected for is only visible from subclasses not from the same package.

1. scala> class Class1 {
2.      | protected def pMethod = "protected"
3.      | }
4. defined class Class1
6. scala> class Class2 { 
7. // pMethod is not accessible because Class2 is not a subclass of Class1
8.      | new Class1().pMethod 
9.      | }
10. <console>:6: error: method pMethod cannot be accessed in Class1
11.        new Class1().pMethod
12.                     ^
14. scala> class Class3 extends Class1 {
15. // also unlike Java, protected restricts to the same object
16.      | new Class1().pMethod
17.      | }
18. <console>:6: error: method pMethod cannot be accessed in Class1
19.        new Class1().pMethod
20.                     ^
22. scala> class Class3 extends Class1 {
23.      | pMethod
24.      | }
25. defined class Class3

If the protected is parameterized then only classes that fall into the parameter category can access the parameter:

1. scala> class Class1 {                                
2. // protected[Class1] is equivalent to private
3.      | protected[Class1] def method() = println("hi")
4.      | method()
5.      | }
6. defined class Class1
8. scala> new Class1()
9. hi
10. res0: Class1 = Class1@dc44a6d
12. // this does not work because method is only accessible in Class1
13. scala> class Class2 extends Class1 { method() }      
14. <console>:5: error: not found: value method
15.        class Class2 extends Class1 { method() }
16.                                      ^
17. scala> object Module {                                         
18.      |   object Inner1 {                                         
19.      |     protected[Inner1] def innerMethod = println("hi")       
20.      |     protected[Module] def moduleMethod = println("moduleMethod")
21.      |
22.      |     object InnerInner { 
23.      |       // InnerInner is within Inner1 so the access works
24.      |       def callInner = innerMethod
25.      |     }
26.      |   }
27.      |   // module method is protected[Module] so anything in Module can access it
28.      |   def callModuleMethod = Inner1.moduleMethod
29.      |
30.      |   object Inner2 {
31.      |     // Inner1.module method is protected[Module] and 
32.      |     // Inner2 is within module so therefore has access
33.      |     def callModuleMethod = Inner1.moduleMethod
34.      |   }
35.      | }
36. defined module Module
38. scala> Module.callModuleMethod
39. moduleMethod
41. scala> Module.Inner1.InnerInner.callInner
42. hi
44. scala> Module.Inner1.innerMethod         
45. <console>:6: error: method innerMethod cannot be accessed in object Module.Inner1
46.        Module.Inner1.innerMethod
47.                      ^
49. scala> Module.Inner1.moduleMethod
50. <console>:6: error: method moduleMethod cannot be accessed in object Module.Inner1
51.        Module.Inner1.moduleMethod

The following example shows how package access works in Scala 2.8. They have to be compiled as 2 files.

Root.scala:

1. package root
3. class Class1 {
4.   protected[root] def rootMethod = println("rootMethod")
5. }
7. class Class2 {
8.   // same package so this is legal
9.   new Class1().rootMethod
10. }

Subpackage.scala

1. package root.sub
3. class Class3 {
4.   // Class3 is in a subpackage of root so 
5.   // it can access all objects protected by
6.   // protected[root] as well as objects
7.   // protected by protected[root.sub]
8.   new root.Class1().rootMethod
9. }

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