Scala snippets 1: Folding

Coming from a Java background, Scala provides lots of nice features and libraries that allow you to create nice and concise code. Wrapping your head around these concepts though, can be hard. In this short series of articles I’ll walk through some of the concepts behind scala, and show you how you can use the various concepts. There is no strict structure to this series, I’ll just show concepts I found interesting.

The following snippets are available:

1. Scala snippets 1: Folding
2. Scala snippets 2: List symbol magic
3. Scala snippets 3: Lists together with Map, flatmap, zip and reduce
4. Scala snippets 4: Pimp my library pattern with type classes

Folding and unfolding

In this snippet, we’ll look at folding. According to wikipedia this is what folding does:

"In functional programming, fold – also known variously as reduce, accumulate, aggregate, compress, or inject – refers to a family of higher-order functions that analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its constituent parts, building up a return value."

• http://en.wikipedia.org/wiki/Fold_(higher-order_function)

So basically, you input some data, apply a method and return a different value. Lets first look at the signature of the fold operation:

def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1

First lets look at the documentation (http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List):

Folds the elements of this traversable or iterator using the specified associative binary operator. The order in which operations are performed on elements is unspecified and may be nondeterministic.

• A1: a type parameter for the binary operator, a supertype of A.
• z: a neutral element for the fold operation; may be added to the result an arbitrary number of times, and must not change the result (e.g., Nil for list concatenation, 0 for addition, or 1 for multiplication.)
• op: a binary operator that must be associative returns the result of applying fold operator op between all the elements and z

I always have difficulty reading these kind of descriptions to lets look at an example:

scala> val list = "Hello World this is a string".split(" ");
list: Array[String] = Array(Hello, World, this, is, a, string)

scala> list.fold(">>") {(z, i) => z + ":" + i }
res3: String = >>:Hello:World:this:is:a:string

Here we first create a List[String]. On this object we call the fold method. The first argument we provide is the starting value, and the second argument is the function we apply to each value of the list. In this case we just concatenate the values together. The output of this function is the used as input for the next one.

Lets look at a couple of other examples:

Here we sum all the values:

scala> val list = List.range(0, 20)
list: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)

scala> list.fold(0){(z, i) => z + i }
res10: Int = 190

Or product them:

scala> val list = List.range(1, 20)
list: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)

scala> list.fold(1){(z, i) => i * z}
res12: Int = 109641728

Easy right! There are a lot more advanced usages of fold you can use, but the basic premise is the same: http://oldfashionedsoftware.com/2009/07/30/lots-and-lots-of-foldleft-examples/