haskell 中使用 BST 的集合的交集和差分函数

Question

我已经使用二叉搜索树实现了 Set 数据类型。

我的实现如下：-

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

我还写了一些其他函数，例如toList、fromList和Insert。（在我之前的问题中得到帮助）

这些是我到目前为止编写的函数：

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)

我已经尝试解决以下功能很长时间了。你能帮帮我吗？我进行了多次尝试，但 none 成功了。

   ---- 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

这是我对这个函数的尝试，编译没有错误，但没有解决问题：

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

我无法导入任何外部模块/库。如果有帮助，我还写了一个 setmap 函数。

感谢您的帮助。

Answer 1

这是我的解决方案，它在性能上不是最好的但有效，解决方案是创建一个列表并在过滤器函数中使用元素函数。

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

haskell 中使用 BST 的集合的交集和差分函数

Intersection and difference function on sets using BST in haskell

haskell

set