Почему Scala не может скомпилировать эту функцию как хвостовую рекурсивную? - PullRequest
Новая
       33

Почему Scala не может скомпилировать эту функцию как хвостовую рекурсивную?

0 голосов
/ 25 января 2020

Если я заменим первую строку следующей функции поиска первой рекурсивной глубины на строки, закомментированные в пределах блока foreach, она не сможет скомпилироваться как хвостовая рекурсивная функция (из-за аннотации @ tailre c), даже если рекурсия по-прежнему явно последнее действие функции. Есть ли законная причина для такого поведения? 

@tailrec def searchNodes(nodes: List[Node], visitedNodes: List[Node], end: String, currentLevel: Int) : Int = {
    if (nodes.exists(n => n.id == end)) return currentLevel
    val newVisitedNodes = visitedNodes ::: nodes
    var nextNodes = List[Node]()
    nodes.foreach(n => {

        /*
        if (n.id == end){
            return currentLevel
        } 
        */
        nextNodes = nextNodes ::: n.addAdjacentNodes(visitedNodes)
    })
    if (nextNodes.size == 0) return -1
    return searchNodes(nextNodes, newVisitedNodes, end, currentLevel + 1)
}

Ответы [ 2 ]

5 голосов
/ 25 января 2020

Как объясняется в другом ответе, использование return в scala - плохая идея и анти-паттерн. Но что еще хуже использует return внутри лямбда-функции (как ваш закомментированный код внутри foreach): это на самом деле выдает исключение, которое затем перехватывается снаружи для выхода из основной функции ,

В результате тело вашей функции скомпилировано во что-то вроде: 

def foo(nodes: List[Node]) = {
  val handle = new AnyRef
  try {
     nodes.foreach { n => 
       if(n.id == "foo") throw new NonLocalReturnControl(handle, currentLevel)
     ...
     foo(nextNodes)
  } catch {
     case nlrc: NonLocalReturnControl[Int] if nlrc.key == handle => nlrc.value
  }
}

Как вы можете видеть, ваш рекурсивный вызов здесь не в хвостовой позиции, поэтому ошибка компилятора ле git.

Еще одним идиоматическим c способом написать то, что вы хотите, будет деконструкция списка и использование самой рекурсии в качестве «движка» для l oop: 

def searchNodes(nodes: List[Node], end: String) = {
  @tailrec def doSearch(
    nodes: List[(Node, Int)], 
    visited: List[Node], 
    end: String
  ) : Int = nodes match {
    case Nil => -1
    case (node, level) :: tail if node.id == end => level
    case (node, level) :: tail => 
      doSearch(
        tail ::: node.addAdjacentNodes(visited).map(_ -> level+1),
        node :: visited,
        end
      )
  }

  doSearch(nodes.map(_ -> 0), Nil, end)
}
3 голосов
/ 25 января 2020

Я не совсем уверен, о чем думает компилятор, но я думаю, что все ваши return утверждения будут вызывать проблемы .

Использование return является антипаттерном в scala - вам не нужно писать это, и вы не должны. Чтобы избежать этого, вам придется реструктурировать свои if ... return блоки в виде if ... value ... else ... other value блоков.

Эта форма возможна, потому что все является выражением (своего рода). Ваш def имеет значение, которое определяется блоком if ... else, где if и else оба имеют значения и так далее до конца. Если вы хотите игнорировать значение чего-либо, вы можете просто поставить новую строку после него, а возвращаемое значение блока всегда будет значением последнего выражения в нем. Вы можете сделать это, чтобы избежать необходимости переписывать ваш foreach, но было бы лучше написать его функционально, как map.

...