Sets

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.

About these ads

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 http://bonsaicode.wordpress.com/2013/06/07/programming-praxis-sets/ 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 H.new
    
    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:

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 612 other followers

%d bloggers like this: