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)

Return value of a block

A common misunderstanding is that a code block (without parameters) is a function. That is not the case. A code block is a sequence of statements that are executed and result the last statement is returned. That sounds like a Function0, however, if the block is passed to a method/function only the last statement will be returned to the function/method. If that method/function expects a function as the parameter the last statement maybe returned as a function not a value, this means that the block itself is not a function.

1. scala> var count = 0                                                                                                                         
2. count: Int = 0
4. // the last statement is returned as a function so count
5. // is incremented only one during the creation of the function
6. scala> List(1,2,3,4).map{count += 1;_ + 1}
7. res9: List[Int] = List(2, 3, 4, 5)
9. scala> count
10. res10: Int = 1
12. // now the count increment is within the function
13. scala> List(1,2,3,4).map{i => count += 1;i + 1}
14. res11: List[Int] = List(2, 3, 4, 5)
16. scala> count
17. res12: Int = 5

The previous example demonstrates a Gotcha if I ever saw one. Map expects a function so the block essentially constructs a function. The last statement being the function. The first line count += 1 executed only once because it is part of creating the function not part of the resulting function. This is equivalent to:

1. scala> val x = {count += 1 ; i:Int => i +1}
2. x: (Int) => Int = < function1>
4. scala> List(1,2,3,4).map(x)
5. res15: List[Int] = List(2, 3, 4, 5)

Beginning a block with the parameter list signals that the entire block is a function.

Rule of thumb: Functions with placeholder parameters should be a single statement.

Type Inference with Abstract Types

A second "gotcha" that one might get tripped up when dealing with abstract types is the signature of the concrete class contains type information about the abstract type. So if you are not explicit when assigning a variable or defining a function you can get unexpected compiler errors.

