More efficient Solution with tailrecursion?

Question

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.

Although there is answer, I would expect somebody to roll out actual benchmark (though, I'm not an op) — om-nom-nom
– om-nom-nom, Commented May 30, 2014 at 23:33

wingedsubmariner · Accepted Answer · 2014-05-31 00:11:59Z

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)) }

Thank you. I think you meant it to be case formula :: next. Way nicer than my fold!

Collectives™ on Stack Overflow

More efficient Solution with tailrecursion?

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related