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

Variant Positions 2

This is a continuation of post: Variant Positions 1

...

My first attempt at the Verified was to make it a mutable object (my Java tourettes kicking in). But it cannot be covariant and mutable. Look at the code to see why:

1. class Verified[+A <: V,V](assertion : (V) => Boolean, private var value : A){
2.     assert(assertion(value))
3.     
4.     def a = value
5. // update is illegal.  See the example below
6.     def update[ B >: A <: V](a : B) = value = a
7. }
9. def notNull(obj : AnyRef) = obj != null
10. val v = new Verified(notNull, "hi")
12. /*
13. Up to this point everything looks ok but the next line
14. will assign an object to value which is a reference to a String
15. */
16. v update (new Object())

For Verified to be mutable A must be invariant. If you look at the Mutable collections in Scala they are all invariant.

Here is an interesting example of both invariant and covariant type parameters in a class hierarchy:

1. scala> class X[+A](val x :A)
2. defined class X
4. scala> class Y[A](var a: A) extends X[A](a)
5. defined class Y
7. scala> val x: X[Any] = new Y[String]("hi")
8. x: X[Any] = Y@1732a4df
10. scala> x.asInstanceOf[Y[String]].a="ho"

This example is perfectly legal because no matter how X[Any] is used no illegal assignment in Y can occur. The interesting thing is that the object can be used in covariant usecases when only X is required. This is now the collections in Scala can work.

Here is a little example of collections invariance and covariance in action. In List the parameter is covariant but in Buffer it is invariant

1. scala> def printList(l : List[Any]) = print(l mkString " :: ")
2. printList: (l: List[Any])Unit
4. scala> val buffer = Buffer(1,2,3)
5. buffer: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1, 2, 3)
7. scala> printList(buffer)
8. 1 :: 2 :: 3
10. /*
11. ++ is part of Iterable.  Since Iterable is covariant ++ 
12. returns a new buffer it does not modify the existing buffer
13. All mutators are only defined on invariant traits
14. */
15. scala> buffer ++ List(4)
16. res16: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1, 2, 3, 4)
18. scala> res16 eq buffer
19. res17: Boolean = false
21. /*
22. buffer defines += to add an element to the buffer
23. so res27 is the same buffer with an extra element
24. */
25. scala> buffer += 10
26. res27: buffer.type = ArrayBuffer(1, 2, 3, 10)
28. scala> res27 eq buffer
29. res28: Boolean = true

Zip with a constant value

A simple tip for zipping a List (or other collection) with a single value.

1. scala> Stream.continually("h") zip List(1,2,3,4)
2. res2: scala.collection.immutable.Stream[(java.lang.String, Int)] = Stream((h,1), ?)
4. scala> res2 mkString ","
5. res3: String = (h,1),(h,2),(h,3),(h,4)
7. scala> List(1,2,3,4) zip Stream.continually("h")
8. res4: List[(Int, java.lang.String)] = List((1,h), (2,h), (3,h), (4,h))

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.

Tuples are (not?) Collections

Tuples are quite handy but a potential annoyance is that at a glance they seem list-like but appearances can be deceiving. The normal collection methods are not supported by Tuples. For example suppose you like the simple syntax: (1,2,3) better than List(1,2,3). With the Tuple you cannot do the maps, filters, etc... (with good reason) but there is a use-case for being able to convert a Tuple to a Traversable.

Word of warning. Unlike collections Tuples are very often not homogeneous. IE you do not have Tuple2[Int] you have Tuple2[A,B]. So the best you can do is to map a tuple to an Iterator[Any].

Note: this was done with Scala 2.8 so results may be slightly different with 2.7. But I believe the syntax is valid.

