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


-- | Simple set types. Useful to create sets of arbitrary types and nested sets.
--   
--   This package answers two problems : how to make sets of types which
--   does not implement the Ord typeclass and how to make arbitrarily
--   nested sets as set theory allows. The first problem is resolved thanks
--   to <a>HomogeneousSet</a> which is a list where duplicates elements are
--   not allowed and the order of elements is forgotten. The second problem
--   is resolved thanks to <a>PureSet</a>, it is a tree structure where the
--   order of the branches does not matter.
@package WeakSets
@version 0.4.0.0


-- | Homogeneous sets are sets which can contain only one type of values.
--   
--   They are more flexible than Data.Set because they do not require the
--   objects contained to be orderable.
--   
--   The datatype only assumes its components are equatable, it is
--   therefore slower than the Data.Set datatype.
--   
--   We use this datatype because most of the datatypes we care about are
--   not orderable.
--   
--   Inline functions related to homogeneous sets are written between pipes
--   <tt>|</tt>.
--   
--   Function names should not collide with Prelude but may collide with
--   Data.Set.
module Data.WeakSets.HomogeneousSet

-- | A homogeneous set is a list of values.
--   
--   The only differences are that we don't want duplicate elements and we
--   don't need the order of the list elements.
--   
--   To force these constraints, the <a>Set</a> constructor is abstract and
--   is not exported. The only way to construct a set is to use the smart
--   constructor <a>set</a> which ensures the previous conditions.
data Set a

-- | <i>O(1)</i>. The smart constructor of sets. This is the only way of
--   instantiating a <a>Set</a>.
--   
--   If several elements are equal, they are kept until the user wants a
--   list back.
set :: [a] -> Set a

-- | <i>O(n)</i>. Transform a <a>Set</a> back into a list, the list
--   returned does not have duplicate elements, the order of the original
--   list holds.
setToList :: Eq a => Set a -> [a]

-- | <i>O(n^2)</i>. Return a boolean indicating if a <a>Set</a> is included
--   in another one.
isIncludedIn :: Eq a => Set a -> Set a -> Bool

-- | <i>O(n)</i>. Size of a set.
cardinal :: Eq a => Set a -> Int

-- | <i>O(n)</i>. Return wether an element is in a set.
isIn :: Eq a => a -> Set a -> Bool

-- | <i>O(n*m)</i>. Return the intersection of two sets.
(|&|) :: Eq a => Set a -> Set a -> Set a

-- | <i>O(n)</i>. Return the union of two sets.
(|||) :: Set a -> Set a -> Set a

-- | <i>O(n*m)</i>. Return the cartesian product of two sets.
(|*|) :: Set a -> Set b -> Set (a, b)

-- | <i>O(n)</i>. Return the disjoint union of two sets.
(|+|) :: Set a -> Set b -> Set (Either a b)

-- | <i>O(n*m)</i>. Return the difference of two sets.
(|-|) :: Eq a => Set a -> Set a -> Set a

-- | Returns the cartesian product of a set with itself n times.
(|^|) :: (Num a, Eq a) => Set a -> a -> Set [a]

-- | Return the set of all subsets of a given set.
powerSet :: Set a -> Set (Set a)

-- | <i>O(n)</i>. Filter a set according to a condition.
filterSet :: (a -> Bool) -> Set a -> Set a

-- | <i>O(n)</i>. Remove duplicates in the set using your own equality
--   function.
nubSetBy :: (a -> a -> Bool) -> Set a -> Set a

-- | <i>O(1)</i>. Set version of listToMaybe.
setToMaybe :: Set a -> Maybe a

-- | <i>O(1)</i>. Set version of maybeToList.
maybeToSet :: Maybe a -> Set a

-- | <i>O(n)</i>. Set version of catMaybes.
catMaybesToSet :: Set (Maybe a) -> Set a

-- | <i>O(n)</i>. Set version of mapMaybe.
mapMaybeToSet :: (a -> Maybe b) -> Set a -> Set b
instance GHC.Show.Show a => GHC.Show.Show (Data.WeakSets.HomogeneousSet.Set a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.WeakSets.HomogeneousSet.Set a)
instance GHC.Base.Semigroup (Data.WeakSets.HomogeneousSet.Set a)
instance GHC.Base.Monoid (Data.WeakSets.HomogeneousSet.Set a)
instance Data.Foldable.Foldable Data.WeakSets.HomogeneousSet.Set
instance GHC.Base.Functor Data.WeakSets.HomogeneousSet.Set
instance GHC.Base.Applicative Data.WeakSets.HomogeneousSet.Set
instance GHC.Base.Monad Data.WeakSets.HomogeneousSet.Set


