Scala,列表追加在递归函数中不起作用
Scala, list append don't work inside recursive function
所以我正在研究采用二叉树的算法:
sealed trait BT
case object Empty extends BT
case class Node(val x: Int, val left: BT, val right: BT) extends BT
和 return 二叉树,但在递归 dfs 的帮助下没有重复项来搜索树。
def removeRecurring_dfs(bt: BT, found: List[Int]): BT = {
def dfs_helper(tree: BT): BT = {
tree match
case Empty => Empty
case Node(x, _, _) if found.contains(x) => dfs_helper(rR(tree))
case Node(x, Empty, Empty) =>
x::found
tree
case Node(x, left, Empty) =>
x::found
Node(x, dfs_helper(left), Empty)
case Node(x, Empty, right) =>
x::found
Node(x, Empty, dfs_helper(right))
case Node(x, left, right) =>
x::found
Node(x, dfs_helper(left), dfs_helper(right))
}
def rR(tree: BT): BT = removeNode(tree, findPath(tree))
dfs_helper(bt)
}
列表 'found' 最初是空的。 'removeNode' 和 'findPath' 是帮助我实现目标的函数。经过一些测试,我发现
x::found
line 从不工作,即使触发了该行的情况。通过一些 println 操作,结果证明模式匹配按我的意图工作。
我最近开始玩 scala,我不明白是什么导致了这种行为
正如已经指出的那样,List
是不可变的,因此 x :: found
创建一个新的 List
,并在 found
列表前面加上元素 x
。
新的 List
必须在 saved/sent 某处,否则它会丢失并被垃圾收集。
我不知道你的 findPath()
和 removeNode()
方法应该做什么,所以有点难说,但看起来这就是你想要完成的. (Scala-3 语法)
sealed trait BT
case object Empty extends BT
case class Node(x: Int, left: BT, right: BT) extends BT
def removeRecurring_dfs(bt: BT): BT =
def dfs_helper(tree:BT, found:Set[Int]): (BT,Set[Int]) = tree match
case Empty => (Empty, found)
case Node(x, left, right) =>
if found(x) then
dfs_helper(rR(tree), found)
else
val (lftNode, moreFound) = dfs_helper(left, found + x)
val (rgtNode, totalFound) = dfs_helper(right, moreFound)
(Node(x, lftNode, rgtNode), totalFound)
def rR(tree: BT): BT = removeNode(tree, findPath(tree))
dfs_helper(bt, Set())._1
所以我正在研究采用二叉树的算法:
sealed trait BT
case object Empty extends BT
case class Node(val x: Int, val left: BT, val right: BT) extends BT
和 return 二叉树,但在递归 dfs 的帮助下没有重复项来搜索树。
def removeRecurring_dfs(bt: BT, found: List[Int]): BT = {
def dfs_helper(tree: BT): BT = {
tree match
case Empty => Empty
case Node(x, _, _) if found.contains(x) => dfs_helper(rR(tree))
case Node(x, Empty, Empty) =>
x::found
tree
case Node(x, left, Empty) =>
x::found
Node(x, dfs_helper(left), Empty)
case Node(x, Empty, right) =>
x::found
Node(x, Empty, dfs_helper(right))
case Node(x, left, right) =>
x::found
Node(x, dfs_helper(left), dfs_helper(right))
}
def rR(tree: BT): BT = removeNode(tree, findPath(tree))
dfs_helper(bt)
}
列表 'found' 最初是空的。 'removeNode' 和 'findPath' 是帮助我实现目标的函数。经过一些测试,我发现
x::found
line 从不工作,即使触发了该行的情况。通过一些 println 操作,结果证明模式匹配按我的意图工作。
我最近开始玩 scala,我不明白是什么导致了这种行为
正如已经指出的那样,List
是不可变的,因此 x :: found
创建一个新的 List
,并在 found
列表前面加上元素 x
。
新的 List
必须在 saved/sent 某处,否则它会丢失并被垃圾收集。
我不知道你的 findPath()
和 removeNode()
方法应该做什么,所以有点难说,但看起来这就是你想要完成的. (Scala-3 语法)
sealed trait BT
case object Empty extends BT
case class Node(x: Int, left: BT, right: BT) extends BT
def removeRecurring_dfs(bt: BT): BT =
def dfs_helper(tree:BT, found:Set[Int]): (BT,Set[Int]) = tree match
case Empty => (Empty, found)
case Node(x, left, right) =>
if found(x) then
dfs_helper(rR(tree), found)
else
val (lftNode, moreFound) = dfs_helper(left, found + x)
val (rgtNode, totalFound) = dfs_helper(right, moreFound)
(Node(x, lftNode, rgtNode), totalFound)
def rR(tree: BT): BT = removeNode(tree, findPath(tree))
dfs_helper(bt, Set())._1