Изменить что-то в дереве Scala

Question

У меня есть древовидная структура данных в Scala, построенная с использованием case-классов (это AST, но это не имеет отношения к вопросу).Чтобы изменить дерево, я использую рекурсивную функцию, которая уничтожает и восстанавливает каждый класс наблюдений во всем дереве:

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

Все узлы в дереве просто «проходят», за исключением узла «Лист» справильный идентификатор, который обновляется.У меня есть около 27 различных типов узлов, поэтому блок совпадений становится очень большим.

Может ли этот тип кода соответствия быть выражен более кратким способом?Мне все равно, что код не изменяет дерево на месте, я просто хочу, чтобы оно стало короче.

Answer 1

Эта идиома - применение функции (в вашем случае замена значений для конкретного id) на значения внутри структуры - может быть представлена ​​ Функтором в Cats:

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
}

Если запись дел для разных типов узлов даже один раз затруднительна, вы можете использовать Котята , чтобы получить Functor экземпляр автоматически :

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