-- | Homogeneous functions are functions between <tt>HomogeneousSet</tt>s.
--   
--   They are more flexible than Data.Map because they do not require the
--   keys to be orderable.
--   
--   The datatype only assumes its keys are equatable, it is therefore
--   slower than the Data.Map datatype.
--   
--   We use this datatype because most of the datatypes we care about are
--   not orderable.
--   
--   Inline functions related to homogeneous functions are written between
--   pipes <tt>|</tt>.
--   
--   Function names should not collide with Prelude but may collide with
--   Data.Map.
module Data.WeakSets.HomogeneousFunction

-- | An association list is a list of pairs (key,value).
type AssociationList k v = [(k, v)]

-- | A function of homogeneous sets. It is a set of pairs (key,value) such
--   that their should only be one pair with a given key.
--   
--   It is an abstract type, the smart constructor is <a>function</a>.
data Function k v

-- | <i>O(1)</i>. The smart constructor of functions. This is the only way
--   of instantiating a <a>Function</a>.
--   
--   Takes an association list and returns a function which maps to each
--   key the value associated.
--   
--   If several pairs have the same keys, they are kept until the user
--   wants an association list back.
function :: AssociationList k v -> Function k v

-- | <i>O(n)</i>. Return the domain of a function.
domain :: Function k v -> Set k

-- | <i>O(n)</i>. Return the image of a function. The image of a function
--   is the set of values which are reachable by applying the function.
image :: Function k v -> Set v

-- | <i>O(n)</i>. Return the identity function associated to a <a>Set</a>.
idFromSet :: Set a -> Function a a

-- | Compose two functions. If the two functions are not composable, strips
--   the functions until they can compose.
(|.|) :: (Eq a, Eq b) => Function b c -> Function a b -> Function a c

-- | <i>O(n)</i>. The number of entries in the function.
size :: Eq k => Function k v -> Int

-- | <i>O(n)</i>. Return wether a key is in the function domain or not.
member :: Eq k => Function k v -> k -> Bool

-- | <i>O(n)</i>. Negation of member.
notMember :: Eq k => Function k v -> k -> Bool

-- | <i>O(n)</i>. Apply a function to a given value. If the function is not
--   defined on the given value returns <a>Nothing</a>, otherwise returns
--   <a>Just</a> the image.
--   
--   This function is like <a>lookup</a> in Data.Map for function (the
--   order of the argument are reversed though).
(|?|) :: Eq k => Function k v -> k -> Maybe v

-- | <i>O(n)</i>. Unsafe version of <a>(|?|)</a>.
--   
--   This function is like <tt>(!)</tt> in Data.Map for function.
(|!|) :: Eq k => Function k v -> k -> v

-- | <i>O(n)</i>. Apply a function to a given value, if the value is in the
--   domain returns the image, otherwise return a default value.
--   
--   This function is like <a>findWithDefault</a> in Data.Map for function
--   (the order of the argument are reversed though).
findWithDefault :: Eq k => Function k v -> v -> k -> v

-- | O(1). Insert a new key and value in the function. If the key is
--   already present in the function, the associated value is replaced with
--   the supplied value. insert is equivalent to insertWith const.
insert :: k -> v -> Function k v -> Function k v

-- | O(n). Insert with a function, combining new value and old value.
--   insertWith f key value mp will insert the pair (key, value) into mp if
--   key does not exist in the function. If the key does exist, the
--   function will insert the pair (key, f new_value old_value).
insertWith :: Eq k => (v -> v -> v) -> k -> v -> Function k v -> Function k v

-- | O(n). Insert with a function, combining key, new value and old value.
--   insertWithKey f key value mp will insert the pair (key, value) into mp
--   if key does not exist in the function. If the key does exist, the
--   function will insert the pair (key,f key new_value old_value). Note
--   that the key passed to f is the same key passed to insertWithKey.
insertWithKey :: Eq k => (k -> a -> a -> a) -> k -> a -> Function k a -> Function k a

-- | O(n). Delete a key and its value from the function. When the key is
--   not a member of the function, the original function is returned.
delete :: Eq k => k -> Function k a -> Function k a

-- | O(n). Update a value at a specific key with the result of the provided
--   function. When the key is not a member of the function, the original
--   function is returned.
adjust :: Eq k => (a -> a) -> k -> Function k a -> Function k a

