How to write a nice Low-Pass-Filter in Scala

Question

I needed a Low-Pass-Filter in one of my Scala projects and came up with this:

def filter(numbers: Seq[Double], filterSize: Int): Seq[Double] = {
  assert(filterSize > 0)
  val ringBuffer = new Array[Double](filterSize)
  var ringBufferIndex = 0

  numbers.map(x => {
    // update ring buffer
    ringBuffer(ringBufferIndex) = x

    // increase ring index
    ringBufferIndex += 1 
    if (ringBufferIndex == filterSize) {
      ringBufferIndex = 0
    }

    // get avarage
    ringBuffer.foldLeft(0.0)(_ + _) / filterSize
  })
}

However, there are some things I don't like about it:

• It uses map (nicely functional) but needs a mutable variable (ringBufferIndex - BAD).

• It work's on Seq[Double] (which is fine), but returns Seq[Double], which is bad cause it requires the caller to call .toList or whatever he actually uses. I tried using Generics here like this:

  def filter\[T <% Seq[Double]](numbers: T, filterSize: Int): T

but that would not compile.

Does anyone have suggestionts how to improve those two issues?

Answer 1

If index lookups are a problem (O(n) with List), you could use a persistent vector. This gives you O(1) indexing as well as O(1) update. It's also purely functional (immutable), so life is still happy in that regard.

With a little bit of imagination, we can convert your code directly into a pure-functional version using Vector:

def filter(numbers: List[Double], size: Int) = {
  def walk(numbers: List[Double], buffer: Vector[Double], i: Int): List[Double] = {
    numbers match {
      case x :: tail => {
        val nextBuffer = buffer(i) = x
        val nextI = if (i == size) 0 else i + 1

        val avg = buffer.foldLeft(0.0) { _ + _ } / size
        avg :: walk(tail, nextBuffer, nextI)
      }

      case Nil => Nil
    }
  }

  walk(numbers, Vector.empty, 0)
}

Note that this isn't tail-recursive, so it'll break down when numbers is too large. It's pretty easy to fix this problem, but I'm being lazy right now.