Изменение узла в дереве классов case Scala

Предположим, что у меня есть некоторое дерево, построенное с использованием классов case, что-то вроде этого: 

abstract class Tree
case class Branch(b1:Tree,b2:Tree, value:Int) extends Tree
case class Leaf(value:Int) extends Tree
var tree = Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(4), Leaf(5),6))

А теперь я хочу построить метод для изменения узла с некоторым идентификатором на другой узел. Этот узел легко найти, но я не знаю, как его изменить. Есть ли простой способ сделать это?

3 4
scala pattern-matching case-class

3 ответа:

Это очень интересный вопрос! Как уже отмечали другие, вам нужно изменить весь путь от корня до узла, который вы хотите изменить. Неизменяемые карты очень похожи, и вы можете узнать что-то , глядя на PersistentHashMap Clojure.

Мои рекомендации таковы:

  • измените Tree на Node. Вы даже называете его узлом в своем вопросе, так что это, вероятно, лучшее название.
  • подтяните value до базового класса. Еще раз, вы говорите об этом в своей книге. вопрос, так что это, вероятно, правильное место для этого.
  • в вашем методе замены убедитесь, что если ни Node, ни его дочерние элементы не изменяются, не создавайте новый Node.

Комментарии приведены в коде ниже: 

// Changed Tree to Node, b/c that seems more accurate
// Since Branch and Leaf both have value, pull that up to base class
sealed abstract class Node(val value: Int) {
  /** Replaces this node or its children according to the given function */
  def replace(fn: Node => Node): Node

  /** Helper to replace nodes that have a given value */
  def replace(value: Int, node: Node): Node =
    replace(n => if (n.value == value) node else n)
}

// putting value first makes class structure match tree structure
case class Branch(override val value: Int, left: Node, right: Node)
     extends Node(value) {
  def replace(fn: Node => Node): Node = {
    val newSelf = fn(this)

    if (this eq newSelf) {
      // this node's value didn't change, check the children
      val newLeft = left.replace(fn)
      val newRight = right.replace(fn)

      if ((left eq newLeft) && (right eq newRight)) {
        // neither this node nor children changed
        this
      } else {
        // change the children of this node
        copy(left = newLeft, right = newRight)
      }
    } else {
      // change this node
      newSelf
    }
  }
}
3

Поскольку ваша древовидная структура неизменна, вы должны изменить весь путь, от узла до корня. когда вы посещаете свое дерево, сохраните список посещенных узлов, а затем обновите все узлы до корня, используя метод копирования , как это предлагает pr10001.

2

Метод copy: 

val tree1 = Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(4), Leaf(5),6))
val tree2 = tree1.copy(b2 = tree1.b2.copy(b1 = Leaf(5))
// -> Branch(Branch(Leaf(1),Leaf(2),3),Branch(Leaf(5), Leaf(5),6))
1