Hi,
I am looking for a data structure that will represent a collection of
sets such that no element in the collection is a subset of another set.
In other words, inserting an element that is already a subset of another
element will return the original collection, and inserting an element
that is a superset of any elements will result in a collection with the
superset added and the subsets removed.
What I have so far is the below but I am wondering if there has been any
prior work on this (particularly using Haskell but also conceptual
work). Inserting a set that is a subset is easy to handle, inserting a
superset and remove subsets of it is a little tricker.
Cheers
Mark
module SetTrie where
--
-- A set of sets which does not contain elements which are subsets of
any other element.
-- ie insert a element which is a proper subset of another set returns
the same set of sets
-- insert a element which is a proper superset of one or more
elements causes those elements to be removed
-- (and the first element to be added)
--
import Data.Set hiding (toList,singleton,map,insert)
import Data.Map hiding
(fromList,showTreeWith,toAscList,toList,singleton,map,insert)
import qualified Data.Map as M (toList,fromList,lookup,insert)
import qualified Data.Set as S (toList,fromList)
-- Normally we would have a flag at a node to indicate a subset is
there, but we
-- don't store subsets.
data SetTrie a = Leaf [a] | Node (Map a (SetTrie a)) deriving (Show,Eq)
singleton :: Ord a => Set a -> SetTrie a
singleton = Leaf . S.toList
toList' :: Ord a => SetTrie a -> [[a]]
toList' (Leaf xs) = [xs]
toList' (Node m) = concatMap (\(x,y) -> map (x:) (toList' y)) $ M.toList m
toList :: Ord a => SetTrie a -> [Set a]
toList x = map S.fromList $ toList' x
insert :: Ord a => SetTrie a -> Set a -> SetTrie a
insert t s = insert' t $ toAscList s
insert':: Ord a => SetTrie a -> [a] -> SetTrie a
insert' (Leaf (y:ys)) (x:xs) = Node (M.fromList [(y,Leaf ys),(x,Leaf xs)])
insert' (Node m) (x:xs) = case M.lookup x m of
Nothing -> case xs of
[] -> Node $ M.insert x
(Leaf xs) m
_ -> Node $ M.insert x
(Leaf xs) m
Just t' -> case xs of
[] -> Node m
_ -> Node $ M.insert x
(insert' t' xs) m
-- removeSubsets ::
-- terminate (Node m) = Node mTrue m
-- terminate (Leaf (x:xs)) = Node True (M.fromList [(x,Leaf xs)])
s1 = fromList [1,2,3,5,2]
s2 = fromList [2,3,5]
t1 = Node (M.fromList [(1,Leaf [2]),(3,Leaf [5]),(2,Node (M.fromList
[(4,Leaf [6])]))])
t2 = insert (singleton (S.fromList [1])) $ S.fromList [1,2,3]
t3 = insert t1 $ S.fromList [2,4,7]
t4 = insert t2 $ S.fromList [1]
t5 = insert t3 $ S.fromList [2,5]
t6 = insert t5 $ S.fromList [2,4]
-- Now add a superset of everything
t7 = insert (singleton (S.fromList [8])) $ S.fromList [1,2,3,4,5,6,7,8,9]
Mark
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
