Relations is imported by: AST4ModSys, CheckModules, ModSysAST, Modules, PPModules, WorkModule, ScopeModule, PFE2, PFE3, PFE4, PFE_StdNames, Pfe2Cmds, Pfe4Cmds, PfeDepCmds, ToQC.

>moduleRelationswhere> >importFiniteMap(emptyFM,addListToFM_C,lookupWithDefaultFM) >importSets

\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.

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::(Orda,Ordb)=>[(a,b)]->Relab>listToRelxs=mkSetxs>relToList::Relab->[(a,b)] >relToListr=setToListr

The empty relation is `emptyRel`. It does not relate any elements at all.

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

>restrictDom::(Orda,Ordb)=>> (a->Bool)->Relab->Relab>restrictDompr=listToRel[(x,y)|(x,y)<-relToListr,px] >restrictRng::(Orda,Ordb)=>> (b->Bool)->Relab->Relab>restrictRngpr=listToRel[(x,y)|(x,y)<-relToListr,py]

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

> --dom :: Ord a => Rel a b -> Set a >domr=mapSetfstr> --rng :: Ord b => Rel a b -> Set b >rngr=mapSetsndr

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 >mapDomf=mapSet(\(x,y)->(fx,y)) > --mapRng :: (Ord a, Ord x) => > -- (b -> x) -> Rel a b -> Rel a x >mapRngf=mapSet(\(x,y)->(x,fy))

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::(Orda,Ordb)=>>Relab->Relab->Relab>r`intersectRel`s=r`intersect`s>unionRels::(Orda,Ordb)=>[Relab]->Relab>unionRelsrs=unionManySetsrs

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`.

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::(Orda,Ordb)=>> (a->Bool)->Relab->(Relab,Relab) >partitionDompr=(restrictDompr,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::(Orda,Ordb)=>Relab->a->[b] > --applyRel r a = setToList (rng (restrictDom (== a) r)) > --applyRel r a = [b|(a',b)<-setToList r,a'==a] -- not faster... >applyRelr=lookupWithDefaultFMfm[] >wherefm=addListToFM_C(++)emptyFM[(a,[b])|(a,b)<-setToListr]

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::Ordb=>(a->Setb)->(Seta->Setb) >unionMapSetf=unionManySets.mapf.setToList

Index

(HTML for this module was generated on 2009-01-04. About the conversion tool.)