Modifying data structures in Scala

Question

I gather from this question that there is no standard Scala approach to dynamically changing data structures. In my case, I will be building a tree in which values are stored at the nodes. As processing progresses, two changes will occur. The tree will grow (new leaves sprout), and the values at the nodes will change. Is there a preferred Scala approach to this sort of structure?

That question was specifically about immutable structures. It's not really the case that Scala doesn't have a standard approach to mutable data structures: take a look at http://www.scala-lang.org/api/current/#scala.Mutable where there are many. But not a tree, though, as it happens (although SortedSet has a RedBlack tree as its underlying data structure). Can you say more about the specific issues/questions you have about implementing a tree in Scala? — The Archetypal Paul, May 01 '14 at 06:22
I can't tell exactly what you need, but a mutable tree seems pretty straightforward? `case class Tree[A](var value: A, children: mutable.Set[Tree[A]] = mutable.Set.empty[Tree[A]])` — Chris Martin, May 01 '14 at 06:44
Thanks, Paul, Chris. I'm familiar with Mutable. I've used collection.mutable.Map quite a bit. (Somehow a mutable Map seems less offensive than a raw mutable `var`.) Chris's suggestion is definitely worth pursuing. FYI the application I'm working on is [MonteCarloTreeSearch](http://arrogant.stanford.edu/ggp/chapters/chapter_08.html) (section 8.3) as discussed in the Coursera [General Game Playing course](https://class.coursera.org/ggp-002/). — RussAbbott, May 01 '14 at 15:55
The specific issue I'm concerned about is violating immutability and the preferred way to do it if one must. — RussAbbott, May 01 '14 at 16:01
While Scala does offer mutable data structures for you to solve the problem the way you are thinking, it's worth the exercise to discover how to use immutable structures to reach a solution. — joescii, May 01 '14 at 16:16

score 0 · Answer 1 · answered May 03 '14 at 05:56

There have been no answers do far. So I'm going to post what I am doing and ask for comments. As background, the application is a game tree for General Game Playing (GGP). The assumption in GGP is that there are any number of players. Each player moves on each turn. In a traditional 2-player game in this framework, the player who is not moving, plays noop.

As a result, in the game tree the node levels alternate: states then moves (from those states), then states again. So a move from a state is itself a node in the tree. Its subnodes are the various states that might result depending on the moves of the other players.

First of all, I'll keep the tree in a mutable Map.

gameTree: collection.mutable.Map[Node, NodeInfo]

(From here on I'll write Map for collection.mutable.Map.)

A Node is a node identifier. It is immutable. Nodes also contain a reference to the game tree. NodeInfo objects store the information kept about each node. They too are immutable, but one NodeInfo object replaces another in the gameTree when the tree information is updated.

class Node(gameTree: Map[Node, NodeInfo])

There are two classes of subnodes, one for states and one for moves from states.

class StateNode(val state: MachineState, gameTree: Map[Node, NodeInfo]) extends Node(gameTree: Map[Node, NodeInfo])

class StateMoveNode(state: MachineState, move: Move, gameTree: Map[Node, NodeInfo]) extends Node(gameTree: Map[Node, NodeInfo])

The following information is stored at each node.

class NodeInfo(parent: Option[Node], children: Buffer[Node], visits: Int, utility: Double)

I'm using Buffer[Node] for the children because this is embedded in a Java application, and transformation from Java produces Buffer.

Nodes have a number of convenience methods. (The the following repeats the Node declaration.)

class Node(gameTree: collection.mutable.Map[Node, NodeInfo]) {

  def children: Buffer[Node] = gameTree(this).children
  // Not every node has a parent. In particular the root doesn't.
  def parent: Option[Node] = gameTree(this).parent
  def utility: Double = gameTree(this).utility
  def visits: Int = gameTree(this).visits

  def incrementVisits = {
    val nodeInfo = gameTree(this)
    val newNodeInfo = new NodeInfo(nodeInfo.parent, nodeInfo.children, nodeInfo.visits + 1, nodeInfo.utility)
    gameTree(this) = newNodeInfo
  }

  def updateUtility(newUtility: Double) = {
    val nodeInfo = gameTree(this)
    val newNodeInfo = new NodeInfo(nodeInfo.parent, nodeInfo.children, nodeInfo.visits, newUtility)
gameTree(this) = newNodeInfo
  }

}

Since Buffer[A] is invariant, when building the children list, I was forced to do the following. For example the children of a (State, Move) node is a Buffer of StateNode objects cast to Node:

new StateNode(state, node.gameTree).asInstanceOf[Node])

Comments/suggestions on any of this are appreciated.

Thanks.

Modifying data structures in Scala

1 Answers1