% -*- LaTeX -*-
% $Id: Set.lhs,v 1.6 2002/12/20 14:58:46 lux Exp $
%
% Copyright (c) 2002, Wolfgang Lux
% See LICENSE for the full license.
%
\nwfilename{Set.lhs}
\section{Sets}
The module \texttt{Set} implements sets as a special case of finite
maps.
\begin{verbatim}

> module Set where

> import Data.List
> import Data.Maybe

> import Map

> infixl 8 `addToSet`, `deleteFromSet`
> infixl 7 `unionSet`, `intersectionSet`
> infixl 6 `diffSet`, `symDiffSet`
> infix  4 `subsetSet`, `elemSet`, `notElemSet`

> newtype Set a = Set (FM a ())

\end{verbatim}
Two sets are equal if both contain the same elements.
\begin{verbatim}

> instance Ord a => Eq (Set a) where
>   xs == ys = toListSet xs == toListSet ys

> instance (Ord a, Show a) => Show (Set a) where
>   showsPrec p set =
>     showChar '{' . showElems (map shows (toListSet set)) . showChar '}'
>     where showElems = flip (foldr ($)) . intersperse (showChar ',')      -- $

> nullSet :: Ord a => Set a -> Bool
> nullSet = null . toListSet

> zeroSet :: Ord a => Set a
> zeroSet = Set zeroFM

> unitSet :: Ord a => a -> Set a
> unitSet x = Set (unitFM x ())

> addToSet :: Ord a => a -> Set a -> Set a
> addToSet x (Set xs) = Set (addToFM x () xs)

> deleteFromSet :: Ord a => a -> Set a -> Set a
> deleteFromSet x (Set xs) = Set (deleteFromFM x xs)

> elemSet :: Ord a => a -> Set a -> Bool
> elemSet x (Set xs) = isJust (lookupFM x xs)

> notElemSet :: Ord a => a -> Set a -> Bool
> notElemSet x set = not (elemSet x set)

> subsetSet :: Ord a => Set a -> Set a -> Bool
> subsetSet xs ys = all (`elemSet` ys) (toListSet xs)

> fromListSet :: Ord a => [a] -> Set a
> fromListSet = foldr addToSet zeroSet

> toListSet :: Ord a => Set a -> [a]
> toListSet (Set xs) = map fst (toListFM xs)

> unionSet :: Ord a => Set a -> Set a -> Set a
> unionSet xs ys = foldr addToSet xs (toListSet ys)

> unionSets :: Ord a => [Set a] -> Set a
> unionSets = foldr unionSet zeroSet

> intersectionSet :: Ord a => Set a -> Set a -> Set a
> intersectionSet xs ys =
>   foldr addToSet zeroSet [y | y <- toListSet ys, y `elemSet` xs]

> diffSet :: Ord a => Set a -> Set a -> Set a
> diffSet xs ys = foldr deleteFromSet xs (toListSet ys)

> symDiffSet :: Ord a => Set a -> Set a -> Set a
> symDiffSet xs ys = unionSet (diffSet xs ys) (diffSet ys xs)

> mapSet :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b
> mapSet f = fromListSet . map f . toListSet

> domainFM :: Ord a => FM a b -> Set a
> domainFM = Set . fmap (const ())

\end{verbatim}