CODEWITHSUNDEEP
scalatail-recursion
bcb
bcb

Reputation: 13

Making recursive code, tail recursive in Scala

I'd like to change the code to be tail recursive not to overflow the stack expression is an ADT of Label or Tree

  def combine[A](expression: Expression, runners: List[Runner[A]]): Runner[A] = {
    val labelToHashmap = runners.map(runner=> (runner.label.get, runner)).toMap
    def reduceExpression(e: Expression): Runner[A] = {
      e match {
        case Label(_, value) => labelToHashmap(value)
        case Tree(_, operation, left, right) =>
          operation match {
            case AND =>  reduceExpression(left).and(reduceExpression(right))
            case OR => reduceExpression(left).or(reduceExpression(right))
          }
      }
    }
    reduceExpression(expression)
  }

How can I turn the above code to a tail recursive one?

Upvotes: 1

Views: 152

Answers (2)

Matthias Berndt
Matthias Berndt

Reputation: 4577

You can rewrite the function in a tail-recursive way like Kolmar has shown, and it'll work. But I think this usually obscures the intent of the algorithm, because now you have to fiddle around with an explicit stack that is normally implicit.

I would say it's better to factor out the stack fiddling bits into a re-usable data structure and use that. The cats.Eval type is such a data structure.

import cats.Eval
import cats.syntax.all._

  def combine[A](
    expression: Expression,
    runners: List[Runner[A]]
  ): Runner[A] = {
    val labelToHashmap = runners.fproductLeft(_.label.get).toMap
    def reduceExpression(e: Expression): Eval[Runner[A]] =
      Eval.now(e).flatMap {
        case Label(_, value) => labelToHashmap(value)
        case Tree(_, operation, left, right) =>
          operation match {
            case AND =>
              (
                reduceExpression(left),
                reduceExpression(right)
              ).mapN(_ and _)
            case OR =>
              (
                reduceExpression(left),
                reduceExpression(right)
              ).mapN(_ or _)
          }
      }
    reduceExpression(expression).value
  }

As you can see, this essentially retains the logic of the straight-up recursive implementation, but it's nevertheless stack-safe due to the way Eval's value method is implemented.

Also check out the documentation: https://typelevel.org/cats/datatypes/eval.html

Upvotes: 2

Kolmar
Kolmar

Reputation: 14224

As @JörgWMittag has commented, to process a tree with tail recursion you have to transform the computation, and the most straightforward way is to simulate the call stack and pass it to the recursive calls:

def combine[A](expression: Expression, runners: List[Runner[A]]): Runner[A] = {
  val labelToRunner = runners.map(runner => (runner.label.get, runner)).toMap
  
  sealed trait Element
  case class Op(operation: Operation) extends Element
  case class Expr(expression: Expression) extends Element
  case class Result(runner: Runner[A]) extends Element

  @tailrec
  def reduce(stack: List[Element]): Runner[A] = {
    def expand(expression: Expression): List[Element] = expression match {
      case Label(_, value) =>
        List(Result(labelToRunner(value)))
      case Tree(_, operation, left, right)=>
        List(Expr(left), Expr(right), Op(operation))
    }

    stack match {
      case List(Result(runner)) => runner
      case Expr(expression) :: rest =>
        reduce(expand(expression) ::: rest)
      case (left @ Result(_)) :: Expr(expression) :: rest =>
        // The subtree we are processing is put on the top of the stack
        // Thus when the operation is applied the elements are in reverse order
        reduce(expand(expression) ::: left :: rest)
      case Result(right) :: Result(left) :: Op(operation) :: rest =>
        val combined = operation match {
          case AND => left.and(right)
          case OR => left.or(right)
        }
        reduce(Result(combined) :: rest)
    }
  }

  reduce(List(Expr(expression)))
}

It's interesting to print out the trace of that function to see how it first expands expressions, transforms simple expressions into results, and applies operations. For example here is the stack for some expression on mock runners with numberic labels:

Expr(((1 AND (2 OR 3)) OR 4) AND ((5 OR 6) AND 7))
Expr((1 AND (2 OR 3)) OR 4), Expr((5 OR 6) AND 7), Op(AND)
Expr(1 AND (2 OR 3)), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Expr(1), Expr(2 OR 3), Op(AND), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result(1), Expr(2 OR 3), Op(AND), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Expr(2), Expr(3), Op(OR), Result(1), Op(AND), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result(2), Expr(3), Op(OR), Result(1), Op(AND), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result(3), Result(2), Op(OR), Result(1), Op(AND), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result(2 OR 3), Result(1), Op(AND), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result(1 AND (2 OR 3)), Expr(4), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result(4), Result(1 AND (2 OR 3)), Op(OR), Expr((5 OR 6) AND 7), Op(AND)
Result((1 AND (2 OR 3)) OR 4), Expr((5 OR 6) AND 7), Op(AND)
Expr(5 OR 6), Expr(7), Op(AND), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Expr(5), Expr(6), Op(OR), Expr(7), Op(AND), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Result(5), Expr(6), Op(OR), Expr(7), Op(AND), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Result(6), Result(5), Op(OR), Expr(7), Op(AND), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Result(5 OR 6), Expr(7), Op(AND), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Result(7), Result(5 OR 6), Op(AND), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Result((5 OR 6) AND 7), Result((1 AND (2 OR 3)) OR 4), Op(AND)
Result(((1 AND (2 OR 3)) OR 4) AND ((5 OR 6) AND 7))

Upvotes: 1

Related Questions