1. // the productIterator method gives access to an iterator over the elements
2. scala> (1,2,3).productIterator.map {_.toString} mkString (",")
3. res1: String = 1,2,3
5. scala> (1,2,3).productIterator foreach {println _}            
6. 1
7. 2
8. 3
10. // if you know the tuple is heterogeneous then you can use partial functions
11. // for casting the elements to a particular type.  
12. scala> (1,2,3).productIterator map {case i:Int => i + 2} foreach {println _}
13. 3
14. 4
15. 5
17. // To get a full Traversable out of the deal you use one of the many
18. // to* methods to convert to Seq, List, Array, etc...
19. scala> (1,2,3).productIterator.toList map {case i:Int => i + 2}      
20. res15: List[Int] = List(3, 4, 5)
22. // and if you want you can use an implicit to clean up the syntax a bit
24. // Problem with this is you need an implicit for each Tuple length
25. scala> implicit def tupleToTraversable[T](t:(T,T,T)) = t.productIterator.toList map { case e:T => e}
26. warning: there were unchecked warnings; re-run with -unchecked for details
27. tupleToTraversable: [T](t: (T, T, T))List[T]
29. scala> (1,2,3) foreach {println _}
30. 1
31. 2
32. 3
34. /* 
35. EDIT:  Dan pointed out that the methods I am using are inherited from the
36. Product super class of Tuple.  So you can do something similar as follows.
38. Note:  I am using the same name as the previous method so that they don't interfer 
39. with one another
40. */
41. scala> implicit def tupleToTraversable[T](t:Product) = t.productIterator.toList map { case e:T => e} 
42. warning: there were unchecked warnings; re-run with -unchecked for details
43. tupleToTraversable: [T](t: Product)List[T]
45. scala> (1,2,3) foreach {println _}
46. 1
47. 2
48. 3
50. // this is interesting... it does cast to int unless required
51. scala> (1,2,'t') foreach {println _}
52. 1
53. 2
54. t
56. // lets verify we are getting correct conversion
57. scala> def inc(l:List[Int]) = l map {_ + 1} 
58. inc: (l: List[Int])List[Int]
61. scala> inc ( (1,2,3))                              
62. res4: List[Int] = List(2, 3, 4)
64. // yep this I expected
65. scala> inc ( (1,2,'t'))
66. java.lang.ClassCastException: java.lang.Character cannot be cast to java.lang.Integer
67. at scala.runtime.BoxesRunTime.unboxToInt(Unknown Source)
68. at $anonfun$inc$1.apply(< console>:7)
69. at scala.collection.TraversableLike$$anonfun$map$1.apply(TraversableLike.scala:238)
70. at .< clinit>(< console>)
72. scala> def inc(l:List[Int]) = l foreach {println _}
73. inc: (l: List[Int])Unit
75. scala> def p(l:List[Int]) = l foreach {println _}  
76. p: (l: List[Int])Unit
78. scala> p ( (1,2,'t'))                              
79. 1
80. 2
81. t

Scala 2.8 Traversable and IndexedSequence

This topic is really just a collection of examples using the Scala 2.8 API. The examples are mostly based on Strings. But because Strings are in fact an IndexedSeq all of these examples also work with Lists arrays and the first several work with all collections.

These examples are all based on first Traversable. The basis of all collections and therefore will work with all collections. And the next set of examples work with IndexedSeq and most will work with Seq as well. Sets, Maps and others still need to be examined.

This is not an exhaustive set of examples and not all are even that interesting (sorry :-) ). But I let out the most trivial unless theay are being compared to others.

Traversable:

