CODEWITHSUNDEEP
scalatail-recursion
Kigyo
Kigyo

Reputation: 5768

More efficient Solution with tailrecursion?

I have the following ADT for Formulas. (shortened to the important ones)

sealed trait Formula
case class Variable(id: String) extends Formula
case class Negation(f: Formula) extends Formula
abstract class BinaryConnective(val f0: Formula, val f1: Formula) extends Formula

Note that the following methods are defined in an implicit class for formulas.

Let's say i want to get all variables from a formula.

My first approach was:

Solution 1

def variables: Set[Variable] = formula match {
  case v: Variable => HashSet(v)
  case Negation(f) => f.variables
  case BinaryConnective(f0, f1) => f0.variables ++ f1.variables
  case _ => HashSet.empty
}

This approach is very simple to understand, but not tailrecursive. So I wanted to try something different. I implemented a foreach on my tree-like formulas.

Solution 2

def foreach(func: Formula => Unit) = {
  @tailrec
  def foreach(list: List[Formula]): Unit = list match {
    case Nil =>
    case _ => foreach(list.foldLeft(List.empty[Formula])((next, formula) => {
      func(formula)
      formula match {
        case Negation(f) => f :: next
        case BinaryConnective(f0, f1) => f0 :: f1 :: next
        case _ => next
      }
    }))
  }
  foreach(List(formula))
}

Now I can implement many methods with the help of the foreach.

def variables2 = {
    val builder = Set.newBuilder[Variable]
    formula.foreach { 
        case v: Variable => builder += v
        case _ => 
    }
    builder.result
}

Now finally to the question. Which solution is preferable in terms of efficieny? At least I find my simple first solution more aesthetic.

Upvotes: 0

Views: 67

Answers (1)

wingedsubmariner
wingedsubmariner

Reputation: 13667

I would expect Solution 2 to be more efficient, because you aren't create many different HashSet instances and combining them together. It is also more general.

You can simplify your Solution 2, removing the foldLeft:

def foreach(func: Formula => Unit) = {
  @tailrec
  def foreach(list: List[Formula]): Unit = list match {
    case Nil =>
    case formula :: next => {
      func(formula)
      foreach {
        formula match {
          case Negation(f) => f :: next
          case BinaryConnective(f0, f1) => f0 :: f1 :: next
          case _ => next
        }
      }
    }
  }
  foreach(List(formula))
}

Upvotes: 1

Related Questions