Haskell : Comparing if two binary trees have the same elements

Question

So I am working on a function that detects if two binary trees have the same numbers in them.

So what I've come up with is the following which works just fine but the problem is that I am using total of 5 functions. Is there another way of detecting if two BT's have the same elements with just one function ? Here is my solution so far which seems to work just fine.

flatten :: BinTree a -> [a]
flatten Empty        = []
flatten (Node l x r) = flatten l ++ [x] ++ flatten r

splt :: Int -> [a] -> ([a], [a])
splt 0 xs = ([], xs)
splt _ [] = ([],[])
splt n (x:xs) = (\ys-> (x:fst ys, snd ys)) (splt (n-1) xs)

merge :: Ord a => [a] -> [a] -> [a] 
merge xs [] = xs
merge [] ys = ys    
merge (x:xs) (y:ys) = if (x > y) then y:merge (x:xs) ys else x:merge xs(y:ys)

msort :: Ord a => [a] -> [a]
msort [] =[]
msort (x:[]) = (x:[])
msort xs = (\y -> merge (msort (fst y)) (msort (snd y))) (splt (length xs `div` 2) xs)

areTreesEqual :: (Ord a) => BinTree a -> BinTree a-> Bool
areTreesEqual Empty Empty = True
areTreesEqual Empty a = False
areTreesEqual a Empty = False
areTreesEqual a b = msort (flatten (a) ) == msort (flatten (b))

Why do you need to define your own merge-sort function, instead of using Data.List.sort(By)? That would save 3 functions. — kennytm
– kennytm, Commented Sep 28, 2013 at 22:38

daniel gratzer · Accepted Answer · 2013-09-28 22:49:16Z

1

How about

import Data.MultiSet as Set

equal a b = accum a == accum b
  where accum Empty = Set.empty
        accum (Node l x r) = Set.insert x (accum l `Set.union` accum r)

Sets are lovely for unordered comparison and multisets will make sure that

 1   /=   1
1 1

Eg, that duplicate numbers are counted properly. If this isn't a big concern, than swap MultiSet for Set. I think 3 lines is pretty decent for this sort of thing.

edited Sep 28, 2013 at 22:49

answered Sep 28, 2013 at 22:38

daniel gratzer

54k11 gold badges100 silver badges137 bronze badges

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

Collectives™ on Stack Overflow

Haskell : Comparing if two binary trees have the same elements

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related