Checking if two n-ary trees are equal in Haskell

Question

I am trying to implement a simple boolean function in Haskell to check if two n-ary trees are equal.

My code is:

-- This is the n-ary tree definition.
-- (I know "Leaf a" is not necessary but I prefer to write it for clarity)
data Tree a = Leaf a | Node a [Tree a]
    deriving (Show)

-- This is a simple tree used for test purposes
t :: Tree Int
t = Node 3 [Node 5 [Leaf 11, Leaf 13, Leaf 15], Leaf 7, Leaf 9]

treeEquals :: Eq a => Tree a -> Tree a -> Bool
treeEquals (Leaf n1) (Leaf n2) = n1 == n2
treeEquals (Node n1 xs1) (Node n2 xs2) = n1 == n2 && and(zipWith (treeEquals) xs1 xs2)
treeEquals _ _ = False

My problem is that if I do tests such as:

treeEquals t t
treeEquals t (Leaf 3)
treeEquals t (Node 3 [Leaf 7])

it returns correctly false because the trees are not equal, but if I try a test such as:

treeEquals t (Node 3 [])

It doesn't work because it returns true as the trees were equals.

Do you know what I am doing wrong?

Are there better ways to implement this method without using zipWith avoiding two lists traversals? — JohnQ
– JohnQ, Commented Dec 13, 2012 at 18:51
Using Leaf in this fashion actually leads to redundant representations: Node x [] vs Leaf x. Redundant representations should normally be used only for a good reason (e.g., if they allow some operations to be much faster). In this case, just dropping the Leaf constructor seems likely to be the best course of action. Alternatively, you could change the Node constructor to Node a (Tree a) [Tree a], but why bother? — dfeuer
– dfeuer, Commented Jun 26, 2014 at 0:50

melpomene · Accepted Answer · 2012-12-13 18:55:53Z

3

Why don't you just derive Eq and use ==?

The problem with your current code is the zipWith. It stops as soon as it reaches the end of the shorter list, so zipWith treeEquals foo [] always returns [] (regardless of what foo is).

Here's an (untested) alternative solution:

treeEquals :: Eq a => Tree a -> Tree a -> Bool
treeEquals (Leaf n1) (Leaf n2) = n1 == n2
treeEquals (Node n1 xs1) (Node n2 xs2) = n1 == n2 && listTreeEquals xs1 xs2
    where
    listTreeEquals [] [] = True
    listTreeEquals (x1 : xs1) (x2 : xs2) = treeEquals x1 x2 && listTreeEquals xs1 xs2
    listTreeEquals _ _ = False
treeEquals _ _ = False

edited Dec 13, 2012 at 18:55

answered Dec 13, 2012 at 18:44

melpomene

86.2k8 gold badges96 silver badges155 bronze badges

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

2 Comments

JohnQ Over a year ago

Thank you for your answer. Yes, I have understood what's the problem. Unfortunately I have to implement my own method because I have to exercise myself for an exam. I am trying to implement all the possible things they could ask me, so I can't just use ==.

Daniel Fischer Over a year ago

@JohnQ The cool thing about (==) here is that even if you don't derive it, but implement it yourself, you can define (Node n1 xs1) == (Node n2 xs2) = n1 == n2 && xs1 == xs2 [plus the equations for the other cases, Leaf/Leaf and _/_]. The xs1 == xs2 then uses the generic instance Eq a => Eq [a] to do the right thing. For your treeEquals, you could then simply use treeEquals = (==) ;)

Luka Horvat · Accepted Answer · 2012-12-13 18:46:13Z

1

Add another && before the zipWith and check if the lengths of the lists are the same.

answered Dec 13, 2012 at 18:46

Luka Horvat

4,4224 gold badges35 silver badges51 bronze badges

2 Comments

stephen tetley Over a year ago

Doing this means potentially two list traversals - it's better not to use zipWith in the first place.

JohnQ Over a year ago

@Darwin, thanks for your answer. I had not thought that, it was so simple!

Collectives™ on Stack Overflow

Checking if two n-ary trees are equal in Haskell

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related