Блог

У меня есть древовидная структура данных в 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)
  }
}
  

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

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

Эта идиома — применение функции (в вашем случае, замена значений для определенного 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
}
  

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

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