I find myself reversing accumulators at the end of most functions; how can I stop?

Question

I've been working through a book on Functional Programming in Scala (with that very title.) Running through the exercises, I've found myself frequently reversing my final result when it is gathered with an accumulator. I recall having similar patterns during my Racket days. My concern is that I might be making my code slightly messier than necessary and perhaps performing an extra O(n) operation (where n is the length of the accumulator/result.)

Example:

// Produces a List from a Stream, forcing evaluation of all elements.
def toList(): List[A] = {
    def go(l: Stream[A], acc: List[A]): List[A] = {
        l match {
            case Empty if acc.nonEmpty => acc.reverse
            case Empty if acc.isEmpty => Nil
            case Cons(h, t) => go(t(), h() :: acc)
        }
    }
    // "this" is a Stream[A].
    go(this, Nil)
}

This pattern of reversing the result to restore the original order is my concern. Is there a better way (no reverse call) to do this in FP in general and in Scala in particular?

Answer 1

You could try using a data structure such as Vector that will append a value at effectively constant time.

So where you have:

case Cons(h, t) => go(t(), h() :: acc)

use instead:

case Cons(h,t) => go(t(), acc :+ h())

Then there needn't be a reverse when you return the accumulator.

Answer 2

Well, there are various approaches, even without turning to non-tailrecursion, which you should not do over the size of a possibly large container.

First you should ask: why do you care? If your code is fast enough, why would you want to avoid the reversal?

Then the simplest solution probably is: use mutable builders locally. There is a ListBuffer for exactly the purpose of building a list by append elements step by step. The implementations in the Scala API use this a lot for performance reasons.

If you do not want to directly use a list buffer you can do a lazy computation and convert it to a list. This might in some cases be more readable than using an accumulator, but it probably wont be more efficient.

def map[A,B](list: List[A], f: A => B): Stream[B] = list match {
  case x :: xs  => Stream(f(x)) #:: map(xs, f)
  case Nil => Stream() 
}
map(list, (x: Int) => x + 1).toList