Posted on by & filed under Content - Highlights and Reviews, Programming & Development.

A guest post by John Sullivan, a 15-year Java veteran who has been programming in Scala for 2+ years. He enjoys posting in-depth articles on his popular Scala-oriented blog scabl.blogpost.com, and he is currently employed as a Principal Sofware Engineer at the Broad Institute.

As we program our way through life, we are commonly faced with the task of taking some sequential input, applying some transformation to each element, and producing a new sequence as output. Let’s quickly review how we might accomplish this in Java, and then consider some approaches for performing the same task in Scala.

Building a Java Sequence

We commonly use the java.util.ArrayList class in Java because of its performance characteristics. Get and set operations run in constant time, and the append operation runs in amortized constant time. So any given append operation may take longer than O(1), but n append operations will take O(n) time, for sufficiently large values of n. We prefer this over Java arrays, because the size of the ArrayList is not fixed.

In our simple example, we will transform an input sequence by squaring each of its values. Let’s see how this works when the input sequence is a simple range of integers:

Direct Translation into Scala

There are many approaches we can take for performing this task in Scala. Let’s start by doing a direct translation of the buildListFromRange() method presented above. The Scala equivalent to java.util.ArrayList is scala.collection.mutable.ArrayBuffer. It has the same performance characteristics. We use immutable collections in Scala by default, so this mutable collection has to be imported. Standard practice is to import in such a way that when we actually use the type we say mutable.ArrayBuffer, to make it clear to the reader that we are using a mutable collection.

Immutable objects are strongly preferred when programming in a functional style. They are easier to reason about, because we don’t have to worry about them changing underneath us. But it’s important to emphasize that it’s perfectly okay to use mutable objects in Scala, because Scala doesn’t try to penalize you for “doing things wrong.” Instead, it tries to encourage you to use a functional approach whenever possible. You are welcome to program in a very Java-like style, and to pick up more functional techniques when it is comfortable and convenient to do so.

Getting Rid of the Mutable Collection

The immutable counterpart to ArrayBuffer is Vector. Random access and append operations occur in effective constant time – actually in log time with a very large base for the logarithm. If you are willing to accept some upper bound – say 100G – on the size of your sequences, then the operations are O(1).

The transformation from the previous example is straightforward. Appending to the Vector with :+ creates a new Vector with one more element. Each time we append, we store the latest result in a local var.

On the surface of it, we are just replacing one non-functional technique (the mutable object) with another: a local var. They both suffer from the same problem: They make things harder to reason about, because the value can vary over time. But let’s consider this as a stepping stone. Our code is evolving into a fully functional version. Also, let’s remember that even if not ideal, it’s fine to use vars in Scala!

Removing the Local Variable with Recursion

A common functional technique for removing mutable state, such as local variables, is to use recursion. Our recursive method squares the first element of the range, and appends it to the accumulated result. It passes the rest of the elements of the range, and the new accumulated result, to a recursive call. When the range is exhausted, we return the accumulated result.

Note how we annotate our recursive method with @tailrec. This will cause the Scala compiler to produce an error if it is unable to apply tail recursion elimination to the method. Tail recursion elimination rewrites the recursive method as a loop, preventing you from overflowing the stack on large inputs. Because it can sometimes be tricky to reason about when tail recursion can occur, we use the annotation to assure ourselves that it does.

Removing the Local Variable with foldLeft

Another approach to removing the mutable state is with a fold operation on the input collection. foldLeft on a Seq takes two arguments: the initial accumulator, and a function that takes the current accumulator and the next element of the sequence, returning an updated accumulator. We simply iterate over the input sequence, processing each element in turn, producing a new accumulator for each element. Here’s how it looks:

The symbolic operator /: is a synonym with foldLeft. Because symbolic operators ending in a colon are right-associative, we put the initial accumulator first, which some people find a little easier to read:

Building a Scala Sequence Using map

Scala collections are very powerful, and they are often times much more convenient to manipulate than their Java equivalents. One clear example are the monadic methods on Scala collections such as map. We’ll save the details for another time, but the following example is equivalent to those above:

Wrapping Up

Scala is designed to allow people to write code in an imperative, non-functional style. At the same time, it encourages people to write in a functional style when possible. The key take-home message is, don’t be scared to write ugly, Java-like code in Scala! Challenge yourself to learn functional techniques such as those demonstrated here, but take your time and don’t rush. You’ll find that your coding techniques will improve quickly if you are patient.

Safari Books Online has the content you need

Check out these Scala books available from Safari Books Online:

Scala in Action is a comprehensive tutorial that introduces Scala through clear explanations and numerous hands-on examples. Because Scala is a rich and deep language, it can be daunting to absorb all the new concepts at once. This book takes a “how-to” approach, explaining language concepts as you explore familiar programming challenges that you face in your day-to-day work.
This book takes a step-by-step tutorial approach to teaching you Scala. Starting with the fundamental elements of the language, Programming in Scala introduces functional programming from the practitioner’s perspective, and describes advanced language features that can make you a better, more productive developer.
Scala in Depth is a unique new book designed to help you integrate Scala effectively into your development process. By presenting the emerging best practices and designs from the Scala community, it guides you though dozens of powerful techniques example by example.

About the author

john_sullivan John Sullivan is a professional software engineer and technical blogger. A 15-year Java veteran, he has been happily programming in Scala for 2+ years. He enjoys posting in-depth articles on his popular Scala-oriented blog scabl.blogpost.com. His major interests outside of Scala include software engineering best practices, the agile development process, and Domain Driven Design. John has a Master of Science in Computer Science from UMass Boston. He is currently employed as a Principal Software Engineer at the Broad Institute.

Tags:

One Response to “Building a Scala Sequence in a Functional Style”

  1. Samuel Heaney

    Another clear way of doing it is using:

    def buildSeqFromRangeVersion6(): Seq[Int] =
    Vector.tabulate(100)(x => x * x)