CODEWITHSUNDEEP
haskelltreeequals
JohnQ
JohnQ

Reputation: 1093

Checking if two n-ary trees are equal in Haskell

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?

Upvotes: 1

Views: 1170

Answers (2)

melpomene
melpomene

Reputation: 85887

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

Upvotes: 3

Luka Horvat
Luka Horvat

Reputation: 4412

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

Upvotes: 1

Related Questions