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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
2 Comments »

2 Responses to “Sets”

  1. Programming Praxis – Sets | Bonsai Code said
    June 7, 2013 at 7:16 PM

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

  2. Remco Niemeijer said
    June 7, 2013 at 7:16 PM

    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 comment