Scala自引用树结构的尾递归merge方法实现探究

更新于2024.03.16：已提供可生成正确输出的代码，但仍非尾递归实现。

如何在Scala的自引用树结构上创建尾递归的merge方法？或者这是否根本不可能实现？

我已研究该问题多日，查阅过相关文章（包括其他语言的实现思路），还尝试过多个AI工具（Bard、Copilot、AskCodi等），但它们返回的代码不仅无法运行，也无法通过@tailrec注解的编译。

我肯定在将Node样例类中的merge方法转换为尾递归实现时，漏掉了某个关键思路，恳请各位提供指导。

尤其希望能获得可指导此类自引用结构自底向上解决方案思考的元认知方法相关资源（书籍、视频、文章等）。

最后，我了解有些问题无法用尾递归解决，那么本次问题是否属于此类？如果是，原因是什么？

修正后的代码 #

以下代码可实现预期功能，但并非尾递归：

object Node {
  val Terminal: Node = Node(true, Map.empty)
}

final case class Node(
    isWord: Boolean
  , nodeByLetter: Map[Char, Node]
) {
  require(
    isWord || nodeByLetter.nonEmpty
    , s"either isWord [$isWord] or nodeByLetter.nonEmpty [${nodeByLetter.nonEmpty}] must be true")

  def merge(that: Node): Node = {
    //@tailrec
    def recursive(cursor: (Node, Node) = (this, that)): Node = {
      cursor match {
        case (Node.Terminal, Node.Terminal) =>
          Node.Terminal
        case (left, Node.Terminal) =>
          if (left.isWord)
            left
          else
            left.copy(isWord = true)
        case (Node.Terminal, right) =>
          if (right.isWord)
            right
          else
            right.copy(isWord = true)
        case (left, right) =>
          val lettersToMerge =
            left.nodeByLetter
              .keySet
              .filter(
                letter =>
                  right.nodeByLetter.keySet.contains(letter)
                    && (left.nodeByLetter(letter) != right.nodeByLetter(letter)))
          if (lettersToMerge.isEmpty)
            Node(
                left.isWord || right.isWord
              , right.nodeByLetter ++ left.nodeByLetter)
          else {
            val nodeKeysAll = (left.nodeByLetter.keySet ++ right.nodeByLetter.keySet)
              .toList
              .sorted
            val nodes = nodeKeysAll
              .map(
                letter =>
                  if (lettersToMerge.contains(letter)) {
                    //this call fails the @tailrec annotation
                    recursive(left.nodeByLetter(letter), right.nodeByLetter(letter))
                  } else
                    left.nodeByLetter.getOrElse(letter, right.nodeByLetter(letter))
              )
            val nodeByLetter = {
              nodes
                .zip(nodeKeysAll)
                .map(_.swap)
                .toMap
            }

            Node(
                left.isWord || right.isWord
              , nodeByLetter
            )
          }
      }
    }

    recursive()
  }
}

取消merge方法中@tailrec行的注释后，以下代码行会触发编译错误：

recursive(left.nodeByLetter(letter), right.nodeByLetter(letter))

IntelliJ中会提示：
Recursive call not in tail position (in @tailrec annotated method)

验证用示例数据 #

object Main {
  def main(args: Array[String]): Unit = {
    //cat
    val t = Node.Terminal
    val at = Node(false, Map('t' -> t))
    val cat = Node(false, Map('a' -> at))
    val catRoot = Node(false, Map('c' -> cat))
    //camp - intentionally not in alpha order
    val p = Node.Terminal
    val mp = Node(true, Map('p' -> p))
    val amp = Node(false, Map('m' -> mp))
    val camp = Node(false, Map('a' -> amp))
    val campRoot = Node(false, Map('c' -> camp))


    val root = catRoot.merge(campRoot)
    println("----------------")
    println("root: " + root)
  }
}

预期输出：

----------------
root: Node(false,Map(c -> Node(false,Map(a -> Node(false,Map(t -> Node(true,Map()), m -> Node(true,Map(p -> Node(true,Map())))))))))

原始提交代码（存在错误） #

该代码无法实现预期功能，更不用说尾递归了。根据StackOverflow的更新规则，我保留了原始代码，修正后的代码见上文：

case class Node(isWord: Boolean, nodeByLetter: Map[Char, Node]) {
  //@tailrec
  final def merge(that: Node): Node = {
    val mergedIsWord = this.isWord || that.isWord
    val mergedNodes =
      (this.nodeByLetter.keySet ++ that.nodeByLetter.keySet)
        .map(letter =>
          (
              letter
            , (this.nodeByLetter.get(letter), that.nodeByLetter.get(letter)) match {
                case (Some(thisNode), Some(thatNode)) =>
                  thisNode.merge(thatNode)
                case (Some(thisNode), None) =>
                  thisNode
                case (None, Some(thatNode)) =>
                  thatNode
                case _ =>
                  throw new IllegalStateException("should never get here")
              }))
        .toMap

    Node(mergedIsWord, mergedNodes)
  }
}

内容的提问来源于stack exchange，提问作者chaotic3quilibrium