CODEWITHSUNDEEP
scalarecursionfunctional-programming
Maciej
Maciej

Reputation: 145

@tailrec error - "recursive call targeting a supertype"

I have a following problem. 

class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {

  @tailrec final def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet =
    if(p(elem))
      (this remove elem).filterAcc(p, acc incl elem)
    else
      (this remove elem).filterAcc(p, acc)

}

Scala tels me, that it can not optimize @tairec, because my method contains a recursive call targeting a supertype. (Superclass of NonEmpty is class TweetSet, where the method filterAcc is defined). How to deal with such an error?

Upvotes: 1

Views: 462

Answers (2)

Alexey Romanov
Alexey Romanov

Reputation: 170713

In this case it may make sense to move filterAcc into the companion object:

trait TweetSet {
  final def filterAcc(p: Tweet => Boolean) = TweetSet.filterAcc(p, this, Empty)
}

object TweetSet {
  @tailrec 
  private def filterAcc(p: Tweet => Boolean, self: TweetSet, acc: TweetSet) = self match {
    case ne: NonEmpty =>
      // the original body with `this` replaced by `self` and made an argument for recursive calls
      val elem = ne.elem
      if(p(elem))
        filterAcc(p, self remove elem, acc incl elem)
      else
        filterAcc(p, self remove elem, acc)
    // other cases
  }
}

Upvotes: 0

Sergey
Sergey

Reputation: 2900

This is intended behavior. The error occurs due to how @tailrec works: in essence, the compiler tries to transform a recursive call into a local loop. In spite of the fact that your method is recursive, it recurses by calling itself on another instance not even of the same type, but of the supertype - and since other children of TweetSet may provide a completely different implementation of filterAcc, the compiler cannot make sure this method can be safely expanded into a loop.

A rule of thumb for tail-recursive functions is to ensure that it always calls exactly itself as the last statement - in your case, instead of calling

(this remove elem).filterAcc(...)

you have to try and transform acc in the way that emulates this remove elem and call

filterAcc(p, <transformed acc>)

In functional programming involving recursion it is a good idea to define the entire method in the superclass (in your case TweetSet) and rely on pattern matching by ADT members instead of polymorphism - that way there will be no issues with optimizing recursion.

Upd: There's a nice blog post explaining tail recursion, as specified in an answer to this question

Upvotes: 4

Related Questions