How to construct an infinite immutable tree in scala

4
votes

I was trying to translate a snippet from Java into Scala. It is an infinite tree structure. 

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;
    }

It is working just fine. Once I translated the snipped above to Scala I noticed a problem with Map. Looks like in Scala stock mutable and immutable maps are not compatible.

So I have to use mutable map type in the field Node. As for me it looks weird cause my map is not mutable. It is not changed in Node and Node has to know slightly more about its dependency that it should.

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

I would be glad to see an alternative solution where Node.routes is an immutable map.

3
scalatypes

3 Answers

6
votes

Nothing mutable here:

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

It builds without StackOverflowErrors, and is still infinitely unfoldable:

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

The key is that definitions of functions in a scope can recursively refer to themselves.

0
votes

I don't think it is possible to create cyclic structures without at least some kind of mutability. For example, an alternative way would be to use something like 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

This still does kind of push mutability down to internal implementation of Eval, though, and might be cumbersome to use. It also requires constructing the entire recursive object at once - since the map is immutable, you won't be able to add new items to it, you'll have to recreate the entire structure from scratch.

0
votes
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
  }
}