CODEWITHSUNDEEP
scalafunctional-programmingtail-recursionfold
COOLBEANS
COOLBEANS

Reputation: 757

Is this Depth First Search implementation tail recursive now?

I had this function for functionally traversing a graph:

private def dfs(current: RCell, rCellsMovedWithEdges: Vector[RCell], acc: Vector[RCell] = Vector()): Vector[RCell] = {
    current.edges.foldLeft(acc) {
      (results, next) =>
        if (results.contains(rCellsMovedWithEdges(next))) results
        else dfs(rCellsMovedWithEdges(next), rCellsMovedWithEdges, results :+ current)
    } :+ current
  }

Implementation taken from manuel kiessling here

It's quite nice, but I'm worried the " :+ current" at the end is making it non-tail recursive.

I changed it to this:

private def dfs(current: RCell, rCellsMovedWithEdges: Vector[RCell]): Vector[RCell] = {

    @annotation.tailrec
    def go(current: RCell, rCellsMovedWithEdges: Vector[RCell], acc: Vector[RCell] = Vector()): Vector[RCell] = {
      current.edges.foldLeft(acc) {
        (results, next) =>
          if (results.contains(rCellsMovedWithEdges(next))) results
          else go(rCellsMovedWithEdges(next), rCellsMovedWithEdges, results :+ current)
      }
    }
    go(current, rCellsMovedWithEdges) :+ current
  }

but the compiler says the recursive call is not in tail position.

Is leftfold already tail recursive per chance?

If not, is there another way to do what I want?

Upvotes: 4

Views: 3904

Answers (2)

Brian McCutchon
Brian McCutchon

Reputation: 8594

It's not tail recursive because the last call is not to go, but to foldLeft. There's no way it could be even mutually tail recursive, as foldLeft calls go multiple times. It's hard to make DFS tail recursive, as the recursive algorithm relies heavily on the call stack to keep track of your position in the tree. I would suggest not bothering if you can guarantee that your tree is shallow. Otherwise, you will need to pass around an explicit stack (List is a good choice here) and completely rewrite your code.

Upvotes: 10

Joe K
Joe K

Reputation: 18434

You must essentially manually manage the stack if you want to implement DFS tail-recursively:

def dfs(start: RCell, rCellsMovedWithEdges: Vector[RCell]): Vector[RCell] = {
  @annotation.tailrec
  def go(stack: List[RCell], visited: Set[RCell], acc: Vector[RCell]): Vector[RCell] = stack match {
    case Nil => acc
    case head :: rest => {
      if (visited.contains(head)) {
        go(rest, visited, acc)
      } else {
        val expanded = head.edges.map(rCellsMovedWithEdges)
        val unvisited = expanded.filterNot(visited.contains)
        go(unvisited ++ rest, visited + head, acc :+ head)
      }
    }
  }
  go(List(start), Set.empty, Vector.empty)
}

Bonus: change unvisited ++ rest to rest ++ unvisited and you get BFS.

Upvotes: 6

Related Questions