Tail recursion with multiple accumulator stages

Question

I'm trying to determine the best pattern for tail recursion with multiple accumulator stages, judging best by being a balance of efficiency and readability.

The particular scenario is a stream of frames arriving ordered by track and then time. I need to accumulate track information and then accumulate those tracks:

case class Frame(trackId: Int, time: Double)
case class Track(id: Int, count: Int, start: Double, end: Double)

The pattern I find more readable uses the actual Track case class as the track accumulator:

def scanTracks(reader: Stream[Frame]): List[Track] = {  
  def scanTracks2(reader2: Stream[Frame], track: Option[Track], acc: List[Track]): List[Track] =
    if (reader2.isEmpty)
      track.map(_ :: acc).getOrElse(acc)
    else {
      val frame = reader2.head
      track match {
        case None => scanTracks2(reader2.tail, Some(Track(frame.trackId,1,frame.time,0)), acc)
        case Some(t) => if(frame.trackId == t.id)
          scanTracks2(
            reader2.tail,
            Some(t.copy(count = t.count+1,end=frame.time)),
            acc
          )
          else
          scanTracks2(
            reader2.tail,
            Some(Track(frame.trackId,1,frame.time,frame.time)),
            t :: acc
          )
      }
    }
  scanTracks2(reader, None, Nil)
}

My concern with this pattern is that each recursion does a copy of the current track to produce the new track accumulator. While head::tail is very efficient, since it's just a cons of an existing list, creating a new copy of Track seems less efficient.

The alternative is to explicitly pass all values that will make up a track, so that recursion just changes function parameters:

def scanTracks(reader: Stream[Frame]): List[Track] = {  
  def scanTracks2(reader2: Stream[Frame], id: Int, count: Int, start: Double, end: Double, acc: List[Track]): List[Track] =
    if (reader2.isEmpty)
      Track(id, count + 1, start, end) :: acc
    else {
      val frame = reader2.head
      frame.trackId match {
        case -1 => scanTracks2(reader2.tail, frame.trackId, 1, frame.time, 0, acc)
        case x if x == id => scanTracks2(reader2.tail, id, count + 1, start, frame.time, acc)
        case _ =>
          scanTracks2(
            reader2.tail,
            frame.trackId,
            1,
            frame.time,
            0,
            Track(id, count + 1, start, end) :: acc
          )
      }
    }
  scanTracks2(reader, -1, 0, 0, 0, Nil)
}

This muddies the function signature and has the kludge of using -1 as a marker of no track yet. Overall, I feel that readability has degraded a good bit.

My question is whether my concern about copy efficiency is unreasonable in the overall scheme or whether there is yet another pattern for doing this multi-stage accumulation that is better than both of these.

Arne Claassen Arne Claassen · Accepted Answer · 2015-05-13T19:25:46

The best solution I've found so far is to have inlined tail-recursive functions for additional accumulator stages. Given my example above, I've rewritten as follows:

def scanTracks(reader: Stream[Frame]): List[Track] = {

  def scanTracks(scanReader: Stream[Frame], acc: List[Track]): List[Track] =
    if (scanReader.isEmpty)
      acc
    else {
      val frame = scanReader.head

      def scanTrack(trackReader: Stream[Frame], count: Int, end: Double): (Stream[Frame], Track) =
        if (trackReader.isEmpty)
          (trackReader, Track(frame.trackId, count, frame.time, end))
        else {
          val frame2 = trackReader.head
          if (frame2.trackId == frame.trackId)
            scanTrack(trackReader.tail, count + 1, frame2.time)
          else
            (trackReader.tail, Track(frame.trackId, count, frame.time, end))
        }

      val (scanReader2, track) = scanTrack(scanReader.tail, 1, frame.time)
      scanTracks(scanReader2, track :: acc)
    }

  scanTracks(reader, Nil)
}

The benefit is that the outer scanTracks has drastically reduced state being passed in its signature, while inner scanTrack doesn't have to pick up all the state that used to be in the outer, since anything that isn't changed during the inner recursion is accessible in scope. Since the inner scanTrack always completes its recursion before another scanTracks recursion is required, scanTracks remains tail-recursive only ever calling itself as an exit condition.

Tail recursion with multiple accumulator stages

1 Answers