>module Relations where

>import qualified Data.Map as M
>import qualified Data.Set as S

>fromListS = S.fromList
>emptyS = S.empty
>map' = S.map
>intersection = S.intersection
>elems = S.elems
>unions = S.unions
>emptyM = M.empty
>difference = S.difference
>addListTo_C combiner fm key_elt_pairs
>   = foldl add fm key_elt_pairs	-- foldl adds from the left
>   where
>   add fmap (key,elt) = M.insertWith combiner key elt fmap

>findWithDefault a k fm = M.findWithDefault a k fm



Relations
=========
\label{sec-relations}

In this section, we present a number of operators for manipulating
relations.  To represent relations we use the #Set# library provided
with the GHC and Hugs Haskell implementations.
However, the specification in this paper uses only the operators defined here,
so any other representation would do as well.

>type Rel a b = S.Set (a,b)

Next we describe a number of simple operations on relations.  Most of them
require the elements to be in the class #Ord#.  This is due to the
implementation of the #Set# library.  A different representation may
relax or strengthen these requirements.  

The operations #listToRel# and #relToList# allow us to switch between relations
represented as sets, and relations represented as association lists.

>listToRel :: (Ord a,Ord b) => [(a,b)] -> Rel a b
>listToRel xs = fromListS xs

>relToList :: Rel a b -> [(a,b)]
>relToList r = elems r
 
The empty relation is #emptyRel#. It does not relate any elements at all.

>emptyRel :: Rel a b
>emptyRel = emptyS

The combinators #restrictDom# and #restrictRng# restrict the
domain and range, respectively, of a relation #r#, to the elements satisfying
a predicate #p#. 

>restrictDom :: (Ord a, Ord b) => 
>   (a -> Bool) -> Rel a b -> Rel a b
>restrictDom p r = listToRel [(x,y) | (x,y) <- relToList r, p x]

>restrictRng :: (Ord a, Ord b) => 
>   (b -> Bool) -> Rel a b -> Rel a b
>restrictRng p r = listToRel [(x,y) | (x,y) <- relToList r, p y]

To access the domain and range of a relation, we use the functions
 #dom# and #rng#, respectively.

>--dom :: Ord a => Rel a b -> S.Set a
>dom r = map' fst r

>--rng :: Ord b => Rel a b -> Set b
>rng r = map' snd r

Sometimes it is useful to apply a function to all elements in the
domain or range of a relation.  This is the task of #mapDom# and
 #mapRng#, respectively.

>--mapDom :: (Ord b, Ord x) => 
>--  (a -> x) -> Rel a b -> Rel x b
>mapDom f = map' (\(x,y) -> (f x, y)) 

>--mapRng :: (Ord a, Ord x) => 
>--  (b -> x) -> Rel a b -> Rel a x
>mapRng f = map' (\(x,y) -> (x, f y)) 

We also need to be able to compute the intersection and union of relations.
Elements are related by the intersection of two relations, if they are
related by _both_ relations.  They are related by the union of two relations,
if they are related by _either_ one of them.

>intersectRel :: (Ord a, Ord b) => 
>  Rel a b -> Rel a b -> Rel a b
>r `intersectRel` s = r `intersection` s

>unionRels :: (Ord a, Ord b) => [Rel a b] -> Rel a b
>unionRels rs = unions rs

The function #minusRel# computes the complement of a relation with
respect to another relation.  The new relation relates all those 
elements that are related by #r#, but not by #s#.

>minusRel :: (Ord a, Ord b) => 
>  Rel a b -> Rel a b -> Rel a b
>r `minusRel` s = r `difference` s

Given a predicate #p# over the domain of a relation #r#, #partitionDom# 
produces two new relations: the first one is the subset of #r# whose 
first component satisfies #p#, and the second is the rest of #r#.

>partitionDom :: (Ord a, Ord b) =>
>  (a -> Bool) -> Rel a b -> (Rel a b, Rel a b)
>partitionDom p r = (restrictDom p r, restrictDom (not . p) r)

%\begin{ex}
%If #r = [(1,'a'),(2,'a'),(3,'b')]#, \newline
%then #partitionDom (== 2) r = ([(2,'a')],[(1,'a'),(3,'b')])#.
%\end{ex}

So far we have been thinking of relations as sets of pairs.  An alternative
view is to think of them as functions, which given an element of the
domain, return all related elements in the range.  The function
 #applyRel# converts a relation to a function form.

>applyRel :: (Ord a, Ord b) => Rel a b -> a -> [b]
>--applyRel r a = setToList (rng (restrictDom (== a) r))
>--applyRel r a = [b|(a',b)<-setToList r,a'==a] -- not faster...
>applyRel r k = findWithDefault [] k fm 
>  where fm = addListTo_C (++) emptyM [(a,[b])|(a,b)<- elems r]

Finally we define the operation #unionMapSet#, which is the ``bind''
operator of the set monad.  It is not an operation on relations, but 
rather on arbitrary sets.  It is missing from the #Set# library, so we define
it here.

>unionMapSet :: Ord b => (a -> S.Set b) -> (S.Set a -> S.Set b)
>unionMapSet f = unions . map f . (elems)