1. scala> trait S {
2.      |   type x
3.      |   def get : x
4.      | }
5. defined trait S
7. scala> var sample = new S{ 
8.      |   type x = Int
9.      |   def get = 3
10.      | }
11. sample: java.lang.Object with S{type x = Int} = $anon$1@397af435
13. scala> sample = new S {
14.      |   type x = Double
15.      |   def get = 3.0
16.      | }
17. < console>:7: error: type mismatch;
18.  found   : java.lang.Object with S
19.  required: java.lang.Object with S{type x = Int}
20.        sample = new S {

In this example sample uses type inference so the actual type is S with underlying type Int. The consequence is that sample can only be assigned with instances of S with type x = Int. The fix is to explicitly declare the variable type:

1. scala> var sample2 : S = new S{ 
2.      |   type x = Int
3.      |   def get = 3
4.      | }
5. sample2: S = $anon$1@31602bbc
7. scala> sample2 = new S {
8.      |   type x = Double
9.      |   def get = 3.0
10.      | }
11. sample2: S = $anon$1@4de5ed7b

The same thing happens when declaring functions and allows type inference for function definition

1. scala> class Fac {
2.      |   def newS = new S {
3.      |     type x = Int
4.      |     def get = 3
5.      |   }
6.      | }
7. defined class Fac
9. scala> class SubFac extends Fac{
10.      |   override def newS = new S {
11.      |     type x = Double
12.      |     def get = 3.0
13.      |   }
14.      | }
15. < console>:8: error: type mismatch;
16.  found   : java.lang.Object with S
17.  required: java.lang.Object with S{type x = Int}
18.          override def newS = new S {

The fix for this example is to be explicit in the definition of the function in the superclass

Instance Type (Abstract type gotcha 1)

In a previous post about abstract types I showed one of the benefits of using abstract types over parameterized types. Abstract Types vs Parameter. The next several posts will feature potential problems you may encounter when using Abstract Types.

I should point out that abstract types are not inherently difficult to understand but they are rather different from anything you will see when you come from the Java world so if you are new to them I would use them with caution at first.

In the abstract types example you will notice that the abstract type 'I' in Foreach is not within the trait Source rather it is outside in the Foreach trait. At first one might consider putting the type in Source rather than Foreach. The naive change can get you in trouble (but there is a couple easy fixes)

1. trait Foreach[A] {
2.   trait Source {
3.     type I <: java.io.Closeable  // moved this line into Source
4.     def in : I
5.     def next(in : I) : Option[A]
6.   }
7.   def source : Source
8.   
9.   def foreach[U](f : A => U) : Unit = {
10.     val s = source.in
11.     try {
12.       def processNext : Unit = source.next(s) match {
13.         case None => 
14.           ()
15.         case Some(value) => 
16.           f(value)
17.           processNext
18.       }
19.       
20.       processNext
21.     } finally {
22.       // correctly handle exceptions
23.       s.close
24.     }
25.   }
26. }

Compiling the class results in a compilation error:

jeichar: tmp$ scalac XX.scala
XX.scala:12: error: type mismatch;
found : s.type (with underlying type Foreach.this.Source#I)
required: _2.I where val _2: Foreach.this.Source
def processNext : Unit = source.next(s) match {
^
XX.scala:16: error: type mismatch;
found : value.type (with underlying type Any)
required: A
f(value)
^
two errors found

So what is the problem? The problem is simple but subtle. Notice that source is defined as a def. So calling source 2 times may return 2 different instances of Source. A simple change can fix this. Either change def source : Source to val source : Source. Or change the method foreach to assign the result from source to a val.

1. trait Foreach {
2.   trait Source {
3.     type I <: java.io.Closeable  // moved this line into Source
4.     def in : I
5.     def next(in : I) : Option[Int]
6.   }
7.   def source : Source
8.   
9.   def foreach[U](f : Int => U) : Unit = {
10.     // this assignment allows this example to compile
11.     val sameSource = source
12.     val s = sameSource.in
13.     try {
14.       def processNext : Unit = sameSource.next(s) match {
15.         case None => 
16.           ()
17.         case Some(value) => 
18.           f(value)
19.           processNext
20.       }
21.       
22.       processNext
23.     } finally {
24.       // correctly handle exceptions
25.       s.close
26.     }
27.   }
28. }

Abstract Types vs Parameter

This topic (and the next) are intended to discuss abstract types. A class/trait with an abstract type is quite similar to a class/trait type parameter. For example:

1. trait C[A] {
2.   def get : A
3.   def doit(a:A):A
4. }
6. trait C2 {
7.   type A
8.   def get : A
9.   def doit(a:A):A
10. }

Both implementations have similar properties. However they are NOT the same. At first I thought that I could used them inter-changeably. However, consider the following examples:

1. //compiles
2. def p(c:C[Int]) = c.doit(c.get)
4. // doesn't compile
5. def p2(c:C2) = c.doit(c.get)

So why doesn't p2 compile? Because it returns A. From the signature of p2 it is impossible to know what p2 returns. There are several ways to fix this problem. One make the method return Unit:

1. // compiles because the internals of C2 does not leak out
2. def p(c:C2):Unit = c.doit(c.get)

Another fix would be to change doit to return Unit or an explicit return value like Int

1. trait C2 {
2.   type A
3.   def get : A
4.   def doit(a:A):Int
5. }
7. // compiles correctly
8. def p(c:C2) = c.doit(c.get)

A second difference between parameterized types and types with abstract type values is illustrated below:

1. trait C2 {
2.    type A
3.    def get : A
4. }
6. scala> var c : C2 = new C2 { 
7.      | type A = Int
8.      | def get = 3
9.      | }
10. c: C2 = $anon$1@11a40fff
12. // what is the type of result if at compile time the
13. // value of c is not known
14. scala> var result = c.get
15. result: C2#A = 3
17. scala> c = new C2 {      
18.      |    type A = String
19.      |    def get = "hi"
20.      | }
21. c: C2 = $anon$1@5f154718
23. // crazy eh :) the variable can be anything but does not
24. // have type Any so you cannot assign arbitrary values
25. scala> result = c.get
26. result: C2#A = hi
28. scala> result.isInstanceOf[String]
29. res0: Boolean = true
31. // while the dynamic type of result is a string the
32. // static type is not so you cannot assign a string to result
33. scala> result = "4"
34. < console> :8: error: type mismatch;
35.  found   : java.lang.String("4")
36.  required: C2#A
37.        result = "4"
38.                 ^

The obvious question is what use are abstract types. I don't claim to know them all but the main point is that they do not expose the internal implementation details to the world. The famous cake pattern is one such example usage of abstract types.

I read the following as well (wish I could remember where):

Abstract types are good when extending and there will be concrete subclasses. Param type good for when a type is useful without extension but can handle several types.

A simpler example is examined here. It is loosely based on a real world usecase.
The example below is contrived so that it is smaller than the actual usecase, so consider the design and not the fact that the example could be easier done with other examples. In the real scenario this design reduced the lines of duplicated code from around 500 to 10.

The example below shows how a Traversable like object can be created from InputStreams and Readers. The important aspect is that the type signature of Foreach does not leak information about the implementation. Users of a Foreach object don't care whether it is backed onto an InputStream or Reader. They just care about the type of object contained.

I am leaving this already long post here. The next post will investigate different ways you can get in trouble trying to implement using abstract types.

1. import java.io.{InputStream, Reader, ByteArrayInputStream, StringReader}
2. import java.net.URL
4. object Foreach {
5.   def fromStream(s: => InputStream) = new Foreach[Int] {
6.     type I = InputStream
7.     def source = new Source {
8.       def in = s
9.       def next(_in : InputStream) = _in.read match {
10.         case -1 => None
11.         case i => Some(i)
12.       }
13.     }
14.   }
15.   
16.   def fromReader(s: => Reader) = new Foreach[Char] {
17.     type I = Reader
18.     def source = new Source {
19.       def in = s
20.       def next(_in : Reader) = _in.read match {
21.         case -1 => None
22.         case i => Some(i.toChar)
23.       }
24.     }
25.   }
26.   
27.   
28.   def fromInputAndFunction[A](s: => InputStream, f: Int => A) = new Foreach[A] {
29.     type I = InputStream
30.     def source = new Source {
31.       def in = s
32.       def next(_in : InputStream) = _in.read match {
33.         case -1 => None
34.         case i => Some(f(i))
35.       }
36.     }
37.   }
38.   
39.   
40. }
42. trait Foreach[A] {
43.   type I <: java.io.Closeable
44.   trait Source {
45.     def in : I
46.     def next(in : I) : Option[A]
47.   }
48.   def source : Source
49.   
50.   def foreach[U](f : A => U) : Unit = {
51.     val s = source.in
52.     try {
53.       def processNext : Unit = source.next(s) match {
54.         case None => 
55.           ()
56.         case Some(value) => 
57.           f(value)
58.           processNext
59.       }
60.       
61.       processNext
62.     } finally {
63.       // correctly handle exceptions
64.       s.close
65.     }
66.   }
67. }
69. object Test {
70.   def main(args : Array[String]) = {
71.     val data = "Hello World"
72.     val bytes = data.toArray.map { _.toByte }
73.     import Foreach._
74.     fromStream(new ByteArrayInputStream(bytes)).foreach {a => print(a.toChar)}
75.     
76.     println
78.     fromReader(new StringReader(data)) foreach print
79.     
80.     println
81.     
82.     fromInputAndFunction(new ByteArrayInputStream(bytes), i => i.toChar) foreach print
83.     
84.     println
85.   }
86. }

Filter with FlatMap (or collect)

I picked up this tip from one of Daniel Spiewak's tweets. He tweeted a pro tip that uses flatMap to create a filtered list:

1. list flatMap {
2.   case st: String => Some(st)
3.   case _ => None
4. }

At a glance one might wonder why not simply use list.filter{_.isInstanceOf[String]}. The difference is that the flatMap will return a List[String].

However Scala 2.8 offers the collect method for doing a similar thing.

1. def strings(list: List[Any]) = list flatMap {
2.   case st: String => Some(st)
3.   case _ => None
4. }
6. // returned list is a List[String]
7. scala> strings("hi" :: 1 :: "world" :: 4 :: Nil)
8. res11: List[String] = List(hi, world)
10. // returned list is a List[Any] (not as useful)
11. scala> "hi" :: 1 :: "world" :: 4 :: Nil filter {_.isInstanceOf[String]}
12. res12: List[Any] = List(hi, world)
14. // collect returns List[String]
15. scala> "hi" :: 1 :: "world" :: 4 :: Nil collect {case s:String => s}           
16. res13: List[String] = List(hi, world)

Implicit Parameter Resolution

This topic is a continuation of the previous implicit parameter topics:

• Implicit Parameters
• Companion Object Implicits

This topic provides some explanation about how implicit parameters are resulted. There are very strict rules for which implicit value is to be applied to a implicit parameter. A simple way to think about it is that the "closest" definition will be used. Local scope, enclosing class, parent class, companion object of the desired type.

1. class X(val i:Int)
2. class Y(val i:Int)
4. object X {
5.   implicit def xx = new X(1)
6. }
8. class Method {
9.   def x(implicit x:X)=println(x.i)
10.   def y(implicit y:Y)=println(y.i)
11. }
13. trait M { 
14.   self : Method =>
16.   implicit def x1 = new X(10)
17.   implicit def y1 = new Y(100)
19.   def testy = y
20.   def testx = x
21. }
22. trait SM extends M {
23.   self : Method =>
25.   implicit def x2 = new X(20)
26.   implicit def y2 = new Y(200)
27.   
28.   def testy2 = y  
29. }
31. // implicit resolved from companion object of X
32. new Method().x
33. // explicit applied so that value is used
34. new Method().x(new X(3))
35. // implicit resolved from companion object of X
36. // NOT from M.  This is because the call site of x 
37. // is not within M therefore does not use the implicits in M
38. // for resolution.
39. (new Method with M).x
41. implicit def x = new X(30)
42. // local scope overrides companion object implicit
43. new Method().x
44. // explicit applied so that value is used
45. new Method().x(new X(3))
46. // local scope overrides companion object implicit
47. (new Method with M).x
49. // testy is defined within M so the implicits within M
50. (new Method with M).testy
51. // testx is defined within M so the implicit within M
52. // overrides the companion object implicit
53. (new Method with M).testx
54. // testy is within M (not SM) so the implicit within M
55. // is used
56. (new Method with SM).testy
57. // testy2 is within SM so the implicit within SM 
58. // overrides the implicit in M and the companion object
59. (new Method with SM).testy2

Output:

1
3
1
30
3
30
100
10
100
200

Implicit Parameters

Evidently the topic of implicit parameters has not yet been correctly addressed. There have been several topic that refer to implicit parameters but none that directly discuss them. So before I continue with the topic of implicit parameter resolution I will discuss implicit parameters.

First, implicit parameters are not the same as implicit object conversions. Implicit parameters provide a way to allow parameters of a method to be "found". This is similar to default parameters at a glance but in fact is a different mechanism for finding the "default" value. It differs from implicit object conversion in that it is only a way for parameters for a method to be resolved. Implicit object conversion allows methods to appear to be called on one object when in fact that object is being converted behind the scenes to another type. (more or less)

An implicit parameter is a parameter to method or constructor that is marked as implicit. This means that if a parameter value is not supplied then the compiler will search for an "implicit" value defined within scope (according to resolution rules.) Implicit parameter resolution rules will be discussed soon.

Example:

1. scala> def p(implicit i:Int) = print(i)
2. p: (implicit i: Int)Unit
4. // defining a val/var/def as implicit 
5. // means that it will be considered during implicit resolution
6. scala> implicit val v=2
7. v: Int = 2
9. // scope is searched for a implicit value to sue
10. // v is found as marked implicit
11. scala> p               
12. 2
14. // explicit declarations always overrides implicit values
15. scala> p(1)
16. 1

Implicit parameters are very nice for simplifying APIs. For example the collections use implicit parameters to supply CanBuildFrom objects for many of the collection methods. This is because normally the user does not need to be concerned with those parameters. Another example is supplying an encoding to an IO library so the encoding is defined once (perhaps in a package object) and all methods can use the same encoding without having to define it for every method call.

One important restriction is that there can only be a single implicit keyword per method. It must be at the start of a parameter list (which also makes all values of that parameter list be implicit). I further understand that only the last parameter list may be implicit.

Here are several illegal examples:

1. // implicit is not in last parameter list
2. scala> def pp(implicit i:Int, a:Int)(b:Int) = println(a,i)                 
3. < console>:1: error: '=' expected but '(' found.
4.        def pp(implicit i:Int, a:Int)(b:Int) = println(a,i)
6. // there are 2 implicit parameters
7. scala> def pp(implicit j:Int, a:Int)(implicit i:Int,b:Int) = println(a,i)
8. < console>:1: error: '=' expected but '(' found.
9.       def pp(implicit j:Int, a:Int)(implicit i:Int,b:Int) = println(a,i)
11. // implicit is not the first parameter of the parameter list
12. scala> def pp(a:Int, implicit i:Int) = println(i,j)         
13. < console>:1: error: identifier expected but 'implicit' found.
14.        def pp(a:Int, implicit i:Int) = println(i,j)
15.                      ^

Here are several legal examples (Updated with useage examples):

1. scala> implicit def v = 7
2. v: Int
4. scala> implicit var x = 10L
5. x: Long
7. // i is implicit
8. scala> def pp(a:Int)(implicit i:Int) = println(a,i)
9. pp: (a: Int)(implicit i: Int)Unit
11. scala> pp(3)
12. (3,7)
14. // both i and b are implicit
15. scala> def pp(a:Int)(implicit i:Int, b:Long) = println(a,i,b) 
16. pp: (a: Int)(implicit i: Int,implicit b: Long)Unit
18. scala> pp(4)               
19. (4,7,10)
21. // both i and b are implicit
22. scala> def pp(implicit i:Int, b:Long) = println(i,b)  
23. pp: (implicit i: Int,implicit b: Long)Unit
25. scala> pp
26. (7,10)
28. // all or none of the parameters must be supplied
29. scala> pp(2)
30. < console>:13: error: not enough arguments for method pp: (implicit i: Int,implicit b: Long)Unit.
31. Unspecified value parameter b.
32.        pp(2)
34. // This is syntactically legal but I cannot seem to implicitly invoke this
35. // I would recommend: def pp(b:Long*)(implicit i:Int) = println(i,b)
36. scala> def pp(implicit i:Int, b:Long*) = println(i,b)
37. pp: (implicit i: Int,implicit b: Long*)Unit
39. scala> pp(3,1,2,3)
40. (3,WrappedArray(1, 2, 3))
42. scala> def pp(b:Long*)(implicit i:Int) = println(i,b)
43. pp: (b: Long*)(implicit i: Int)Unit
45. scala> pp(1,2,3)
46. (7,WrappedArray(1, 2, 3))

A related topic is Companion Object implicits.

Break Performance

In the Breaks comments there were several questions about the performance of the Scala break command vs the Java break command. So I decided to take a look.

The code for the tests is available on GitHub at: Scala Benchmarks. Feel free to play around with it.

I personally don't think these tests say anything of particular import because they only test how fast the Java break is vs the Scala break without doing any work in the loop. So I don't expect these number would ever been seen in the real world. However that said if you have a tight loop with minimal processing then a Scala break may not be the correct construct to use.

Here is the Java test (labelled JavaSimpleBreak)

1. int i = 0;
2. while (i < 10) {
3.   if(i==1) break;
4.   i += 1;
5. }

Here is the Scala test (labelled ScalaSimpleBreak)

1. var i = 0;
2. breakable {
3.   while (i < 10) {
4.     if(i==1) break;
5.     i += 1;
6.   }
7. }

Out of curiosity I also added a test that created a new Exception each iteration (labelled ScalaException):

1. var i = 0;
2.   while (i < 10) {
3.     if(i==1) throw new Exception();
4.     i += 1;
5.   }

And also a test that just throws the same ScalaBreak exception each time. This one is weird since Scala Simple Break also throws the same exception but is much much faster so I think there is something about popping the stack in the example compared to the ScalaSimpleBreak test.

1. var i = 0;
2. breakable {
3. while (i < 10) {
4. if(i==1) break;
5. i += 1;
6. }
7. }

The results of the tests:

First, don't compare the break tests to the Exception tests. They are sufficiently different to not be worth comparing.
Second, remember that this is a micro benchmark and has very little relationship to reality.

90000000 iterations. Swapping every 90000000 tests
JavaSimpleBreak = 254 (0.0016279129387033098)
ScalaSimpleBreak = 2475 (0.015862537493270438)
ScalaBreakException = 18806 (0.12052964852462379)
ScalaException = 156028 (1.0)

90000000 iterations. Swapping every 500000 tests
JavaSimpleBreak = 772 (0.005138547761203965)
ScalaSimpleBreak = 2351 (0.015648608531853004)
ScalaBreakException = 19346 (0.12876987692778744)
ScalaException = 150237 (1.0)

90000000 iterations. Swapping every 500 tests
JavaSimpleBreak = 790 (0.005242446563543097)
ScalaSimpleBreak = 2247 (0.014911110668710557)
ScalaBreakException = 19213 (0.1274976276270298)
ScalaException = 150693 (1.0)

Companion Object Implicits

When a method requires an implicit there are several ways that the implicit is resolved. One way is to search for an implicit definition in the companion object of the required type. For example: def x(implicit m:MyClass) parameter m will search local scope, class hierarchy and the MyClass companion object for an implicit val or def. (More on implicit resolution later).

To demonstrate the method put the following code block into a file and run the script:

1. class X(val i:Int) {
2.   def add(implicit x:X)=println(x.i+i)
3. }
5. object X {
6.   implicit def xx = new X(3)
7. }
9. // implicit is obtained from companion object of X
10. new X(3).add
12. val other = new {
13.   def print(implicit x:X)=println(x.i)
14. }
16. // implicit is obtained from companion object of X
17. other.print
19. implicit def x = new X(32)
21. // implicit is obtained local scope
22. other.print

Running: scala impl.scala should produce:
6
3
32

Breaks

Scala 2.8 added the break control flow option. It is not implemented as a special language feature. Rather it is simply implemented as an object/trait using standard Scala mechanisms. If you are interested in creating a control flow object similar to this look at the Defining Custom Control Structures post.

The Break functionality is works basically how you would expect:

1. // Import the control flow methodsmethods
2. scala> import util.control.Breaks._
3. import util.control.Breaks._
5. // pass a function to the breakable method
6. scala> breakable {
7.      | for (i <- 1 to 10 ) {
8.      | if(i > 5) break  // call break when done
9.      | println(i)
10.      | }
11.      | }
12. 1
13. 2
14. 3
15. 4
16. 5

Pretty intuitive but beware, break only breaks out to the first enclosing breakable. Here is an example of the issue:

1. scala> def loop(f : Int => Boolean) = breakable {
2.      | for (i <- 1 to 300) if (f(i)) break else println(i)
3.      | }
4. loop: (f: (Int) => Boolean)Unit
6. // This never ends because break is caught by breakable in the loop method
7. scala> breakable {
8.      | while(true) {
9.      | loop{ i => break; true }
10.      | }
11.      | }

Fortunately the implementers provide an elegant way to handle these sorts of cases. The Breaks object extends the Breaks class. By instantiating other instances of Breaks it is possible to control which breaks capture

1. scala> import scala.util.control._
2. import scala.util.control._
4. scala> 
6. scala> def loop(f : Int => Boolean) = {
7.      |   val Inner = new Breaks
8.      |   Inner.breakable {
9.      |     for (i <- 1 to 4) if (f(i)) Inner.break else println(i)
10.      |   }
11.      | }
12. loop: (f: (Int) => Boolean)Unit
14. scala> 
16. scala> val Outer = new Breaks
17. Outer: scala.util.control.Breaks = scala.util.control.Breaks@1ba4806
19. scala> Outer.breakable {
20.      |   while(true) {
21.      |     loop{ i => if(i==4) Outer.break; false}
22.      |   }
23.      | }
24. 1
25. 2
26. 3

Scala 2.8 Arrays are not Traversables

One performance/consistency change that has been make in Scala 2.8 is to make Scala Array always be a Java Array. This has some consequences which we will examine in this post. The biggest one is that Array is not a Scala Collection/Traversable. It is implicitly converted to one but it is not an instance of a Traversable. There are several reasons this was done. Probably the biggest is for performance. Because a Scala array is a Java array there is no overhead when using a Scala array.

Thanks to implicit type conversion all the normal collection methods are useable with an array. Even better, after running a method like map the result will again be a Java array. So the API is much more consistent.

An example illustrating that an Array is not a Traversable:

1. // This does not compile (which is good) 
2. // because Traversable[Int] can never be an array
3. scala> def x(t:Traversable[Int]) = t match {
4.      | case x : Array[Int] => true          
5.      | }
6. < console>:13: error: pattern type is incompatible with expected type;
7.  found   : Array[Int]
8.  required: Traversable[Int]
9.        case x : Array[Int] => true
10.                 ^
11. < console>:13: error: type mismatch;
12.  found   : Array[Int]
13.  required: Traversable[Int]
14.        case x : Array[Int] => true
15.               ^

Another example:

1. scala> def x(t:Traversable[Int]) = t.isInstanceOf[Array[_]]
2. x: (t: Traversable[Int])Boolean
4. /* this evaluates to false because Array is converted
5.  * to WrappedArray because it has to be implicitly converted
6.  * to a Traversable.  Since Array is not a Traversable the resulting 
7.  * object is not an Array
8.  */
9. scala> x(Array(1,2,3))                                     
10. res24: Boolean = false
12. scala> def x(t:Traversable[Int]) = println(t)
13. x: (t: Traversable[Int])Unit
15. // This method call demonstrates the previous assertion
16. scala> x(Array(1,2,3))                                            
17. WrappedArray(1, 2, 3)

So suppose you want to be able to accept and use arrays and Traversables in a method but you want to be able to
check that the parameter is an Array. Why not match against WrappedArray. You probably can, but you may get performance improvements in some cases if you don't require wrapping the array.

For a more concrete example of why you may want to do this. In a Input/Output routine I wrote I would write the data one way if the input was an Array: stream.write(array). But if the input was a traversable then I would have to handle it differently. My particular issue was more complicated than that but that is the basic issue.

So the work around is to define a Generic parameter for the method:

1. scala> def x[T <% Traversable[Int]](t:T) = t match { 
2.      | case x : Array[Int] => true                                
3.      | }
4. x: [T](t: T)(implicit evidence$1: (T) => Traversable[Int])Boolean
6. scala> x(Array(1,2,3))                               
7. res27: Boolean = true

A quick note. ScalaDays Rocks! Wish you were here :)

This topic just demonstrates a cute little trick that can occasionally be quite useful:

1. scala> List(1,2,3) ++ Some(4)
2. res0: List[Int] = List(1, 2, 3, 4)
4. scala> List(1,2,3) ++ None   
5. res1: List[Int] = List(1, 2, 3)

Options are implicitly converted to Iterables, so Options can be appended to collections.

1. scala> val x : Iterable[Int] = None       
2. x: Iterable[Int] = List()
4. scala> val x : Iterable[Int] = Some(4)
5. x: Iterable[Int] = List(4)

Creating Custom Traversable implementations

One of the most talked about features of Scala 2.8 is the improved Collections libraries. Creating your own implementation is trivial, however if you want your new collection to behave the same way as all the included libraries there are a few tips you need to be aware of.

Note: All of these examples can either be ran in the REPL or put in a file and ran

Starting with the simple implementation:

1. import scala.collection._
2. import scala.collection.generic._
4. class MyColl[A](seq : A*) extends Traversable[A] {
5.     // only abstract method in traversable is foreach... easy :) 
6.   def foreach[U](f: A => U) = util.Random.shuffle(seq.toSeq).foreach(f)
7. }

This is a silly collection I admit but it is custom :).

This example works but if you test the result of a map operation (or any other operation that returns a new instance of the collection) you will notice it is not an instance of MyColl. This is expected because unless otherwise defined Traversable will return a new instance of Traversable.

To demonstrate run the following tests:

1. val c = new MyColl(1, 2, 3)
2. println (c mkString ",")
3. println(c mkString ",")
5. println(c drop 1 mkString ",")
7. // this two next assertions fail (see following explanation)
8. assert(c.drop(1).isInstanceOf[MyColl[_]])
9. assert((c map {_ + 1}).isInstanceOf[MyColl[_]])

Both assertions will fail. The reason for these failures is because the collection is immutable which dictates by necessity that a new object must be returned from filter/map/etc... Since the Traversable trait returns instances of Traversable these two assertions fail. The easiest way to make these methods return an instance of MyColl is to make the following changes/additions.

1. import scala.collection._
2. import scala.collection.generic._
4. /*
5. Adding GenericTraversableTemplate will delegate the creation of new
6. collections to the companion object.  Adding the trait and
7. companion object causes all the new collections to be instances of MyColl
8. */
9. class MyColl[A](seq : A*) extends Traversable[A] 
10.                              with GenericTraversableTemplate[A, MyColl] {
11.   override def companion = MyColl
12.   def foreach[U](f: A => U) = util.Random.shuffle(seq.toSeq).foreach(f)
13. }
15. // The TraversableFactory trait is required by GenericTraversableTemplate
16. object MyColl extends TraversableFactory[MyColl] {
17. /* 
18. If you look at the signatures of many methods in TraversableLike they have an
19. implicit parameter canBuildFrom.  This allows one to define how the returned collections
20. are built.  For example one could make a list's map method return a Set
21. In this case we define the default canBuildFrom for MyColl
22. */
23.   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, MyColl[A]] = new GenericCanBuildFrom[A]
24. /*  
25. The method that builds the new collection.  This is a simple implementation
26. but it works.  There are other implementations to assist with implementation if
27. needed
28. */
29.   def newBuilder[A] = new scala.collection.mutable.LazyBuilder[A,MyColl[A]] {
30.     def result = {
31.       val data = parts.foldLeft(List[A]()){(l,n) => l ++ n}
32.       new MyColl(data:_*)
33.     }
34.   }
35. }

Now instances of MyColl will be created by the various filter/map/etc... methods and that is fine as long as the new object is not required at compile-time. But suppose we added a method to the class and want that accessible after applying methods like map and filter.

Adding val o : MyColl[Long] = c map {_.toLong} to the assertions will cause a compilation error since statically the class returned is Traversable[Long]. The fix is easy.

All that needs to be done is to add with TraversableLike[A, MyColl[A]] to MyColl and we are golden. There may be other methods as well but this works and is simple.

Note that the order in which the traits are mixed in is important. TraversableLike[A, MyColl[A]] must be mixed in after Traversable[A]. The reason is that we want methods like map and drop to return instances of MyColl (statically as well as dynamically). If the order was reversed then those methods would return Traversable event though statically the actual instances would still be MyColl.

1. import scala.collection._
2. import scala.collection.generic._
4. class MyColl[A](seq : A*) extends Traversable[A]
5.                              with GenericTraversableTemplate[A, MyColl] 
6.                              with TraversableLike[A, MyColl[A]] {
7.   override def companion = MyColl
8.   def foreach[U](f: A => U) = util.Random.shuffle(seq.toSeq).foreach(f)
9. }
11. object MyColl extends TraversableFactory[MyColl] {  
12.   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, MyColl[A]] = new GenericCanBuildFrom[A]
13.   def newBuilder[A] = new scala.collection.mutable.LazyBuilder[A,MyColl[A]] {
14.     def result = {
15.       val data = parts.foldLeft(List[A]()){(l,n) => l ++ n}
16.       new MyColl(data:_*)
17.     }
18.   }
19. }

