Scala 方法优化

Question

我有一个递归调用的 def，我正在使用一堆案例。我想知道是否有任何好的解决方案可以摆脱这种情况，同时又不会失去定义的可读性。

 @tailrec
  def getElements(existent:List[List[String]], proposed: List[List[String]], result: List[(String,List[String])]): List[(String, List[String])]= {

    proposed match {
      case head :: tail => {
        existent.find(element => identicalOfMatch(element, head)) match {

          case Some(elem) => getElements(existent.filterNot(e => e == elem), tail, ("Same", elem) :: result)
          case None =>   {
            existent.find(element => noneOfMatch(element, head) && canDelete(proposed, element)) match {

              case Some(elem) => getElements(existent.filterNot(e => e == elem), head::tail, ("Delete", elem) :: result)
              case None => {
                existent.find(element => firstOfMatch(element, head)) match {

                  case Some(elem) => getElements(existent.filterNot(e => e == elem), tail, ("Update", head) :: result)
                  case None => {
                    existent.find(element => anyOfMatch(element, head) && firstOfNotPresent(proposed, head.head) && firstOfNotPresent(existent, head.head)) match {

                      case Some(elem) =>  getElements(existent.filterNot(e => e == elem), tail, ("Update", head) :: result)

                      case None =>        getElements(Nil, Nil, existent.map(element => ("Deleted", element)) ::: proposed.map(element => ("Created", element)) ::: result)
                    }
                  }
                }
              }
            }
          }
        }
      }
      case Nil => result
    }
  }

Answer 1

如果您可以将方法拆分为多个方法，您的方法可读性将会大大提高。不幸的是，如果您希望函数是 tail-recursive.

，则不能这样做

但是有一个名为 trampoline 的解决方案，它允许您创建一个任意深度的函数递归调用链，即 stack-safe.

Trampolines 在包 scala.util.control.TailCalls 中的 Scala 标准库中实现。我重新实现了您的方法以利用它。

我做的第一件事是从 getElements 中删除一个累加器参数，我们将不再需要它。

然后我把getElements拆分成三个函数。我将嵌套函数称为 ifNoneMatched 和 ifNoneMatched2，但您可能会想出更有意义的名称。

然后我将对链中函数的每次调用都包装到 tailcall 中，并将每个常量包装到 done 中（在我们的例子中是 Nil）。当我需要将某些内容附加到递归调用返回的列表时，我使用 TailRec.

中的 flatMap

import scala.util.control.TailCalls._

def getElements(existent:List[List[String]], proposed: List[List[String]]): TailRec[List[(String, List[String])]]= {

    proposed match {
      case head :: tail => {
        existent.find(element => identicalOfMatch(element, head)) match {
          case Some(elem) => tailcall(getElements(existent.filterNot(e => e == elem), tail).map(("Same", elem) :: _))
          case None => tailcall(ifNoneMatched(head, tail, existent, proposed))
        }
      }
      case Nil => done(Nil)
    }
}

def ifNoneMatched(head: List[String], tail: List[List[String]], existent:List[List[String]], proposed: List[List[String]]): TailRec[List[(String, List[String])]] = {
    existent.find(element => noneOfMatch(element, head) && canDelete(proposed, element)) match {

      case Some(elem) => tailcall(getElements(existent.filterNot(e => e == elem), proposed)).map(("Delete", elem) :: _)
      case None => tailcall(ifNoneMatched2(head, tail, existent, proposed))
    }
}

def ifNoneMatched2(head: List[String], tail: List[List[String]], existent:List[List[String]], proposed: List[List[String]]): TailRec[List[(String, List[String])]] = {
    existent.find(element => firstOfMatch(element, head)) match {

      case Some(elem) => getElements(existent.filterNot(e => e == elem), tail).map(("Update", head) :: _)
      case None => {
        existent.find(element => anyOfMatch(element, head) && firstOfNotPresent(proposed, head.head) && firstOfNotPresent(existent, head.head)) match {
          case Some(elem) =>  tailcall(getElements(existent.filterNot(e => e == elem), tail)).map(("Update", head) :: _)
          case None => getElements(Nil, Nil).map(existent.map(element => ("Deleted", element)) ::: proposed.map(element => ("Created", element)) ::: _)
        }
      }
    }
}

getElements returns 现在 TailRec[List[(String, List[String])]]，但你可以通过调用 result.

来解包

当然，您可以将方法嵌套得更深。在将方法调用包装到 tailcall 之前，您的堆栈是安全的。

我没有像 identicalOfMatch 等那样重新实现您的方法，所以我无法真正测试我的实现是否有效。如果有问题请告诉我 ;)

Scala 方法优化

Scala method optimization

scala

optimization

tail-recursion