Making recursive code, tail recursive in Scala

Question

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?

I'd like to make this tail recursive I dont know how to turn the last call tail recursive to take advantage of stack safety — bcb
– bcb, Commented Dec 21, 2020 at 21:08
Please add all clarification to your question by editing it. What keeps you from changing the code? — Nico Haase
– Nico Haase, Commented Dec 21, 2020 at 21:09
Tail recursion is when the recursive call is the last call. When recursing over a binary tree, there are by necessity two recursive calls, one for each subtree, but there can only be one tail recursive call, by definition. Therefore, tree iteration is not "naturally" tail recursive like list iteration is. You will have to restructure your computation to make it tail recursive. Typically, you do that by manually creating your own stack and managing it the same way the computer would do for you for a non tail recursive call. — Jörg W Mittag
– Jörg W Mittag, Commented Dec 21, 2020 at 21:41

Matthias Berndt · Accepted Answer · 2023-04-21 08:45:52Z

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

Kolmar · Accepted Answer · 2020-12-22 05:29:03Z

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

Collectives™ on Stack Overflow

Making recursive code, tail recursive in Scala

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related