5

我被要求比较两棵树。如下所示：

case class Node(elem:String, child:List[Node])

为了比较树的每个元素，我有以下功能：

def compare(n1:Node, n2:Node): Boolean {
   if(n1.elem == n2.elem){
      return compare(n1.child, n2.child)
   }
}

def compare(c1:List[Node], c2:List[Node]): Boolean {
    while (c1.notEmpty) {
       //filter, map etc call function above to compare the element recursively
    }
}

基本上算法是针对 n1 中的每个元素，我们正在检查 n2 中的匹配。有人告诉我，这是非常必要的方式，而不是功能性的方式。什么是实现这种行为的实用方法。换句话说，我们如何在比较孩子列表时删除while循环？

4

2 回答 2

4

考虑压缩两个列表并仅在它处理的每个谓词评估为时才使用forallwhich hold ；比如像这样，truetrue

def compare(c1: List[Node], c2: List[Node]): Boolean = 
  (c1.sorted zip c2.sorted).forall(c => compare(c._1,c._2))

请注意，forall它将在遇到第一个false. zipAll可以通过定义EmptyNode填充长度差异的类来解决节点列表长度不等的情况；两个列表都为空也可以与true.

在@JohnB 的评论之后，更新已排序的节点列表以确保可靠性。

于 2014-08-26T18:29:57.483 回答
2

如果我正确理解了您的问题，您希望将第一个列表的每个元素与第二个列表的每个元素进行比较。下面的代码实现了这一点。while它通过尾递归摆脱了循环。

import scala.annotation.tailrec

def cmp(a:Int, b:Int) = a > b

@tailrec
def compare(xs: List[Int], ys: List[Int]): Boolean = xs match {
    case Nil => true
    case head :: tail if ys.forall(x => cmp(head, x)) => compare(tail, ys)
    case _ => false
}
于 2014-08-26T21:08:13.690 回答