-- | O(n). Adjust a value at a specific key. When the key is not a member
--   of the function, the original function is returned.
adjustWithKey :: Eq k => (k -> a -> a) -> k -> Function k a -> Function k a

-- | O(n). The expression (<a>alter</a> f k function) alters the value x at
--   k, or absence thereof. alter can be used to insert, delete, or update
--   a value in a <a>Function</a>. In short : <a>lookup</a> k (<a>alter</a>
--   f k m) = f (<a>lookup</a> k m).
alter :: Eq k => (Maybe a -> Maybe a) -> k -> Function k a -> Function k a

-- | <i>O(n)</i>. The expression (<a>union</a> t1 t2) takes the left-biased
--   union of t1 and t2. It prefers t1 when duplicate keys are encountered.
union :: Eq k => Function k a -> Function k a -> Function k a

-- | <i>O(n)</i>. Map a function over the keys of a function.
mapKeys :: (k1 -> k2) -> Function k1 v -> Function k2 v

-- | <i>O(n)</i>. Alias of domain.
keys :: Function k v -> Set k

-- | <i>O(n)</i>. Alias of image.
elems :: Function k v -> Set v

-- | <i>O(n)</i>. Transform a function back into its underlying association
--   list.
functionToSet :: Eq k => Function k v -> Set (k, v)

-- | <i>O(n)</i>. Memorize a Haskell function on a given finite domain.
memorizeFunction :: (k -> v) -> Set k -> Function k v
instance (GHC.Classes.Eq k, GHC.Classes.Eq v) => GHC.Classes.Eq (Data.WeakSets.HomogeneousFunction.Function k v)
instance (GHC.Show.Show k, GHC.Show.Show v) => GHC.Show.Show (Data.WeakSets.HomogeneousFunction.Function k v)
instance GHC.Base.Semigroup (Data.WeakSets.HomogeneousFunction.Function k v)
instance GHC.Base.Monoid (Data.WeakSets.HomogeneousFunction.Function k v)
instance Data.Foldable.Foldable (Data.WeakSets.HomogeneousFunction.Function k)
instance GHC.Base.Functor (Data.WeakSets.HomogeneousFunction.Function k)


-- | Pure sets are nested sets which only contain other sets all the way
--   down. They allow to explore basic set theory.
--   
--   Every mathematical object is a set, usual constructions such as Von
--   Neumann numbers and Kuratowski pairs are implemented.
--   
--   It is a tree where the order of the branches does not matter.
--   
--   Functions with the same name as homogeneous set functions are suffixed
--   with the letter <tt>P</tt> for pure to avoid name collision.
module Math.WeakSets.PureSet

-- | A <a>PureSet</a> is a <a>Set</a> of other pure sets.
data PureSet
PureSet :: Set PureSet -> PureSet

-- | Construct a <a>PureSet</a> from a list of pure sets.
pureSet :: [PureSet] -> PureSet

-- | Construct the empty set.
emptySet :: PureSet

-- | Construct the singleton containing a given set.
singleton :: PureSet -> PureSet

-- | Construct an ordered pair from two sets according to Kuratowski's
--   definition of a tuple.
pair :: PureSet -> PureSet -> PureSet

-- | Construct the cartesian product of two sets.
cartesianProduct :: PureSet -> PureSet -> PureSet

-- | Transform a number into its Von Neumann construction
numberToSet :: (Num a, Eq a) => a -> PureSet

-- | Union of two pure sets.
(||||) :: PureSet -> PureSet -> PureSet

-- | Intersection of two pure sets.
(&&&&) :: PureSet -> PureSet -> PureSet

-- | Return wether a pure set is in another one.
isInP :: PureSet -> PureSet -> Bool

-- | Return wether a pure set is included in another one.
isIncludedInP :: PureSet -> PureSet -> Bool

-- | Return the size of a pure set.
card :: PureSet -> Int

-- | Return the set of subsets of a given set.
powerSetP :: PureSet -> PureSet

-- | Prettiffy a pure set according to usual mathematical notation.
prettify :: PureSet -> String

-- | Format pure sets such that if numbers are recognized, they are
--   transformed into integer and if pairs are recognized, they are
--   transformed into pairs.
formatPureSet :: PureSet -> String
instance GHC.Classes.Eq Math.WeakSets.PureSet.PureSet
instance GHC.Show.Show Math.WeakSets.PureSet.PureSet