如何在Scala中构建一个无限不可变的树

Question

我试图将Java代码片段翻译成Scala。

它是一个无限的树形结构。

class Node {
    public Node(Map<String, Node> routes) {}    
}

class Factory {
    public Map<String, Node> buildRoutes() {
        Map<String, Node> routes = new HashMap<>();
        asList("one", "two").forEach(key -> routes.put(key, new Node(routes));
        return routes;
    }

它正常工作。一旦我将上面的代码片段翻译成Scala，我就注意到Map存在问题。在Scala中，似乎股票可变和不可变映射不兼容。

因此，我必须在字段Node中使用可变映射类型。 对我来说，这看起来很奇怪，因为我的映射是不可变的。 它在节点中没有改变，而节点需要了解更多关于它的依赖关系。

import scala.collection.mutable

case class Node(routes: mutable.Map[String, Node])

object Factory {
   def buildRoutes(): mutable.Map[String, Node] = {
      val routes = new mutable.HashMap[String, Node]
      List("one", "two").foreach(key => routes.put(key, Node(routes)))
      routes
   }
}

我希望看到一种替代方案，其中Node.routes是一个不可变的映射表。

- Daniil Iaitskov

Answer 1

这里没有可变的内容：

class Node(unfold: => Map[String, Node]) {
  def routes: Map[String, Node] = unfold
}

object Factory {
   def buildRoutes: Map[String, Node] = {
      def fix: Map[String, Node] =
        List("one", "two").map(_ -> new Node(fix)).toMap
      fix
   }
}

它可以在没有StackOverflowError的情况下构建，并且仍然可以无限展开：

val rs = Factory.buildRoutes
println(rs("one").routes("one").routes("two").routes("one").routes.keys)

关键在于作用域内函数的定义可以递归地引用自身。

- Andrey Tyukin

---

我曾经接近这个解决方案。我定义了一个包含初始化的字段，使用该字段并在运行时右侧得到null值。明显编译器应该对此进行警告。 - Daniil Iaitskov

Answer 2

我认为没有办法创建循环结构而不具备一定程度的可变性。例如，另一种方式是使用类似于cats.Eval的东西：

import cats.Eval

case class Node(routes: Eval[Map[String, Node]])

val routes: Map[String, Node] = List("one", "two")
  .map(key => key -> Node(Eval.later(routes)))
  .toMap

这仍然会将可变性推向Eval的内部实现，可能使用起来很繁琐。它还需要一次构建整个递归对象-由于映射是不可变的，您将无法向其添加新项，必须从头重新创建整个结构。

- Vladimir Matveev

Answer 3

import scala.collection.immutable

case class Node(routes: Map[String, Node])

object Factory {
  def buildRoutes(): Map[String, Node] = {

    val routes = List("one", "two").foldLeft(Map[String, Node]())((mp, s) =>{
      mp + (s -> Node(mp))
    })
    routes
  }
}

- Howard Clark

---

与 OP 的代码不产生相同的结果，这是一个无限递归的数据结构。 - jwvh