我已經使用二叉搜索樹實作了 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)
很長一段時間以來，我一直在嘗試解決以下功能。你能幫幫我嗎？我進行了多次嘗試，但都沒有奏效。
---- 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 函式。
謝謝您的幫助。
uj5u.com熱心網友回復：
這是我的解決方案，它的性能不是最好的，但可以作業，解決方案是創建一個串列并在過濾器函式中使用元素函式。
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
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/408313.html
標籤：
上一篇：Haskell元組串列與元組比較