Intersection and difference function on sets using BST in haskell-CodePudding

I have implement the Set datatype using Binary search tree.

My implementation is as follows:-

data Set a = Empty | Node a (Set a) (Set a)

I have also written some other functions such as toList, fromList, and Insert. (took help in my previous question)

These are the functions that I have written until now:

insert :: Ord a => a -> Set a -> Set a
insert x Empty = Node x Empty Empty
insert x (Node e l r)
| x == e = Node e l r
| x < e = Node e (insert x l) r
| otherwise = Node e l (insert x r) 

fromList :: Ord a => [a] -> Set a
fromList [] = Empty
fromList (x:xs) = insert x (fromList xs)

toList :: Set a -> [a]
toList Empty = [] 
toList (Node val l r) = toList l    val : (toList r)

I have been trying to solve the following functions for quite a long time now. Can you please help me out. I have made multiple attempts , but none of them work.

   ---- return the common elements between two Sets
  intersection :: (Ord a) => Set a -> Set a -> Set a   

  -- all the elements in Set A *not* in Set B,
  -- {1,2,3,4} `difference` {3,4} => {1,2}
  -- {} `difference` {0} => {}
  difference :: (Ord a) => Set a -> Set a -> Set a

Here's my attempt to this function, which compiles without an error , but it does not solve the problem:

intersection :: (Ord a) => Set a -> Set a -> Set a
intersection Empty Empty = Empty
intersection l Empty = Empty
intersection Empty r = Empty 
intersection (Node val1 Empty Empty) (Node val2 Empty Empty) = if val1 
== val2 then (Node val1 Empty Empty) else Empty
intersection l (Node val1 l1 r1) =  Node val1 (intersection l l1) r1

I cannot import any external module/ libraries. I have also written a setmap function if that helps .

Thank you for your help.

CodePudding user response：

Here is my solution, it's not the best in performance but work, solution is create a list and use element function inside filter function.

module Lib
  (
    insert, fromList, toList, element, intersection, difference

  )
where
data Set a = Empty | Node a (Set a) (Set a) deriving Show

insert :: Ord a => a -> Set a -> Set a
insert x Empty = Node x Empty Empty
insert x (Node e l r)
  | x == e = Node e l r
  | x < e = Node e (insert x l) r
  | otherwise = Node e l (insert x r)

fromList :: Ord a => [a] -> Set a
fromList = foldr insert Empty

toList :: Set a -> [a]
toList Empty = []
toList (Node val l r) = toList l    val : toList r

element :: Ord t => Set t -> t -> Bool
element Empty _ = False
element (Node v l r) x
  | x == v = True
  | x < v = element l x
  | otherwise  = element r x

intersection :: (Ord a) => Set a -> Set a -> Set a
intersection s1 s2 = intersect
  where
    ls2 = toList s2
    intersect = fromList $ filter (element s1) ls2

difference :: (Ord a) => Set a -> Set a -> Set a
difference s1 s2 = diff
  where
    ls1 = toList s1
    diff = fromList $ filter (not.element s2) ls1