Functional way to loop over nested list

Question

I was given a question to compare two trees. Something like below:

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

In order to compare each elements of the trees, I have following functions:

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
    }
}

Basically algorithm is for each elements in n1, we are checking for a match in n2. I was told that this is very imperative way and not functional way. What would be a functional way to achieve this behaviour. In other words, how do we remove while loop when comparing the list of children?

Answer 1

Consider zipping both lists and using forall which holds true only if each and every predicate it processes evaluates to true; for instance like this,

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

Note that forall will halt the evaluations as it encounters the first false. Cases of unequal length lists of nodes may be tackled with zipAll by defining an EmptyNode class for padding length differences; also both lists empty may compare to true.

Update Sorted lists of nodes for soundness following comment by @JohnB.

Answer 2

If I understood your question correctly, you want to compare every element of the first list with every element of the second list. The following code achieves this. It gets rid of the while loop via a tail-recursion.

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
}