scala - 在递归函数中使用隐式参数

Question

考虑以下假设的二叉树遍历代码:

def visitAll(node: Node, visited: Set[Node]): Unit = {
  val newVisited = visited + node
  if (visited contains node) throw new RuntimeException("Cyclic tree definition")
  else if (node.hasLeft) visitAll(node.left, newVisited)
  else if (node.hasRight) visitAll(node.right, newVisited)
  else ()
}

我想通过隐式设置 visited 参数来减少重复，如下所示:

def visitAll(node: Node)(implicit visited: Set[Node]): Unit = {
  implicit val newVisited = visited + node
  if (visited contains node) throw new RuntimeException("Cyclic tree definition")
  else if (node.hasLeft) visitAll(node.left) // newVisited passed implicitly
  else if (node.hasRight) visitAll(node.right) // newVisited passed implicitly
  else ()
}

然而，这会产生以下编译错误:

ambiguous implicit values: both value visited of type Set[Node] and value newVisited of type scala.collection.immutable.Set[Node] match expected type Set[Node]

有没有一种方法可以让编译器只“期待”visited 参数的隐式值，而不是在递归调用方法时将其用作隐式值？

Answer 1

不幸的是，没有基于注解的解决方案，比如(@noPropagate implicit visited: Set[Node])，所以你必须隐藏它:

scala> def visitAll(node: Node)(implicit visited: Set[Node]): Unit = {
     |     implicit val visited = Set[Node]()
     |     visitAll(node)
     | }
visitAll: (node: Node)(implicit visited: Set[Node])Unit

但是，如果您想访问隐藏值，它就不起作用:

scala> def visitAll(node: Node)(implicit visited: Set[Node]): Unit = {
     |     val unshadowed: Set[Node] = visited
     |     implicit val visited: Set[Node] = unshadowed
     |     visitAll(node)
     | }
<console>:10: error: forward reference extends over definition of value unshadow
ed
           val unshadowed: Set[Node] = visited
                                       ^

因此，这可能会有所帮助(通过 REPL 检查):

def visitAll(node: Node)(implicit visited: Set[Node]): Unit = {     
  val newVisited = visited + node
  ;{
     implicit val visited = newVisited
     if (visited contains node) throw new RuntimeException("Cyclic tree definition")
     else if (node.hasLeft) visitAll(node.left) // newVisited passed implicitly
     else if (node.hasRight) visitAll(node.right) // newVisited passed implicitly
     else ()
  }    
}

或者这个:

def visitAll(node: Node)(implicit visited: Set[Node]): Unit = {     
    ({implicit visited: Set[Node] => 
       if (visited contains node) throw new RuntimeException("Cyclic tree definition")
       else if (node.hasLeft) visitAll(node.left) // newVisited passed implicitly
       else if (node.hasRight) visitAll(node.right) // newVisited passed implicitly
       else ()
    })(visited + node)    
}

想法是将隐藏的隐式移动到一些嵌套的代码块中