Daily scala

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)
3. /*
4. I like to use functions constructed with case statements
5. in order to clearly label the index.  The alternative is 
6. to use x._2 for the index and x._1 for the value
7. */
8. scala> list.view.zipWithIndex foreach {case (value,index) => println(value,index)}
9. (a,0)
10. (b,1)
11. (c,2)
12. (d,3)
13. // alternative syntax without case statement
14. scala> list.view.zipWithIndex foreach {e => println(e._1,e._2)}
15. (a,0)
16. (b,1)
17. (c,2)
18. (d,3)
19. /*
20. Fold left and right functions have 2 parameters (accumulator, nextValue) 
21. using a case statement allows you to expand that but watch the brackets!
22. */
23. scala> (list.view.zipWithIndex foldLeft 0) {case (acc,(value,index)) => acc + value.toInt + index} 
24. res14: Int = 400
25. // alternative syntax without case statement
26. scala> (list.view.zipWithIndex foldLeft 0) {(acc,e) => acc + e._1.toInt + e._2} 
27. res23: Int = 400
28. /*
29. alternative foldLeft operator.  The thing I like about this
30. syntax is that it has the initial accumulator value on the left 
31. in the same position as the accumulator parameter in the function.
33. The other thing I like about it is that visually you can see that it starts with
34. "" and the folds left
35. */
36. scala> ("" /: list.view.zipWithIndex) {                          
37.      | case (acc, (value, index)) if index % 2 == 0 => acc + value
38.      | case (acc, _) => acc                                       
39.      | }
40. res15: java.lang.String = ac
41. /*
42. This example filters based on the index then uses map to remove the index
43. force simply forces the view to be processed.  (I love these collections!)
44. */
45. scala> list.view.zipWithIndex.filter { _._2 % 2 == 0 }.map { _._1}.force
46. res29: Seq[Char] = List(a, c)

Todays topic does not introduce anything new, it just a useful example of using a function to create a list of objects. This is NOT part of the standard library.

The methods are called unfoldRight and unfoldLeft because they are more or less the inverse of foldLeft and foldRight. foldLeft and Right run a function on each element in a list producing some result. unfoldLeft and right produce a list from a function and a seed value. The List is created from executing the function repeatedly with the result from the previous execution (or the seed value). Each function call returns a result which is the element in the list. The list is done when the function returns None rather than Some(x).

This sample is directly derived from the samples: http://paste.pocoo.org/show/140865/

Remember the performance differences between the two. Adding an element to the head of scala list is a constant operation but adding an element to the end(tail) of the list is linear time based on the size of the list. So unfoldLeft will typically suffer from worse performance.

1. scala> def unfoldRight[A, B](seed: B)(f: B => Option[(A, B)]): List[A] = f(seed) match {
2.      |   case Some((a, b)) => a :: unfoldRight(b)(f)
3.      |   case None => Nil
4.      | }
5. unfoldRight: [A,B](B)((B) => Option[(A, B)])List[A]
6. scala> unfoldRight(10) { x => if (x == 0) None else Some((x, x - 1)) }
7. res0: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
8. scala> unfoldRight("Jesse") { x => if (x.length == 0) None else Some((x, x.drop(1).toString)) }
9. res2: List[java.lang.String] = List(Jesse, esse, sse, se, e)
10. scala> def unfoldLeft[A, B](seed: B)(f: B => Option[(B, A)]) = {
11.      |   def loop(seed: B)(ls: List[A]): List[A] = f(seed) match {
12.      |     case Some((b, a)) => loop(b)(a :: ls)
13.      |     case None => ls
14.      |   }
15.      |
16.      |   loop(seed)(Nil)
17.      | }
18. unfoldLeft: [A,B](B)((B) => Option[(B, A)])List[A]
19. scala> unfoldLeft(1) { x => if (x == 11) None else Some((x + 1, x)) }
20. res0: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
21. // Notice that the result is ordered in the opposite way from unfoldRight
22. // Also notice the order of the list is reversed since the algorithm is the same but
23. // unfoldLeft adds to end of list.
24. scala> unfoldLeft("Jesse")  { x => if (x.length == 0) None else Some((x.drop(1).toString,x)) }
25. res1: List[java.lang.String] = List(e, se, sse, esse, Jesse)

Folding and reducing are two types of operations that are both very important with dealing with collections in Scala (and other functional languages). This topic covers the fold operations. The reduce topic was previously covered.

A simplistic explanation is they allow processing of the collections. I think about foldRight and foldLeft to be very similar to a visitor that visits each element and performs a calculation. It does not change the values of the collection instead it calculates a result from visiting each element. In Java you might see the following pattern:

1. class Collection {
2.   pubic Result op( Result startingValue, Op operation){...}
3. }
4. interface Op{
5.   public Result op( Object nextCollectionElem, Result lastCalculatedResult)
6. }

To a Java programmer this is pretty obvious how you use it. This is essentially the fold operation. The difference is we are using closures so there is almost no boilerplate and all collection/Iteratore/Iterable interfaces have the fold methods.

One last point before examples. For fold and reduce operations there are both foldLeft and foldRight and similarly reduceLeft and reduceRight. These indicate the order that a collection is processed. Note that for certain collections one direction is more performant that the other. Lists, for example, are better to process left to right because of the datastructure used.

Some tasks that are suited to fold are:

• Find the 5 smallest elements in a list
• Sum all the values of a Map together
• Sum the lengths of the Strings contained in the collection

There are a number of ways that fold can be written syntactically. The following examples are ways to sum together the integers of a Map. Note that /: is an alias for foldLeft and :/ is an alias for foldRight. Normally foldLeft and foldRight should be used unless the rest of the developers who will be reading the code are quite confortable reading Scala.

1. // fold right processes from left to right
2. scala> val m = Map(1 -> "one", 2 -> "two", 3 -> "three")
3. m: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> one, 2 -> two, 3 -> three)
4. scala> m.foldRight(0)((kv: (Int, String), a : Int) => a+kv._2.length)
5. res1: Int = 11
6. scala> (m :\ 0)((kv: (Int, String), a : Int) => a+kv._2.length)
7. res5: Int = 11
8. scala> m.foldRight(0){ case ((key, value), a) => a+value.length}
9. res7: Int = 11
10. scala> m.foldRight(0){ case (kv, a) => a+kv._2.length} }}
11. res8: Int = 11
12. // fold left processes from right to left (usually slower than foldRight)
13. scala> val m = Map("a" -> 1, "b" -> 2, "c" -> 3)
14. m: scala.collection.immutable.Map[java.lang.String,Int] = Map(a -> 1, b -> 2, c -> 3)
15. scala> m.foldLeft(0)( (accum, kv) => accum + kv._2 )
16. res9: Int = 6
17. scala> m.foldLeft(0){case (accum, (key, value)) => accum + value}
18. res5: Int = 6
19. scala> (0 /: m){case (accum, (key, value)) => accum + value}
20. res4: Int = 6