更新 2024.03.16： 提供了产生正确输出的代码，但仍然不是尾递归。
如何在 Scala 中在自引用树结构上创建尾递归
merge我已经研究这个问题好几天了。我读过有关接近它的文章，甚至是其他语言的文章。我什至将其提交给各种 AI（Bard、Copilot、AskCodi 等），它们返回的非功能代码仍然无法使用
@tailrec我一定错过了将
mergeNode尤其是任何提供元认知方式来“思考”这种自下而上的解决方案风格构建的自我参照的东西（书籍、视频、文章等的链接）。
最后，我现在知道有些问题无法通过尾递归解决。是不是这个的情况呢？如果是这样，为什么？
更正代码：
这实现了所需的效果，但不是尾递归。
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()
}
}
当方法
@tailrecmergerecursive(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)
}
}
总结：
OP 标题中括号问题的答案...
...（或者甚至可能）？
...是“是”。
OP 标题中完整问题的答案...
如何在 Scala 中的自引用树结构上创建尾递归合并方法？
...就是“只要有任何需要遵循递归调用的情况，就转向基于堆的策略，甚至在返回路径之前进行额外的递归调用。”
详情：
问题是可以解决的，但使用
@tailrec（特别排除了我在Reddit上探索理解的令人费解的挥手方法
sequenceimport scala.annotation.tailrec
import scala.util.control.TailCalls._
object Node {
val Terminal: Node = Node(true, Map.empty)
def encode(word: String): Node =
word
.reverse
.foldLeft(Node.Terminal) {
(node, letter) =>
Node(false, Map(letter -> node))
}
}
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 find(chars: String): Boolean = {
@tailrec
def recursive(charsRemaining: String = chars, node: Node = this): Boolean =
charsRemaining match {
case "" => node.isWord
case charsRemainder =>
node.nodeByLetter.get(charsRemainder.head) match {
case Some(nextNode) => recursive(charsRemainder.tail, nextNode)
case None => false
}
}
recursive()
}
def merge(that: Node): Node = {
def sequence[A](listTailRecA: List[TailRec[A]]): TailRec[List[A]] =
listTailRecA
.reverse
.foldLeft(done(Nil): TailRec[List[A]]) {
(tailRecListA, tailRecA) =>
tailRecA map ((_: A) :: (_: List[A])).curried flatMap tailRecListA.map
}
def recursive(cursor: (Node, Node) = (this, that)): TailRec[Node] = {
cursor match {
case (Node.Terminal, Node.Terminal) =>
done(Node.Terminal)
case (left, Node.Terminal) =>
if (left.isWord)
done(left)
else
done(left.copy(isWord = true))
case (Node.Terminal, right) =>
if (right.isWord)
done(right)
else
done(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)
done(Node(
left.isWord || right.isWord
, right.nodeByLetter ++ left.nodeByLetter))
else {
val nodeKeysAll = (left.nodeByLetter.keySet ++ right.nodeByLetter.keySet)
.toList
.sorted
val listTailRecNode = nodeKeysAll
.map(
letter =>
if (lettersToMerge.contains(letter))
tailcall(recursive(left.nodeByLetter(letter), right.nodeByLetter(letter)))
else
done(left.nodeByLetter.getOrElse(letter, right.nodeByLetter(letter)))
)
val tailRecListNode = sequence(listTailRecNode)
tailRecListNode
.map(
ln => {
val nodeByLetter = ln.zip(nodeKeysAll).map(_.swap).toMap
Node(
left.isWord || right.isWord
, nodeByLetter
)
})
}
}
}
recursive().result
}
}