CODEWITHSUNDEEP
scalatypes
Daniil Iaitskov
Daniil Iaitskov

Reputation: 6039

How to construct an infinite immutable tree in scala

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.

Upvotes: 4

Views: 404

Answers (3)

Andrey Tyukin
Andrey Tyukin

Reputation: 44918

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.

Upvotes: 6

Howard Clark
Howard Clark

Reputation: 21

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

Upvotes: 0

Vladimir Matveev
Vladimir Matveev

Reputation: 127771

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.

Upvotes: 0

Related Questions