Now add in a new method to demonstrate that the new collection works as desired and we are done.

The following is the complete implementation with the tests. You can put it in a file and run scala <filename> or paste it into a REPL

1. import scala.collection._
2. import scala.collection.generic._
3. import scala.collection.mutable.{ Builder, ListBuffer }
5. class MyColl[A](seq : A*) extends Traversable[A]
6.                              with GenericTraversableTemplate[A, MyColl] 
7.                              with TraversableLike[A, MyColl[A]] {
8.   override def companion = MyColl
9.   def foreach[U](f: A => U) = util.Random.shuffle(seq.toSeq).foreach(f)
11.   def sayhi = println("hi!")
12. }
14. object MyColl extends TraversableFactory[MyColl] {  
15.   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, MyColl[A]] = new GenericCanBuildFrom[A]
16.   def newBuilder[A] = new ListBuffer[A] mapResult (x => new MyColl(x:_*))
17. }
19. val c = new MyColl(1, 2, 3)
20. println (c mkString ",")
21. println(c mkString ",")
23. assert(c.drop(1).isInstanceOf[MyColl[_]])
24. assert((c map {_ + 1}).isInstanceOf[MyColl[_]])
26. val o : MyColl[Int] = c filter {_ < 2}
27. println(o mkString "," )
28. o.sayhi