-- 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 and maps of types
-- which do not implement the Ord typeclass and how to make arbitrarily
-- nested sets as set theory allows. The first problem is resolved thanks
-- to WeakSets and WeakMaps. The second problem is resolved
-- thanks to PureSet.
@package WeakSets
@version 1.2.3.0
-- | Weak sets are sets of objects which do not have to be orderable. They
-- are homogeneous, they can only contain a single type of object.
--
-- They are more flexible than Data.Set, they are quicker at insertion
-- but slower at retrieving elements because the datatype only assumes
-- its components are equatable.
--
-- We use this datatype because most of the datatypes we care about are
-- not orderable. It also allows to define a Functor, Applicative and
-- Monad structure on sets.
--
-- Almost all Data.WeakSet functions are implemented so that you can
-- replace a Data.Set import such as
--
--
-- import Data.Set (Set)
-- import qualified Data.Set as Set
--
--
-- by a Data.WeakSet import such as
--
--
-- import Data.WeakSet (Set)
-- import qualified Data.WeakSet as Set
--
--
-- without breaking anything in your code.
--
-- The only functions for which this would fail are the functions
-- converting sets back into list (they require the Eq typeclass unlike
-- in Data.Set). size is one of them.
--
-- If a function really requires the Ord typeclass to even make sense,
-- then it is not defined in this package, you should use Data.Set.
--
-- Note that, just like in Data.Set, the implementation is generally
-- left-biased. Functions that take two sets as arguments and combine
-- them, such as union and intersection, prefer the entries in the first
-- argument to those in the second.
--
-- Functions with non colliding names are defined in Data.WeakSet.Safe.
-- Inline functions are written between pipes |.
--
-- This module is intended to be imported qualified, to avoid name
-- clashes with Prelude functions, except for functions in
-- Data.WeakSet.Safe, e.g.
--
--
-- import Data.WeakSet (Set)
-- import qualified Data.WeakSet as Set
-- import Data.WeakSet.Safe
--
--
-- Unlike Data.Set, we defer the removing of duplicate elements to the
-- conversion back to a list. It is therefore a valid Functor,
-- Applicative and Monad. This allows to create weak sets by
-- comprehension if you include the MonadComprehensions pragma at the
-- beginning of your file.
--
-- Beware if the set is supposed to contain a lot of duplicate elements,
-- you should purge them yourself by transforming the set into a list and
-- back into a set. The time complexity is always given in function of
-- the number of elements in the set including the duplicate elements.
module Data.WeakSet
-- | A weak set is a list of values such that the duplicate elements and
-- the order of the elements are disregarded.
--
-- To force these constraints, the Set constructor is abstract and
-- is not exported. The only way to construct a set is to use the smart
-- constructor fromList or set which ensures the previous
-- conditions.
data Set a
-- | Alias of mempty. Defined for backward compatibility with Data.Set.
empty :: Set a
-- | Alias of pure. Defined for backward compatibility with Data.Set.
singleton :: a -> Set a
-- | O(1). The smart constructor of sets. This is the only way of
-- instantiating a Set with fromList.
--
-- We prefer the smart constructor set because its name does not
-- collide with other data structures.
set :: [a] -> Set a
-- | O(1). This smart constructor is provided to allow backward
-- compatibility with Data.Set.
fromList :: [a] -> Set a
-- | O(1). Defined for backward compatibility with Data.Set.
fromAscList :: [a] -> Set a
-- | O(1). Defined for backward compatibility with Data.Set.
fromDescList :: [a] -> Set a
-- | O(1). Defined for backward compatibility with Data.Set.
fromDistinctAscList :: [a] -> Set a
-- | O(1). Defined for backward compatibility with Data.Set.
fromDistinctDescList :: [a] -> Set a
-- | Return the set of all subsets of a given set.
--
-- Example :
--
--
-- ghci> powerSet $ set [1,2,3]
-- (set [(set []),(set [1]),(set [2]),(set [1,2]),(set [3]),(set [1,3]),(set [2,3]),(set [1,2,3])])
--
powerSet :: Set a -> Set (Set a)
-- | Alias of intersection.
(|&|) :: Eq a => Set a -> Set a -> Set a
-- | Alias of union.
(|||) :: Set a -> Set a -> Set a
-- | Alias of cartesianProduct.
(|*|) :: Set a -> Set b -> Set (a, b)
-- | Alias of disjointUnion.
(|+|) :: Set a -> Set b -> Set (Either a b)
-- | Alias of difference.
(|-|) :: Eq a => Set a -> Set a -> Set a
-- | Returns the cartesian product of a set with itself n times.
(|^|) :: Eq a => Set a -> Int -> Set [a]
-- | O(1). Insert an element in a set. If the set already contains an
-- element equal to the given value, it is replaced with the new value.
insert :: a -> Set a -> Set a
-- | O(n). Delete an element from a set.
delete :: Eq a => a -> Set a -> Set a
-- | O(n). (alterF f x s) can delete or insert x in s depending on
-- whether an equal element is found in s.
--
-- Note that unlike insert, alterF will not replace an element equal to
-- the given value.
alterF :: (Eq a, Functor f) => (Bool -> f Bool) -> a -> Set a -> f (Set a)
-- | O(1). Return wether the set is empty.
null :: Set a -> Bool
-- | O(n). Return wether an element is in a set.
isIn :: Eq a => a -> Set a -> Bool
-- | O(n). Alias of isIn. Defined for backward compatibility
-- with Data.Set.
member :: Eq a => a -> Set a -> Bool
-- | O(n). Negation of member. Defined for backward
-- compatibility with Data.Set.
notMember :: Eq a => a -> Set a -> Bool
-- | O(n^2). Size of a set.
cardinal :: Eq a => Set a -> Int
-- | O(n). Size of a set.
size :: Eq a => Set a -> Int
-- | O(n^2). Return a boolean indicating if a Set is included
-- in another one.
isIncludedIn :: Eq a => Set a -> Set a -> Bool
-- | O(n^2). Return a boolean indicating if a Set is included
-- in another one.
isSubsetOf :: Eq a => Set a -> Set a -> Bool
-- | O(n^2). x is a proper subset of y if x is included in y and x
-- is different from y.
isProperSubsetOf :: Eq a => Set a -> Set a -> Bool
-- | O(n^2). Check whether two sets are disjoint (i.e., their
-- intersection is empty).
disjoint :: Eq a => Set a -> Set a -> Bool
-- | O(n). The union of two sets, preferring the first set when
-- equal elements are encountered.
union :: Set a -> Set a -> Set a
-- | The union of the sets in a Foldable structure.
unions :: Foldable f => f (Set a) -> Set a
-- | O(n*m). Difference of two sets.
difference :: Eq a => Set a -> Set a -> Set a
-- | See difference.
(\\) :: Eq a => Set a -> Set a -> Set a
-- | O(m*n). Return the intersection of two sets. Elements of the
-- result come from the first set.
intersection :: Eq a => Set a -> Set a -> Set a
-- | O(m*n). Return the cartesian product of two sets.
cartesianProduct :: Set a -> Set b -> Set (a, b)
-- | O(n). Return the disjoint union of two sets.
disjointUnion :: Set a -> Set b -> Set (Either a b)
-- | O(n). Filter all elements that satisfy the predicate.
filter :: (a -> Bool) -> Set a -> Set a
-- | O(n). Partition the set into two sets, one with all elements that
-- satisfy the predicate and one with all elements that don't satisfy the
-- predicate. See also split.
partition :: (a -> Bool) -> Set a -> (Set a, Set a)
-- | O(n^2). Lookup the index of an element, which is its zero-based index
-- in the sorted sequence of elements. The index is a number from 0 up
-- to, but not including, the size of the set.
lookupIndex :: Eq a => a -> Set a -> Maybe Int
-- | O(n^2). Return the index of an element, which is its zero-based index
-- in the sorted sequence of elements. The index is a number from 0 up
-- to, but not including, the size of the set. Calls error when the
-- element is not a member of the set.
findIndex :: Eq a => a -> Set a -> Int
-- | O(n^2). Retrieve an element by its index, i.e. by its zero-based index
-- in the sorted sequence of elements. If the index is out of range (less
-- than zero, greater or equal to size of the set), error is
-- called.
elemAt :: Eq a => Int -> Set a -> a
-- | O(n). Delete the element at index, i.e. by its zero-based index in the
-- sorted sequence of elements. If the index is out of range (less than
-- zero, greater or equal to size of the set), error is called.
deleteAt :: Eq a => Int -> Set a -> Set a
-- | O(n^2). Take a given number of elements in order.
take :: Eq a => Int -> Set a -> Set a
-- | O(n^2). Drop a given number of elements in order.
drop :: Eq a => Int -> Set a -> Set a
-- | O(n^2). Split a set at a particular index.
splitAt :: Eq a => Int -> Set a -> (Set a, Set a)
-- | O(n). Alias of fmap for backward compatibility with
-- Data.Set. Note that a WeakSet is a functor.
map :: (a -> b) -> Set a -> Set b
-- | O(n). Alias of fmap for backward compatibility with
-- Data.Set.
mapMonotonic :: (a -> b) -> Set a -> Set b
-- | O(n^2). Fold the elements in the set using the given
-- right-associative binary operator.
--
-- Note that an Eq constraint must be added.
foldr :: Eq a => (a -> b -> b) -> b -> Set a -> b
-- | O(n^2). Fold the elements in the set using the given
-- right-associative binary operator.
--
-- Note that an Eq constraint must be added.
foldl :: Eq b => (a -> b -> a) -> a -> Set b -> a
-- | Strict foldr.
foldr' :: (a -> b -> b) -> b -> Set a -> b
-- | Strict foldl.
foldl' :: (a -> b -> a) -> a -> Set b -> a
-- | O(n^2). Alias of cardinal.
length :: Eq a => Set a -> Int
-- | O(n). Return wether an element is in the Set.
elem :: Eq a => a -> Set a -> Bool
-- | O(n). Return the maximum value of a Set.
maximum :: Ord a => Set a -> a
-- | O(n). Return the minimum value of a Set.
minimum :: Ord a => Set a -> a
-- | O(n^2). Return the sum of values in a Set.
sum :: (Eq a, Num a) => Set a -> a
-- | O(n^2). Return the product of values in a Set.
product :: (Eq a, Num a) => Set a -> a
-- | O(n^2). Flatten a set of lists into a list.
--
-- Example : concat set [[1,2,3],[1,2,3],[1,2]] == [1,2,3,1,2]
concat :: Eq a => Set [a] -> [a]
-- | O(n). Flatten a set of sets into a set.
--
-- Example : concat set [set [1,2,3], set [1,2,3], set [1,2]] == set
-- [1,2,3]
concat2 :: Set (Set a) -> Set a
-- | O(n^2). Map a function over all the elements of a Set
-- and concatenate the resulting lists.
concatMap :: Eq b => (a -> [b]) -> Set a -> [b]
-- | O(n). Return the conjonction of a Set of booleans.
and :: Set Bool -> Bool
-- | O(n). Return the disjunction of a Set of booleans.
or :: Set Bool -> Bool
-- | O(n). Determines whether any element of the Set
-- satisfies the predicate.
any :: (a -> Bool) -> Set a -> Bool
-- | O(n). Determines whether all elements of the Set satisfy
-- the predicate.
all :: (a -> Bool) -> Set a -> Bool
-- | O(n). The largest element of a non-empty Set with
-- respect to the given comparison function.
maximumBy :: (a -> a -> Ordering) -> Set a -> a
-- | O(n). The smallest element of a non-empty Set with
-- respect to the given comparison function.
minimumBy :: (a -> a -> Ordering) -> Set a -> a
-- | O(n). Negation of elem.
notElem :: Eq a => a -> Set a -> Bool
-- | O(n). The find function takes a predicate and a
-- Set and returns an element of the Set matching the
-- predicate, or Nothing if there is no such element.
find :: (a -> Bool) -> Set a -> Maybe a
-- | O(n^2). Transform a Set 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]
-- | O(n^2). Alias of setToList for backward compatibility
-- with Data.Set.
toList :: Eq a => Set a -> [a]
-- | O(n^2). Remove duplicates in the set using your own equality
-- function.
nubSetBy :: (a -> a -> Bool) -> Set a -> [a]
-- | O(1). Set version of listToMaybe.
setToMaybe :: Set a -> Maybe a
-- | O(1). Set version of maybeToList.
maybeToSet :: Maybe a -> Set a
-- | O(n). Set version of catMaybes. Only keeps the Just values of a
-- set and extract them.
catMaybes :: Set (Maybe a) -> Set a
-- | O(n). Set version of mapMaybe. A map which throws out elements
-- which are mapped to nothing.
mapMaybe :: (a -> Maybe b) -> Set a -> Set b
-- | O(n). Map a function to a set, return a couple composed of the
-- set of left elements and the set of right elements.
mapEither :: (a -> Either b c) -> Set a -> (Set b, Set c)
-- | O(n). Map a function to a set and separate Left and Right
-- values.
catEither :: Set (Either a b) -> (Set a, Set b)
-- | Set is not a Traversable because of the Eq typeclass requirement.
traverseSet :: (Applicative f, Eq a) => (a -> f b) -> Set a -> f (Set b)
-- | Set is not a Traversable because of the Eq typeclass requirement.
sequenceSet :: (Applicative f, Eq (f a)) => Set (f a) -> f (Set a)
-- | O(1). Return an element of the set if it is not empty, throw an
-- error otherwise.
anElement :: Set a -> a
-- | Return the cartesian product of a set of set.
cartesianProductOfSet :: Set (Set a) -> Set (Set a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.WeakSet.Set a)
instance GHC.Base.Semigroup (Data.WeakSet.Set a)
instance GHC.Base.Monoid (Data.WeakSet.Set a)
instance GHC.Base.Functor Data.WeakSet.Set
instance GHC.Base.Applicative Data.WeakSet.Set
instance GHC.Base.Monad Data.WeakSet.Set
instance GHC.Show.Show a => GHC.Show.Show (Data.WeakSet.Set a)
-- | Non-clashing functions for Sets.
module Data.WeakSet.Safe
-- | O(1). The smart constructor of sets. This is the only way of
-- instantiating a Set with fromList.
--
-- We prefer the smart constructor set because its name does not
-- collide with other data structures.
set :: [a] -> Set a
-- | O(n^2). Transform a Set 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]
-- | O(n^2). Return a boolean indicating if a Set is included
-- in another one.
isIncludedIn :: Eq a => Set a -> Set a -> Bool
-- | O(n^2). Size of a set.
cardinal :: Eq a => Set a -> Int
-- | O(n). Return wether an element is in a set.
isIn :: Eq a => a -> Set a -> Bool
-- | Alias of intersection.
(|&|) :: Eq a => Set a -> Set a -> Set a
-- | Alias of union.
(|||) :: Set a -> Set a -> Set a
-- | Alias of cartesianProduct.
(|*|) :: Set a -> Set b -> Set (a, b)
-- | Alias of disjointUnion.
(|+|) :: Set a -> Set b -> Set (Either a b)
-- | Alias of difference.
(|-|) :: Eq a => Set a -> Set a -> Set a
-- | Returns the cartesian product of a set with itself n times.
(|^|) :: Eq a => Set a -> Int -> Set [a]
-- | O(n^2). Remove duplicates in the set using your own equality
-- function.
nubSetBy :: (a -> a -> Bool) -> Set a -> [a]
-- | O(1). Return an element of the set if it is not empty, throw an
-- error otherwise.
anElement :: Set a -> a
-- | Return the cartesian product of a set of set.
cartesianProductOfSet :: Set (Set a) -> Set (Set a)
-- | A WeakMap is a Data.Map which does not require the keys to
-- implement the Ord typeclass. It is a weak set of pairs (key,value).
--
-- The datatype only assumes its keys are equatable, it is therefore
-- slower to access data than the Data.Map datatype.
--
-- We use this datatype because most of the datatypes we care about are
-- not orderable.
--
-- Almost all Data.WeakMap functions are implemented so that you can
-- replace a Data.Map import such as
--
--
-- import Data.Map.Strict (Map)
-- import qualified Data.Map.Strict as Map
--
--
-- by a Data.WeakMap import such as
--
--
-- import Data.WeakMap (Map)
-- import qualified Data.WeakMap as Map
--
--
-- without breaking anything in your code.
--
-- The only functions for which this would fail are the functions
-- converting maps back into list (they require the Eq typeclass unlike
-- in Data.Map). size is one of them.
--
-- If a function really requires the Ord typeclass to even make sense,
-- then it is not defined in this package, you should use Data.Map.
--
-- Note that, just like in Data.Map, the implementation is generally
-- left-biased. Functions that take two maps as arguments and combine
-- them, such as union and intersection, prefer the entries in the first
-- argument to those in the second.
--
-- Functions with non colliding names are defined in Data.WeakMap.Safe.
-- Inline functions are written between pipes |.
--
-- This module is intended to be imported qualified, to avoid name
-- clashes with Prelude functions, except for functions in
-- Data.WeakSet.Map, e.g.
--
--
-- import Data.WeakMap (Map)
-- import qualified Data.WeakMap as Map
-- import Data.WeakMap.Safe
--
--
-- Unlike Data.Map, we defer the removing of duplicate keys to the
-- conversion back to a list.
--
-- Beware if the map is supposed to contain a lot of duplicate keys, you
-- should purge them yourself by transforming the map into a list and
-- back into a map. The time complexity is always given in function of
-- the number of pairs in the map including the duplicate pairs.
module Data.WeakMap
-- | An association list is a list of pairs (key,value).
type AssociationList k v = [(k, v)]
-- | A weak map is a weak 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 weakMap.
data Map k v
-- | O(1). The smart constructor of weak maps. This is the only way
-- of instantiating a Map.
--
-- 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.
weakMap :: AssociationList k v -> Map k v
-- | O(1). Construct a Map from a Set of pairs
-- (key,value).
weakMapFromSet :: Set (k, v) -> Map k v
-- | Alias of mempty for backward compatibility with Data.Map.
empty :: Map k a
-- | O(1). A map with a single pair (key,value).
singleton :: k -> a -> Map k a
-- | O(n). Build a map from a set of keys and a function which for
-- each key computes its value.
fromSet :: (k -> a) -> Set k -> Map k a
-- | O(1). Alias of weakMap for backward compatibility with
-- Data.Map.
fromList :: AssociationList k v -> Map k v
-- | O(n). Build a map from a list of key/value pairs with a
-- combining function.
fromListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Build a map from a list of key/value pairs with a
-- combining function.
fromListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
-- | Alias for backward compatibility.
fromAscList :: Eq k => [(k, a)] -> Map k a
-- | Alias for backward compatibility.
fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
-- | Alias for backward compatibility.
fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
-- | Alias for backward compatibility.
fromDistinctAscList :: [(k, a)] -> Map k a
-- | Alias for backward compatibility.
fromDescList :: Eq k => [(k, a)] -> Map k a
-- | Alias for backward compatibility.
fromDescListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
-- | Alias for backward compatibility.
fromDescListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
-- | Alias for backward compatibility.
fromDistinctDescList :: [(k, a)] -> Map k a
-- | O(1). Insert a new key and value in the map. If the key is
-- already present in the map, the associated value is replaced with the
-- supplied value. insert is equivalent to insertWith
-- const.
insert :: k -> a -> Map k a -> Map k a
-- | 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 -> Map k v -> Map 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 -> Map k a -> Map k a
-- | O(n). Combines insert operation with old value retrieval. The
-- expression (insertLookupWithKey f k x map) is a pair where
-- the first element is equal to (lookup k map) and the second
-- element equal to (insertWithKey f k x map).
insertLookupWithKey :: Eq k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
-- | O(1). Insert a new key and value if it is Just in the map. If
-- the key is already present in the map, the associated value is
-- replaced with the supplied value.
insertMaybe :: Eq k => k -> Maybe a -> Map k a -> Map k a
-- | O(n). Delete a key and its value from the map. When the key is
-- not a member of the map, the original map is returned.
delete :: Eq k => k -> Map k a -> Map 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 map, the
-- original map is returned.
adjust :: Eq k => (a -> a) -> k -> Map k a -> Map k a
-- | O(n). Adjust a value at a specific key. When the key is not a
-- member of the map, the original map is returned.
adjustWithKey :: Eq k => (k -> a -> a) -> k -> Map k a -> Map k a
-- | O(n). The expression (update f k map) updates the
-- value x at k (if it is in the map). If (f x) is Nothing, the element
-- is deleted. If it is (Just y), the key k is bound to the new value y.
update :: Eq k => (a -> Maybe a) -> k -> Map k a -> Map k a
-- | O(n). The expression (updateWithKey f k map) updates
-- the value x at k (if it is in the map). If (f k x) is Nothing, the
-- element is deleted. If it is (Just y), the key k is bound to the new
-- value y.
updateWithKey :: Eq k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
-- | O(n). Lookup and update. See also updateWithKey. The
-- function returns changed value, if it is updated. Returns the original
-- key value if the map entry is deleted.
updateLookupWithKey :: Eq k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
-- | O(n). The expression (alter f k map) alters the value x
-- at k, or absence thereof. alter can be used to insert, delete, or
-- update a value in a Map. In short : lookup k
-- (alter f k m) = f (lookup k m).
alter :: Eq k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
-- | O(n). The expression (alterF f k map) alters the value x
-- at k, or absence thereof. alterF can be used to inspect,
-- insert, delete, or update a value in a Map.
alterF :: (Functor f, Eq k) => (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
-- | O(n). Just like (|?|) but the order of argument is
-- reversed. For backward compatibility with Data.Map.
lookup :: Eq k => k -> Map k a -> Maybe a
-- | Alias for backward compatibility.
(!?) :: Eq k => Map k a -> k -> Maybe a
-- | O(n). Find the value at a key. Calls error when the element can
-- not be found.
--
-- Alias of (|!|) for backward compatibility purposes.
(!) :: Eq k => Map k a -> k -> a
-- | O(n). Lookup the value at a key in the map. If the map is not
-- defined on the given value returns Nothing, otherwise returns
-- Just the image.
--
-- This function is like lookup in Data.Map for function (beware:
-- the order of the argument are reversed).
(|?|) :: Eq k => Map k v -> k -> Maybe v
-- | O(n). Unsafe version of (|?|).
--
-- This function is like (!) in Data.Map, it is renamed to avoid
-- name collisions.
(|!|) :: Eq k => Map k v -> k -> v
-- | O(n). The expression (findWithDefault def k map)
-- returns the value at key k or returns default value def when the key
-- is not in the map.
findWithDefault :: Eq k => a -> k -> Map k a -> a
-- | O(n). Is the key a member of the map? See also
-- notMember.
member :: Eq k => k -> Map k a -> Bool
-- | O(n). Negation of member.
notMember :: Eq k => k -> Map k a -> Bool
-- | O(n^2). The number of elements in the map.
size :: Eq k => Map k a -> Int
-- | O(1). Return wether the map is empty.
null :: Map k a -> Bool
-- | O(n). The expression (union t1 t2) takes the
-- left-biased union of t1 and t2. It prefers t1 when duplicate keys are
-- encountered.
union :: Eq k => Map k a -> Map k a -> Map k a
-- | O(n). Union with a combining function.
unionWith :: Eq k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
-- | O(n). Union with a combining function.
--
--
-- let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
-- unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
--
unionWithKey :: Eq k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
-- | The union of a list of maps: (unions == foldl union empty).
unions :: Eq k => [Map k a] -> Map k a
-- | The union of a list of maps, with a combining operation:
-- (unionsWith f == foldl (unionWith f) empty).
unionsWith :: Eq k => (a -> a -> a) -> [Map k a] -> Map k a
-- | O(n*m). Difference of two maps. Return elements of the first
-- map not existing in the second map.
difference :: Eq k => Map k a -> Map k b -> Map k a
-- | See difference.
(\\) :: Eq k => Map k a -> Map k b -> Map k a
-- | O(n*m). Difference with a combining function. When two equal
-- keys are encountered, the combining function is applied to the values
-- of these keys. If it returns Nothing, the element is discarded (proper
-- set difference). If it returns (Just y), the element is updated with a
-- new value y
differenceWith :: Eq k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
-- | O(n*m). Difference with a combining function. When two equal
-- keys are encountered, the combining function is applied to the key and
-- both values. If it returns Nothing, the element is discarded (proper
-- set difference). If it returns (Just y), the element is updated with a
-- new value y.
differenceWithKey :: Eq k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
-- | O(n*m). Intersection of two maps. Return data in the first map
-- for the keys existing in both maps.
intersection :: Eq k => Map k a -> Map k b -> Map k a
-- | O(n*m). Intersection with a combining function.
intersectionWith :: Eq k => (a -> b -> c) -> Map k a -> Map k b -> Map k c
-- | O(n*m). Intersection with a combining function.
intersectionWithKey :: Eq k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
-- | Check whether the key sets of two maps are disjoint.
disjoint :: Eq k => Map k a -> Map k b -> Bool
-- | Compose two functions. If the two functions are not composable, strips
-- the functions until they can compose.
(|.|) :: Eq b => Map b c -> Map a b -> Map a c
-- | Relate the keys of one map to the values of the other, by using the
-- values of the former as keys for lookups in the latter.
compose :: Eq b => Map b c -> Map a b -> Map a c
-- | A universal combining function.
mergeWithKey :: Eq k => (k -> a -> b -> Maybe c) -> (Map k a -> Map k c) -> (Map k b -> Map k c) -> Map k a -> Map k b -> Map k c
-- | O(n). Map a function over all values in the map.
map :: (a -> b) -> Map k a -> Map k b
-- | O(n). Map a function over all values in the map.
mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
-- | Eq typeclass must be added.
--
-- It behaves much like a regular traverse except that the traversing
-- function also has access to the key associated with a value and the
-- values are forced before they are installed in the result map.
traverseWithKey :: (Applicative t, Eq k, Eq a) => (k -> a -> t b) -> Map k a -> t (Map k b)
-- | Eq typeclass must be added. Traverse keys/values and collect the Just
-- results.
traverseMaybeWithKey :: (Applicative f, Eq k, Eq a) => (k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
-- | O(n). The function mapAccum threads an accumulating
-- argument through the map.
mapAccum :: Eq k => (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
-- | O(n^2). The function mapAccumWithKey threads an
-- accumulating argument through the map.
mapAccumWithKey :: Eq k => (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
-- | O(n). Alias of mapAccumWithKey for backward
-- compatibility purposes. We don't implement it because order of pairs
-- should not matter.
mapAccumRWithKey :: Eq k => (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
-- | O(n). mapKeys f s is the map obtained by applying f to
-- each key of s.
mapKeys :: (k1 -> k2) -> Map k1 a -> Map k2 a
-- | O(n^2). mapKeysWith c f s is the map obtained by
-- applying f to each key of s.
--
-- The size of the result may be smaller if f maps two or more distinct
-- keys to the same new key. In this case the associated values will be
-- combined using c.
mapKeysWith :: (Eq k1, Eq k2) => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
-- | Alias of mapKeys defined for backward compatibility.
mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 a
-- | O(n^2). Fold the values in the map using the given
-- right-associative binary operator.
--
-- Note that an Eq constraint must be added.
foldr :: Eq k => (a -> b -> b) -> b -> Map k a -> b
-- | O(n^2). Fold the values in the map using the given
-- left-associative binary operator.
--
-- Note that an Eq constraint must be added.
foldl :: Eq k => (a -> b -> a) -> a -> Map k b -> a
-- | Fold with key.
foldrWithKey :: (Eq a, Eq k) => (k -> a -> b -> b) -> b -> Map k a -> b
-- | foldrWithKey from the left.
foldlWithKey :: (Eq k, Eq a) => (b -> k -> a -> b) -> b -> Map k a -> b
-- | Fold the keys and values in the map using the given monoid.
foldMapWithKey :: (Eq a, Eq k, Monoid m) => (k -> a -> m) -> Map k a -> m
-- | Strict foldr.
foldr' :: Eq k => (a -> b -> b) -> b -> Map k a -> b
-- | Strict foldl.
foldl' :: Eq k => (b -> a -> b) -> b -> Map k a -> b
-- | Strict foldrWithKey.
foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b
-- | Strict foldrWithKey.
foldlWithKey' :: (b -> k -> a -> b) -> b -> Map k a -> b
-- | O(n^2). Transform a function back into its underlying
-- association list.
mapToList :: Eq k => Map k v -> AssociationList k v
-- | O(n^2). Transform a function back into its underlying set of
-- pairs.
mapToSet :: Eq k => Map k v -> Set (k, v)
-- | O(n^2). Return all values of the map. Beware that an Eq
-- typeclass must be added.
elems :: Eq k => Map k a -> [a]
-- | O(n^2). Same as elems but returns a Set. Beware
-- that an Eq typeclass must be added.
elems' :: Eq k => Map k a -> Set a
-- | O(n^2). Alias of elems`.
values :: Eq k => Map k a -> Set a
-- | O(n^2). Alias of elems`.
image :: Eq k => Map k a -> Set a
-- | O(n^2). Return the keys of a map. Beware that an Eq typeclass
-- must be added.
keys :: Eq k => Map k v -> [k]
-- | O(n). Same as keys but returns a Set. No Eq
-- typeclass required.
keys' :: Map k v -> Set k
-- | O(n^2). Alias of keys`.
domain :: Map k a -> Set k
-- | Alias of mapToList for backward compatibility. Beware that an
-- Eq typeclass must be added.
assocs :: Eq k => Map k a -> [(k, a)]
-- | Alias of keys` for backward compatibility.
keysSet :: Map k a -> Set k
-- | O(n^2). Return the set of values of a map.
elemsSet :: Eq k => Map k a -> Set a
-- | O(n^2). Alias of mapToList for backward compatibility.
-- Beware that an Eq typeclass must be added.
toList :: Eq k => Map k a -> [(k, a)]
-- | Alias of toList for backward compatibility.
toAscList :: Eq k => Map k a -> [(k, a)]
-- | Alias of toList for backward compatibility.
toDescList :: Eq k => Map k a -> [(k, a)]
-- | O(n). Filter all values that satisfy the predicate.
filter :: (a -> Bool) -> Map k a -> Map k a
-- | O(n). Filter all keys/values that satisfy the predicate.
filterWithKey :: (k -> a -> Bool) -> Map k a -> Map k a
-- | O(n*m). Restrict a Map to only those keys found in a
-- Set.
restrictKeys :: Eq k => Map k a -> Set k -> Map k a
-- | O(n*m). Remove all keys in a Set from a Map.
withoutKeys :: Eq k => Map k a -> Set k -> Map k a
-- | O(n). Partition the map according to a predicate. The first map
-- contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate.
partition :: (a -> Bool) -> Map k a -> (Map k a, Map k a)
-- | O(n). Partition the map according to a predicate. The first map
-- contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate.
partitionWithKey :: (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
-- | O(n). Map values and collect the Just results.
mapMaybe :: (a -> Maybe b) -> Map k a -> Map k b
-- | O(n). Map keys/values and collect the Just results.
mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b
-- | O(n). Map values and separate the Left and Right results.
mapEither :: (a -> Either b c) -> Map k a -> (Map k b, Map k c)
-- | O(n). Map keys/values and separate the Left and Right results.
mapEitherWithKey :: (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
-- | O(max(m^2,n^2)). This function is defined as (isSubmapOf =
-- isSubmapOfBy (==)).
isSubmapOf :: (Eq k, Eq a) => Map k a -> Map k a -> Bool
-- | O(max(m^2,n^2)). Returns True if the keys of the first map is
-- included in the keys of the second and the predicate evaluation at
-- their value is True.
isSubmapOfBy :: Eq k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
-- | O(max(m^2,n^2)). This function is defined as
-- (isProperSubmapOf = isProperSubmapOfBy (==)).
isProperSubmapOf :: (Eq k, Eq a) => Map k a -> Map k a -> Bool
-- | O(max(m^2,n^2)). Returns True if the keys of the first map is
-- strictly included in the keys of the second and the predicate
-- evaluation at their value is True.
isProperSubmapOfBy :: Eq k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
-- | O(n^2). Lookup the index of a key, which is its zero-based
-- index in the sequence. The index is a number from 0 up to, but not
-- including, the size of the map.
lookupIndex :: Eq k => k -> Map k a -> Maybe Int
-- | O(n^2). Return the index of a key, which is its zero-based
-- index in the sequence. The index is a number from 0 up to, but not
-- including, the size of the map. Calls error when the key is not a
-- member of the map.
findIndex :: Eq k => k -> Map k a -> Int
-- | O(n^2). Retrieve an element by its index, i.e. by its
-- zero-based index in the sequence. If the index is out of range (less
-- than zero, greater or equal to size of the map), error is called.
elemAt :: Eq k => Int -> Map k a -> (k, a)
-- | O(n^2). Update the element at index. Calls error when an
-- invalid index is used.
updateAt :: Eq k => (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
-- | O(n^2). Delete the element at index, i.e. by its zero-based
-- index in the sequence. If the index is out of range (less than zero,
-- greater or equal to size of the map), error is called.
deleteAt :: Eq k => Int -> Map k a -> Map k a
-- | O(n^2). Take a given number of pairs to create a new map.
take :: Eq k => Int -> Map k a -> Map k a
-- | O(n^2). Drop a given number of pairs to create a new map.
drop :: Eq k => Int -> Map k a -> Map k a
-- | O(n^2). Split a map at a particular index.
splitAt :: Eq k => Int -> Map k a -> (Map k a, Map k a)
-- | O(n). Return the identity function associated to a Set.
idFromSet :: Set a -> Map a a
-- | O(n). Memorize a Haskell function on a given finite domain.
-- Alias of fromSet.
memorizeFunction :: (k -> v) -> Set k -> Map k v
-- | O(n^2). Try to construct an inverse map.
inverse :: (Eq k, Eq v) => Map k v -> Maybe (Map v k)
-- | O(n). Return a pseudo inverse g of a Map f
-- such that f |.| g |.| f == f.
pseudoInverse :: Map k v -> Map v k
-- | Return all Functions from a domain to a codomain.
enumerateMaps :: (Eq a, Eq b) => Set a -> Set b -> Set (Map a b)
instance (GHC.Classes.Eq k, GHC.Classes.Eq v) => GHC.Classes.Eq (Data.WeakMap.Map k v)
instance (GHC.Show.Show k, GHC.Show.Show v) => GHC.Show.Show (Data.WeakMap.Map k v)
instance GHC.Base.Semigroup (Data.WeakMap.Map k v)
instance GHC.Base.Monoid (Data.WeakMap.Map k v)
instance GHC.Base.Functor (Data.WeakMap.Map k)
-- | Non-clashing functions for Maps.
module Data.WeakMap.Safe
-- | O(1). The smart constructor of weak maps. This is the only way
-- of instantiating a Map.
--
-- 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.
weakMap :: AssociationList k v -> Map k v
-- | O(1). Construct a Map from a Set of pairs
-- (key,value).
weakMapFromSet :: Set (k, v) -> Map k v
-- | O(n). Lookup the value at a key in the map. If the map is not
-- defined on the given value returns Nothing, otherwise returns
-- Just the image.
--
-- This function is like lookup in Data.Map for function (beware:
-- the order of the argument are reversed).
(|?|) :: Eq k => Map k v -> k -> Maybe v
-- | O(n). Unsafe version of (|?|).
--
-- This function is like (!) in Data.Map, it is renamed to avoid
-- name collisions.
(|!|) :: Eq k => Map k v -> k -> v
-- | Compose two functions. If the two functions are not composable, strips
-- the functions until they can compose.
(|.|) :: Eq b => Map b c -> Map a b -> Map a c
-- | O(n). Return the identity function associated to a Set.
idFromSet :: Set a -> Map a a
-- | O(n). Memorize a Haskell function on a given finite domain.
-- Alias of fromSet.
memorizeFunction :: (k -> v) -> Set k -> Map k v
-- | O(n^2). Same as elems but returns a Set. Beware
-- that an Eq typeclass must be added.
elems' :: Eq k => Map k a -> Set a
-- | O(n). Same as keys but returns a Set. No Eq
-- typeclass required.
keys' :: Map k v -> Set k
-- | O(n^2). Alias of keys`.
domain :: Map k a -> Set k
-- | O(n^2). Alias of elems`.
image :: Eq k => Map k a -> Set a
-- | O(n^2). Try to construct an inverse map.
inverse :: (Eq k, Eq v) => Map k v -> Maybe (Map v k)
-- | O(n). Return a pseudo inverse g of a Map f
-- such that f |.| g |.| f == f.
pseudoInverse :: Map k v -> Map v k
-- | Return all Functions from a domain to a codomain.
enumerateMaps :: (Eq a, Eq b) => Set a -> Set b -> Set (Map a b)
-- | 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 pure set functions are suffixed with
-- the letter P for pure to avoid name collision.
module Math.PureSet
-- | A PureSet is a Set of other pure sets.
data PureSet
PureSet :: Set PureSet -> PureSet
-- | Construct a PureSet 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
-- | Prettify 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.PureSet.PureSet
instance GHC.Show.Show Math.PureSet.PureSet