循环嵌套列表的功能方法

Question

我有一个问题来比较两棵树.如下所示:

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循环？

Answer 1

如果我正确理解你的问题，你想将第一个列表的每个元素与第二个列表的每个元素进行比较。下面的代码实现了这一点。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
}