1. scala> val license = """Subject of Agreement. ?Product?, as referred to in this Agreement, shall be the binary software package ?Sun VirtualBox,? which Product allows for creating multiple virtual computers, each with different operating systems (?Guest Computers?), on a physical computer with a specific operating system (?Host Computer?), to allow for installing and executing these Guest Computers simultaneously. The Product consists of executable files in machine code for the Solaris, Windows, Linux, and Mac?OS?X operating systems as well as other data files as required by the executable files at run-time and documentation in electronic form. The Product includes all documentation and updates provided to You by Sun under this Agreement and the terms of this Agreement will apply to all such documentation and updates unless a different license is provided with an update or documentation."""
2. res0: RandomAccessSeq[Char] = 
3. license: java.lang.String = ...
5. scala> license count (_ == 'u')
6. res1: Int = 37
8. scala> license split ' ' count {_ == "and"} 
9. res3: Int = 6
10. scala> license ++ " this is silly!"
11. res0: RandomAccessSeq[Char] = ...
13. scala> license dropWhile { _ != 'y'} drop 1 takeWhile { _ != 'y'}
14. res6: Seq[Char] = RandomAccessSeqTW( , s, o, ...
16. scala> license forall {_ != 'z'}
17. res8: Boolean = true
19. scala> (1 until 5).init
20. res0: scala.collection.immutable.Range = Range(1, 2, 3)
22. scala> (1 until 5).head
23. res1: Int = 1
25. scala> (1 until 5).tail
26. res2: scala.collection.immutable.IndexedSeq[Int] = Range(2, 3, 4)
28. scala> (1 until 5).last
29. res3: Int = 4
31. scala> (1 until 5).headOption
32. res4: Option[Int] = Some(1)
34. scala> (1 until 5).lastOption
35. res6: Option[Int] = Some(4)
37. scala> license max   
38. res8: Char = y
40. scala> license min
41. res9: Char =  
43. scala> List() nonEmpty 
44. res10: Boolean = false
46. scala> List() isEmpty 
47. res11: Boolean = true
49. scala> license partialMap {case c if ('a' to 'z' contains c) => c}
50. res13: scala.collection.immutable.IndexedSeq[Any] = IndexedSeq(u, b, j, e, c ...)
52. scala> 1 to 10000 by 2 product 
53. res19: Int = 481029393
55. scala> 1 to 10000 by 2 sum                   
56. res23: Int = 25000000
58. scala> license partition {"aeiou" contains _}
59. res20: (String, String) = (ueoeeeouaeeeoiieeeaeeia ....
61. scala> license span {_ != 'a'}
62. res22: (String, String) = (Subject of Agreement. ?Product?, ,as referred to in this Agreement, shall be the binary software package ?Sun VirtualBox,? which Product allows for creating multiple virtual computers, each with differ ...
64. scala> val consonants = license withFilter {c => !("aeiuo" contains c)}
65. consonants: scala.collection.immutable.StringOps#WithFilter = scala.collection.TraversableLike$WithFilter@78e8a591
67. scala> consonants foreach print _                                      
68. Sbjct f Agrmnt. ?Prdct?, s rfrrd t n ths Agrmnt, shll b th bnry sftwr pckg ?Sn VrtlBx,? whch Prdct llws fr crtng mltpl vrtl cmptrs, ch wth dffrnt prtng systms (?Gst Cmptrs?), n  physcl cmptr wth  spcfc prtng systm (?Hst Cmptr?), t llw fr nstllng nd xctng ths Gst Cmptrs smltnsly. Th Prdct cnssts f xctbl fls n mchn cd fr th Slrs, Wndws, Lnx, nd Mc?OS?X prtng systms s wll s thr dt fls s rqrd by th xctbl fls t rn-tm nd dcmnttn n lctrnc frm. Th Prdct nclds ll dcmnttn nd pdts prvdd t Y by Sn ndr ths Agrmnt nd th trms f ths Agrmnt wll pply t ll sch dcmnttn nd pdts nlss  dffrnt lcns s prvdd wth n pdt r dcmnttn.

IndexedSequense additions to Traversable:

1. scala> '!' +: license    
2. res33: String = !Subject of Agreement
4. scala> "hello" +: license
5. res32: scala.collection.immutable.IndexedSeq[Any] = IndexedSeq(hello, S, u, b, j, e, c, t,  , o, f,  , A, g, r, e, e, m, e, n, t, .,  , ?, P, r, o, d, u, c, t, ?, ,,  , a, s,  , r, e, f, e, r, r, e, d,  , t, o,  , i, n,  , t, h, i, s,  , A, g, r, e, e, m, e, n, t, ,,  , s, h, a, l, l,  , b, e,  , t, h, e,  , b, i, n, a, r, y,  , s, o, f, t, w, a, r, e,  , p, a, c, k, a, g, e,  , ?, S, u, n,  , V, i, r, t, u, a, l, B, o, x, ,, ?,  , w, h, i, c, h,  , P, r, o, d, u, c, t,  , a, l, l
7. scala> license(11)
8. res35: Char = A
10. scala> license diff ("aeiou")
11. res47: String = Sbjct f Agreement. ?Product?, s referred to n this Agreement, shall be the binary software package ?Sun VirtualBox,? which Product allows for creating multiple virtual computers, each with different operating systems (?Guest Computers?), on a physical computer with a specific operating system (?Host Computer?), to allow for installing and executing these Guest Computers simultaneously. The Product consists of executable files in machine code for the Solaris, Windows, Linux, and Mac?OS?X operating systems as well as other data files as required by the executable files at run-time and documentation in electronic form. The Product includes all documentation and updates provided to You by Sun under this Agreement and the terms of this Agreement will apply to all such documentation and updates unless a different license is provided with an update or documentation.
13. scala> license dropRight(30)
14. res48: String = Subject of Agreement. ?Product?, as referred to in this Agreement, shall be the binary software package ?Sun VirtualBox,? which Product allows for creating multiple virtual computers, each with different operating systems (?Guest Computers?), on a physical computer with a specific operating system (?Host Computer?), to allow for installing and executing these Guest Computers simultaneously. The Product consists of executable files in machine code for the Solaris, Windows, Linux, and Mac?OS?X operating systems as well as other data files as required by the executable files at run-time and documentation in electronic form. The Product includes all documentation and updates provided to You by Sun under this Agreement and the terms of this Agreement will apply to all such documentation and updates unless a different license is provided wi
16. scala> license takeRight(10)
17. res49: String = mentation.
19. scala> license indexWhere { "aeiou" contains _} 
20. res4: Int = 1
22. scala> license lastIndexWhere { "aeiou" contains _}
23. res6: Int = 873
25. scala> List(1,2,3) flatten {0 to _}
26. res7: List[Int] = List(0, 1, 0, 1, 2, 0, 1, 2, 3)
28. scala> ' ' +: license zip license indexWhere {case (last, c) => "" + last + c == "an"}       
29. res14: Int = 343
31. scala> license indexOfSlice ("and")
32. res17: Int = 342
34. scala> ('a' to 'z') ++ ('A' to 'Z') 
35. res25: scala.collection.IndexedSeqView[Char,IndexedSeq[_]] = IndexedSeqViewA(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z)
37. scala> license intersect res25
38. res26: String = SubjectofAgrmnPdasihlywpkVBxvGCHTWLMOXqY
40. scala> license diff res25     
41. res27: String =   eeet. ?rouct?,  referred to n tis Agreement, shal be the binar softare acage ?Sun irtualo,? which Product allows for creating multiple irtual computers, each with different operating systems (?uest omputers?), on a physical computer with a specific operating system (?ost Computer?), to allow for installing and executing these Guest Computers simultaneously. he Product consists of executable files in machine code for the Solaris, indows, inux, and ac?S? operating systems as well as other data files as reuired by the executable files at run-time and documentation in electronic form. The Product includes all documentation and updates provided to ou by Sun under this Agreement and the terms of this Agreement will apply to all such documentation and updates unless a different license is provided with an update or documentation.
43. scala> license filter res25
44. < console>:7: error: type mismatch;
45.  found   : scala.collection.IndexedSeqView[Char,IndexedSeq[_]]
46.  required: (Char) => Boolean
47.        license filter res25
48.                       ^
50. scala> license filter {res25 contains _}
51. res29: String = SubjectofAgreementProductasreferredtointhisAgreementshallbethebinarysoftwarepackageSunVirtualBoxwhichProductallowsforcreatingmultiplevirtualcomputerseachwithdifferentoperatingsystemsGuestComputersonaphysicalcomputerwithaspecificoperatingsystemHostComputertoallowforinstallingandexecutingtheseGuestComputerssimultaneouslyTheProductconsistsofexecutablefilesinmachinecodefortheSolarisWindowsLinuxandMacOSXoperatingsystemsaswellasotherdatafilesasrequiredbytheexecutablefilesatruntimeanddocumentationinelectronicformTheProductincludesalldocumentationandupdatesprovidedtoYoubySununderthisAgreementandthetermsofthisAgreementwillapplytoallsuchdocumentationandupdatesunlessadifferentlicenseisprovidedwithanupdateordocumentation
53. scala> license filterNot {res25 contains _}
54. res30: String =   . ??,      ,       ? ,?        ,      (? ?),          (? ?),          .            , , ,  ??                -     .                                        .
56. scala> license removeDuplicates
57. res31: String = Subject ofAgrmn.?Pd,asihlywpkVBxv(GC)HTWLMOXq-Y
59. scala> license segmentLength ({_ > 'A'},2) 
60. res37: Int = 5
62. scala> license drop 2 span {_ > 'A'} _1
63. res41: String = bject
65. scala> license sortWith Ordering.Char          
66. res45: String =                                                                                                                                   (()),,,,,,,,,-....??????????AAAABCCCGGHLMOPPPPSSSSSTTVWXYaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbccccccccccccccccccccccccccccccddddddddddddddddddddddddddddddeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeefffffffffffffffffggggggggggghhhhhhhhhhhhhhhhhhhhhiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiijkllllllllllllllllllllllllllllllllllmmmmmmmmmmmmmmmmmmmmmmnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnoooooooooooooooooooooooooooooooooooooooooooooooopppppppppppppppppppqrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrsssssssssssssssssssssssssssssssssssssssssssssssttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuvvvwwwwwwwwwwxxxxxyyyyyyyyy
68. scala> 'a' to 'z' union ('A' to 'Z')
70. scala> "hello world" patch (6, "goof", 5)
71. res51: String = hello goof
73. scala> "hello world" updated(0,'H')
74. res54: String = Hello world

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))

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

Scala 2.8 Collections Overview

This topic introduces the basics of the collections API introduced in Scala 2.8. It is NOT intended to teach everything one needs to know about the collections API. It is intended only to provide context for future discussions about the new features of 2.8 collections. For example I am planning on how to introduce custom collection builders.

Disclaimer: I am not an expert on the changes to 2.8. But I think it is important to have a basic awareness of the changes. So I am going to try to provide a simplified explanation. Corrections are most certainly welcome. I will incorporate them into the post as soon as I get them.

If you want more information you can view the improvement document: Collections SID.

Pre Scala 2.8 there were several criticisms about the inconsistencies on the collections API.

Here is a Scala 2.7 example:

1. scala> "Hello" filter ('a' to 'z' contains _)
2. res0: Seq[Char] = ArrayBuffer(e, l, l, o)
4. scala> res0.mkString("")
5. res1: String = ello

Notice how after the map function the return value is a ArrayBuffer, not a String. The mkString function is required to convert the collection back to a String.
Here is the code in Scala28:

1. scala> "Hello" filter ('a' to 'z' contains _)         
2. res2: String = ello

In Scala28 it recognizes that the original collection is a String and therefore a String should be returned. This sort of issue was endemic in Scala 2.7 and several classes had hacks to work around the issue. For example List overrode the implementations for many of its methods so a List would be returned. But other classes, like Map, did not. So depending on what class you were using you would have to convert back to the original collection type. Maps are another good example:

1. scala> Map(1 -> "one",                                         
2.      |     2 -> "two") map {case (key, value) => (key+1,value)}
3. res3: Iterable[(Int, java.lang.String)] = ArrayBuffer((2,one), (3,two))

But if you use filter in map then you got a Map back.

I don't want to go into detail how this works, but basically each collection is associated with a Builder which is used to construct new instances of the collection. So the superclasses can perform the logic and simply delegate the construction of the classes to the Builder. This has the effect of both reducing the amount of code duplication in the Scala code base (not so important to the API) but most importantly making the return values of the various methods consistent.

It does make the API slightly more complex.

So where in pre Scala 2.8 there was a hierarchy (simplified):

                    Iterable[A]
                       |
                   Collection[A]
                       |
                     Seq[A]

In 2.8 we now have:

               TraversableLike[A,Repr]   
               /               \
     IterableLike[A,Repr]    Traversable[A]
       /               \      / 
  SeqLike[A,Repr]   Iterable[A]
            \        /
              Seq[A]

The *Like classes have most of the implementation code and are used to compose the public facing API: Seq, List, Array, Iterable, etc... From what I understand these traits are publicly available to assist in creating new collection implementations (and so the Scaladocs reflect the actual structure of the code.)

Groupby - collection processing

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 Iterable's groupBy method in this topic.

This is a Scala 2.8 and later method. It is similar to partition in that it allows the collection to be divided (or partitioned). Partition takes a method with returns a boolean and partitions the collection into two depending on a result. GroupBy takes a function that returns an object and returns a Map with the key being the return value. This allows an arbitrary number of partitions to be made from the collection.

Here is the method signature:

1. def groupBy[K](f : (A) => K) : Map[K, This]

A bit of context is require to understand the three Type parameters A, K and This. This method is defined in a super class of collections called TraversableLike (I will briefly discuss this in the next topic.) TraversableLike takes two type parameters: the type of the collection and the type contained in the collection. Therefore in this method definition, 'This' refers to the collection type (List for example) and A refers to contained type (perhaps Int). Finally K refers to the type returned by the function and are the keys of the groups formed by the method.

Examples:

1. scala> val groups = (1 to 20).toList groupBy {
2.      | case i if(i<5) => "g1"
3.      | case i if(i<10) => "g2"
4.      | case i if(i<15) => "g3"
5.      | case _ => "g4"
6.      | }
7. res4: scala.collection.Map[java.lang.String,List[Int]] = Map(g1 -> List(1, 2, 3, 4), g2 -> List(5, 6, 7, 8, 9), g3 -> List(10, 11, 12, 13, 14), g4 -> List(15, 16, 17, 18, 19, 20))
9. scala> groups.keySet
10. res6: scala.collection.Set[java.lang.String] = Set(g1, g2, g3, g4)
12. scala> groups("g1")
13. res7: List[Int] = List(1, 2, 3, 4)
15. scala> val mods = (1 to 20).toList groupBy ( _ % 4 )
16. mods: scala.collection.Map[Int,List[Int]] = Map(1 -> List(1, 5, 9, 13, 17), 2 -> List(2, 6, 10, 14, 18), 3 -> List(3, 7,
17.  11, 15, 19), 0 -> List(4, 8, 12, 16, 20))
19. scala> mods.keySet
20. res9: scala.collection.Set[Int] = Set(1, 2, 3, 0)
22. scala> mods(1)
23. res11: List[Int] = List(1, 5, 9, 13, 17)