Блог

Главная - Вопросы по программированию - Scala, добавление списка не работает внутри рекурсивной функции

Scala, добавление списка не работает внутри рекурсивной функции

#scala #recursion

Вопрос:

Поэтому я работал над алгоритмом, который будет использовать двоичное дерево:

 sealed trait BT case object Empty extends BT case class Node(val x: Int, val left: BT, val right: BT) extends BT

и верните двоичное дерево, но без дубликатов, с помощью рекурсивного dfs для поиска по дереву.

 def removeRecurring_dfs(bt: BT, found: List[Int]): BT = {  def dfs_helper(tree: BT): BT = {  tree match  case Empty =gt; Empty  case Node(x, _, _) if found.contains(x) =gt; dfs_helper(rR(tree))  case Node(x, Empty, Empty) =gt;  x::found  tree  case Node(x, left, Empty) =gt;  x::found  Node(x, dfs_helper(left), Empty)  case Node(x, Empty, right) =gt;  x::found  Node(x, Empty, dfs_helper(right))  case Node(x, left, right) =gt;  x::found  Node(x, dfs_helper(left), dfs_helper(right))  }  def rR(tree: BT): BT = removeNode(tree, findPath(tree))  dfs_helper(bt)  }

Список «найдено» изначально пуст. «removeNode» и «findPath» — это функции, которые помогают мне достичь моей цели. После некоторого тестирования я обнаружил, что

 x::found

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

Я недавно начал играть со scala и не понимаю, что может вызвать такое поведение

Комментарии:

1. Что ж, это может помочь, если перед тем , как пытаться написать двоичное дерево, вы сначала напишете List неизменяемое дерево. Таким образом, вы поймете, почему x :: found это сработало, это создаст НОВЫЙ список, потому что, как вы знаете, идея чего-то неизменного заключается в том, что оно не мутирует. — В любом случае, вы можете добавить дополнительный параметр в свой алгоритм поиска или использовать изменяемую коллекцию или var — Как я уже сказал, если вы новичок в языке, вам следует начать с чего-то более простого.

Ответ №1:

Как уже указывалось, List является неизменяемым, поэтому x :: found создает новый List элемент с x добавлением элемента в found список.

Новое List должно быть сохранено/отправлено куда-то, иначе оно будет потеряно и соберется мусор.

Я не знаю, что 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 =gt; (Empty, found)  case Node(x, left, right) =gt;  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
Метки: ,