1. Introduction
In this tutorial, we’ll explore four different approaches to solve the same problem – how to reverse the elements of a sequence.
2. Solution
We’ll see four ways to solve the problem to understand how different criteria can lead to different solutions.
2.1. Using the Trait’s reverse Method
Our first approach is to rely on the excellent Scala collections library.
The Scala documentation for collections contains a method that does what we need in the trait Seq, with the following signature:
def reverse: Seq[A]
As long as the collection we want to reverse (List, for example) inherits, directly or indirectly, from that trait, we can invoke the method to obtain the reversed collection:
// say we have a list of integers:
val integers = 2 :: 4 :: 6 :: 7 :: 8 :: Nil
// and we want to reverse it:
val reversed = integers.reverse
2.2. Using Simple Recursion
Although the collections library offers a fast and easy way to solve the problem, we want to implement the method and leverage the opportunity to learn some idiomatic code. Our second approach uses a simple recursive method:
def naiveRecursiveReverse[T](xs: Seq[T]): Seq[T] =
if (xs.isEmpty) xs
else naiveRecursiveReverse(xs.drop(1)) :+ xs.head
Let’s observe a few things:
- The method accepts a very abstract, generic Seq instead of a more specific collection type, like a List, an Array, or a Vector. We should aim at writing generic code as much as possible instead of repeating ourselves. Seq is the most basic trait that conveys the notion of positional order in its elements.
- The trait Seq takes one type parameter (the type of its elements), so we must provide it. But we don’t know it in advance! So we pass a very general type T. That’s called a universal type.
- Every time this method calls itself, it has to store a copy of its state in the stack. Therefore, for large collections, it might provoke a stack overflow error.
2.3. Using Tail Recursion
The previous attempt is straightforward to understand but could be more efficient and potentially safe. To avoid overflowing the stack, we can use the technique known as tail recursion.
def tailRecursiveReverse[T](xs: Seq[T]): Seq[T] = {
@tailrec
def aux(acc: Seq[T], sequence: Seq[T]): Seq[T] =
if (sequence.isEmpty) acc
else aux(sequence.head +: acc, sequence.tail)
aux(Seq.empty[T], xs)
}
This time, we declare an inner auxiliary method, aux, where we’ll apply our tail recursion. As we can see, it receives an additional parameter we use as an accumulator. This pattern is typical of tail recursive functions. Because of that, we can be sure that the method is the very last thing that is called (hence the name: tail recursion).
Another interesting detail of this snippet is the use of the annotation @tailrec. It makes no difference in the compiled code but forces the compiler to ensure this method is tail-recursive. If that’s not the case, the code won’t compile.
We want to provide a tail-recursive method because the compiler can transform methods of such type into iterations. As a result, the stack doesn’t need to grow with each invocation. Now we know that reversing big collections doesn’t provoke memory exhaustion issues.
2.4. Using Fold
The pattern used in our previous attempt is very common. So common, indeed, that it receives its own name: folding. Also, there are methods in the standard collections to do it. But what is folding?
In simple terms, we can imagine that we have a very long sheet of paper, and we want to fold it in a certain way, starting at one of the extremes, and keep doing that until the whole sheet comprises all the original elements of the sheet, applying the folding operation.
In our case, we want to take our sequence and fold it: for each element, we want to prepend it to another sequence (initially empty). The resulting code is simple:
def foldBasedReverse[T](xs: Seq[T]): Seq[T] =
xs.foldLeft(Seq.empty[T])((sequence, element) => element +: sequence)
This has all the advantages of the tail-recursive method but is simpler to write. All we have to do is define the initial state of the folded result (an empty sequence for us) and a function that transforms an intermediate result and an element from the original collection into a new intermediate result.
3. Testing
We can test the functionality of our methods using the powerful ScalaTest framework. Let’s start with two generic approaches that test reversing small and big collections, respectively:
import ListReverser._
def testReverseSmallList(f: Seq[_] => Seq[_]): Assertion = {
val list = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
val expectedReversedList = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
val actualReversedList = f(list)
assertResult(expectedReversedList)(actualReversedList)
}
def testReverseBigList(f: Seq[_] => Seq[_]): Assertion = {
val n = 100_000
val vector: Vector[String] =
(0 to n).foldLeft(Vector.empty[String])((v, _) =>
v.appended(Random.nextString(1000))
)
val expectedFirstElement: String = vector.last
val actualFirstElement: String =
f(vector).head.asInstanceOf[String]
assertResult(expectedFirstElement)(actualFirstElement)
}
We want to use the same methods to test the three implementations that we wrote. For that reason, we pass to them the function that reverses, called f.
With the above in place, the actual tests become trivial:
"The naive list reverser" should {
val reversingFunction: Seq[_] => Seq[_] = naiveRecursiveReverse
"reverse small lists" in {
testReverseSmallList(reversingFunction)
}
"exhaust memory with big lists" in {
assertThrows[StackOverflowError](testReverseBigList(reversingFunction))
}
}
"The tail-recursive list reverser" should {
val reversingFunction: Seq[_] => Seq[_] = tailRecursiveReverse
"reverse small lists" in {
testReverseSmallList(reversingFunction)
}
"handle big lists" in {
testReverseBigList(reversingFunction)
}
}
"The folding list reverser" should {
val reversingFunction: Seq[_] => Seq[_] = foldBasedReverse
"reverse small lists" in {
testReverseSmallList(reversingFunction)
}
"handle big lists" in {
testReverseBigList(reversingFunction)
}
}
4. Conclusion
In this article, we’ve learned several ways to reverse the elements of a sequence. As is often the case, in general, we should prefer using the collections library because the code is very performant and thoroughly tested.
Nonetheless, by providing our own implementation, we can learn or refresh interesting, idiomatic, and efficient patterns in our coding. Also, variations can be created easily; for example, to fold a collection starting from the right end instead of the left one.
As usual, the full code for this article is available over on GitHub.