Functional way to iterate over a nested list

Question

I was asked to compare two trees. Something like below:

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

To compare each element of the tree, I have the 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 the algorithm for each element in n1, we check the correspondence in n2. I was told that this is a very important and non-functional way. What would be a functional way to achieve this behavior. In other words, how do we remove the while loop when comparing the list of children?

Answer 1

If I understand your question correctly, you want to compare each element of the first list with each element of the second list. The following code achieves this. It gets rid of the while through 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 } 

Answer 2

Consider zipping both lists and using forall , which contains true , only if every predicate that it processes evaluates to true ; eg,

 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 stop evaluations because it encounters the first false . Cases of unequal node length lists can be resolved with zipAll by defining the EmptyNode class for marking the fill length; also both empty lists can be compared with true .

Update Sort site lists for validity after @JohnB's comment.