June 7, 2013

Sets are ubiquitous in programming; we’ve used sets in several of our exercises. In most cases we made the sets from lists, which is good enough when the sets are small but quickly slows down when the sets get large. In today’s exercise we will write a generic library for sets.

The sets that we will consider are collections of items without duplicates. We will provide an adjoin function to add an item to a set if it is not already present and a delete function to remove an item from a set if it is present. A member function determines if a particular item is present in a set. The three set operations that are provided are intersection, union and difference; we will consider that the universe from which items are drawn is infinite, or at least too large to conveniently enumerate, so we will not provide a complement operation. For convenience, we will also provide functions to calculate the cardinality of a set and to create a list from the items present in the set.

Your task is to write a library for handling sets, based on the description given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


Pages: 1 2

2 Responses to “Sets”

  1. […] today’s Programming Praxis exercise, our goal is to implement a Set data structure. Let’s get […]

  2. My Haskell solution (see for a version with comments):

    import Data.Hashable
    import qualified Data.HashTable.IO as H
    import Data.List (sort)
    data Set a = Set (H.BasicHashTable a ())
    new :: IO (Set a)
    new = fmap Set
    member :: (Eq a, Hashable a) => a -> Set a -> IO Bool
    member x (Set s) = fmap (maybe False $ const True) $ H.lookup s x
    adjoin :: (Eq a, Hashable a) => a -> Set a -> IO (Set a)
    adjoin x (Set s) = H.insert s x () >> return (Set s)
    delete :: (Eq a, Hashable a) => a -> Set a -> IO (Set a)
    delete x (Set s) = H.delete s x >> return (Set s)
    fold :: (a -> b -> IO b) -> Set a -> b -> IO b
    fold f (Set s) x = H.foldM (\a (k,_) -> f k a) x s
    union :: (Eq a, Hashable a) => Set a -> Set a -> IO (Set a)
    union s1 s2 = fold adjoin s2 =<< fold adjoin s1 =<< new
    combine :: (Eq a, Hashable a) => (Bool -> Bool) -> Set a -> Set a -> IO (Set a)
    combine cond s1 s2 = fold (\k a -> member k s2 >>= \b ->
        if cond b then adjoin k a else return a) s1 =<< new 
    intersect :: (Eq a, Hashable a) => Set a -> Set a -> IO (Set a)
    intersect = combine id
    minus :: (Eq a, Hashable a) => Set a -> Set a -> IO (Set a)
    minus = combine not
    toList :: Set a -> IO [a]
    toList s = fold ((return .) . (:)) s []
    size :: Set a -> IO Int
    size = fmap length . toList

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: