修改Scala树中的内容

Question

我在Scala中使用case类构建了一个树数据结构（它是一个AST，但这与问题无关）。要修改树，我使用带有析构的递归函数并重建整个树中的每个case类：

def update(tree: Tree, id: String, val: Int): Tree = {
  tree match {
    case NodeType1(childs) =>
      NodeType1(childs.map(update(_, id, val)))
    case NodeType2(a, childs) =>
      NodeType2(a, childs.map(update(_, id, val))
    case NodeType3(a, b, childs) =>
      NodeType3(a, b, childs.map(update(_, id, val))
    ...  
    case Leaf(`id`, oldVal) =>
      Leaf(id, val)
  }
}

树中的所有节点都只是“通过”，除了具有正确id的Leaf节点，它被更新。我有大约27种不同的节点类型，因此匹配块变得非常大。

这种类型的匹配代码能否以更简洁的方式表达？我不在乎代码不会修改树，我只是希望它变得更短。

Answer 1

这个成语 - 将一个函数（在你的情况下，替换特定id的值）应用于结构内部的值 - 可以用Cats中的Functor表示：

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

您可以像这样为您的树实现map函数：

implicit val functorForTree: Functor[Tree] = new Functor[Tree] {
  def map[A, B](t: Tree[A])(f: A => B): Tree[B] = t match {
    case NodeType1(childs)    => NodeType1(childs.map(_.map(f))
    case NodeType2(a, childs) => NodeType2(a, childs.map(_.map(f))
    ...
    case LeafNode(a)          => LeafNode(f(a))
  }

请注意，要实现这一点，Tree必须通过叶子类型进行参数化，在您的情况下Leaf(id, val)，即

sealed trait Tree
case class NodeType1(childs: List[Tree]) extends Tree
case class Leaf(id, val) extends Tree

你需要的

sealed trait Tree[Leaf]
case class NodeType1[Leaf](childs: List[Tree[Leaf]]) extends Tree[Leaf]
case class NodeType2[Leaf](a: String, childs: List[Tree[Leaf]]) extends Tree[Leaf]
...
case class LeafNode[Leaf](leaf: Leaf) extends Tree[Leaf]

case class OriginalLeaf(id: String, val: Int)
type OriginalTree = Tree[OriginalLeaf]

现在你的例子变成了：

def update(tree: OriginalTree, id: String, val: Int): OriginalTree = tree.map {
  case OriginalLeaf(oldId, _) if oldId == id => OriginalLeaf(id, val)
  case anyOtherLeaf                          => anyOtherLeaf
}

如果写出不同节点类型的情况甚至一次很麻烦，你可以使用Kittens派生Functor实例automatically：

implicit val functorForTree: Functor[Tree] = {
  import cats.derived._
  import auto.functor._
  semi.functor
}