-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A data structure representing Relations on Sets.
--   
--   A library to model relationships between two objects that are
--   subclasses of Ord. We use a two Maps that allows fast searching either
--   by the key element or the value element.
@package relation
@version 0.5

module Data.Relation.Internal

-- | Representation of a relation on ordered (<tt>Ord</tt>) values
data Relation a b
Relation :: Map a (Set b) -> Map b (Set a) -> Relation a b
[domain] :: Relation a b -> Map a (Set b)
[range] :: Relation a b -> Map b (Set a)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Data.Relation.Internal.Relation a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.Relation.Internal.Relation a b)
instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (Data.Relation.Internal.Relation a b)

module Data.Relation.Internal.Set

-- | Flatten a set of sets.
flatten :: Ord a => Set (Set a) -> Set a
justUnlessEmpty :: Set a -> Maybe (Set a)


-- | Relations are modeled as assciations between two elements.
--   
--   Relations offer efficient search for any of the two elements.
--   
--   Unlike <a>Data.Map</a>, an element ca be associated more than once.
--   
--   The two purposes of this structure are:
--   
--   <ol>
--   <li>Associating elements</li>
--   <li>Provide efficient searches for either of the two elements.</li>
--   </ol>
--   
--   Since neither <a>map</a> nor <tt>fold</tt> are implemented, you
--   <i>must</i> convert the structure to a list to process sequentially.
module Data.Relation

-- | Representation of a relation on ordered (<tt>Ord</tt>) values
data Relation a b

-- | <tt>size r</tt> returns the number of tuples in the relation.
size :: Relation a b -> Int

-- | True if the relation <tt>r</tt> is the <a>empty</a> relation.
null :: Relation a b -> Bool

-- | Construct a relation with no elements.
empty :: Relation a b

-- | The list must be formatted like: [(k1, v1), (k2, v2),..,(kn, vn)].
fromList :: (Ord a, Ord b) => [(a, b)] -> Relation a b

-- | Builds a <a>Relation</a> consiting of an association between:
--   <tt>x</tt> and <tt>y</tt>.
singleton :: a -> b -> Relation a b

-- | The <a>Relation</a> that results from the union of two relations:
--   <tt>r</tt> and <tt>s</tt>.
union :: (Ord a, Ord b) => Relation a b -> Relation a b -> Relation a b

-- | Union a list of relations using the <a>empty</a> relation.
unions :: (Ord a, Ord b) => [Relation a b] -> Relation a b

-- | Intersection of two relations: <tt>a</tt> and <tt>b</tt> are related
--   by <tt>intersection r s</tt> exactly when <tt>a</tt> and <tt>b</tt>
--   are related by <tt>r</tt> and <tt>s</tt>.
intersection :: (Ord a, Ord b) => Relation a b -> Relation a b -> Relation a b

-- | Insert a relation <tt> x </tt> and <tt> y </tt> in the relation <tt> r
--   </tt>
insert :: (Ord a, Ord b) => a -> b -> Relation a b -> Relation a b

-- | Delete an association in the relation.
delete :: (Ord a, Ord b) => a -> b -> Relation a b -> Relation a b

-- | The Set of values associated with a value in the domain.
lookupDom :: Ord a => a -> Relation a b -> Set b

-- | The Set of values associated with a value in the range.
lookupRan :: Ord b => b -> Relation a b -> Set a

-- | True if the element <tt> x </tt> exists in the domain of <tt> r </tt>.
memberDom :: Ord a => a -> Relation a b -> Bool

-- | True if the element exists in the range.
memberRan :: Ord b => b -> Relation a b -> Bool

-- | True if the relation contains the association <tt>x</tt> and
--   <tt>y</tt>
member :: (Ord a, Ord b) => a -> b -> Relation a b -> Bool

-- | True if the relation <i>does not</i> contain the association
--   <tt>x</tt> and <tt>y</tt>
notMember :: (Ord a, Ord b) => a -> b -> Relation a b -> Bool

-- | Restrict the domain to that of the provided set
restrictDom :: (Ord a, Ord b) => Set a -> Relation a b -> Relation a b

-- | Restrict the range to that of the provided set
restrictRan :: (Ord a, Ord b) => Set b -> Relation a b -> Relation a b

-- | Restrict the domain to exclude elements of the provided set
withoutDom :: (Ord a, Ord b) => Set a -> Relation a b -> Relation a b

-- | Restrict the range to exclude elements of the provided set
withoutRan :: (Ord a, Ord b) => Set b -> Relation a b -> Relation a b

-- | Builds a List from a Relation.
toList :: Relation a b -> [(a, b)]

-- | Returns the domain in the relation, as a Set, in its entirety.
dom :: Relation a b -> Set a

-- | Returns the range of the relation, as a Set, in its entirety.
ran :: Relation a b -> Set b

-- | Returns the converse of the relation.
converse :: Relation a b -> Relation b a

module Data.Relation.Ops

-- | <pre>
--   (Case a |&gt; r b)
--   </pre>
(|$>) :: (Ord a, Ord b) => Set a -> Set b -> Relation a b -> Set b

-- | <pre>
--   (Case b &lt;| r a)
--   </pre>
(<$|) :: (Ord a, Ord b) => Set a -> Set b -> Relation a b -> Set a

-- | Domain restriction for a relation. Modeled on z.
(<|) :: (Ord a, Ord b) => Set a -> Relation a b -> Relation a b

-- | Range restriction for a relation. Modeled on z.
(|>) :: (Ord a, Ord b) => Relation a b -> Set b -> Relation a b