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

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

但是，这会产生以下编译错误：

不明确的隐式值：类型 Set[Node] 的值visited和类型 scala.collection.immutable.Set[Node] 的值newVisited都与预期的类型 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)    
}

这个想法是将你的阴影隐式移动到一些嵌套的代码块中

Answer 2

对传入的隐式进行阴影处理。

句法解决方案是阴影。隐式的规则是，当两个候选项在作用域中时，使用重载解析。候选人必须可以通过其简单的名字访问。

scala> def f(implicit s: String): String = {
     |   val s0 = s
     |   if (s.length > 10) s else {
     |     implicit val s: String = s0 + "more"
     |     f
     |   }
     | }
f: (implicit s: String)String
scala> f("hi")
res0: String = himoremoremore

如果可以利用重载分辨率，则可以避免阴影和重命名。在这里，类型P2表示"为递归调用做好准备"。

scala> trait P ; trait P2 extends P
defined trait P
defined trait P2
scala> def f(implicit p: P): String = {
     |   if (p.toString.length > 10) p.toString else {
     |     implicit val p2: P2 = new P2 { override def toString = p.toString + "more" }
     |     f
     |   }}
f: (implicit p: P)String
scala> f(new P2 { override def toString = "hi" })
res1: String = himoremoremore

我今天病得太重，无法做有用的工作...