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?

Do you need to compare every element in the first list with every element in the second list? Or just both first elements, both seconds elements and so on? — fresskoma
– fresskoma, Commented Aug 26, 2014 at 20:59
Yes, I want to compare two unordered children to see weather one list contains exactly the same elements as the other all the way down to the leaf nodes. — user_1357
– user_1357, Commented Aug 27, 2014 at 1:42

samthebest · Accepted Answer · 2014-08-27 14:21:27Z

4

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.

edited Aug 27, 2014 at 14:21

samthebest

31.7k25 gold badges106 silver badges153 bronze badges

answered Aug 26, 2014 at 18:29

elm

20.5k15 gold badges72 silver badges116 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

fresskoma Over a year ago

Maybe I'm misunderstanding the question, but it seems like the OP wants to compare every node in the first list to every other node in the second list. Your code would not achieve that, am I right?

JohnB Over a year ago

With the zipAll and a 'emptynode' instance to pad any missing cases it would compare them all. The issue I see however, is that you could consider them equal if they had all the same nodes but different ordering, so sorting first or converting both lists to sets and doing set1.forall(c => s2.contains(c)) and the inverse.

elm Over a year ago

@JohnB agree, Many Thanks for the comments.

som-snytt Over a year ago

Um, I think Seq already has equals that compares all elements. You could use List.corresponds for other predicates. BTW, OP said children are unordered, but that doesn't sound normal. (sorry, I saw the OP comment "exactly the same elements", which isn't the general compare.)

user_1357 Over a year ago

zip won't work in my case, I need to compare each element of outer list to each element in inner list. Combining nodes at same position won't work.

samthebest · Accepted Answer · 2014-08-27 14:20:32Z

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
}

edited Aug 27, 2014 at 14:20

samthebest

31.7k25 gold badges106 silver badges153 bronze badges

answered Aug 26, 2014 at 21:08

fresskoma

25.9k12 gold badges87 silver badges132 bronze badges

Collectives™ on Stack Overflow

Functional way to loop over nested list

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related