Copyright | Guillaume Sabbagh 2022 |
---|---|
License | LGPL-3.0-or-later |
Maintainer | guillaumesabbagh@protonmail.com |
Stability | experimental |
Portability | portable |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
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.
Synopsis
- data Set a
- empty :: Set a
- singleton :: a -> Set a
- set :: [a] -> Set a
- fromList :: [a] -> Set a
- fromAscList :: [a] -> Set a
- fromDescList :: [a] -> Set a
- fromDistinctAscList :: [a] -> Set a
- fromDistinctDescList :: [a] -> Set a
- powerSet :: Set a -> Set (Set a)
- (|&|) :: Eq a => Set a -> Set a -> Set a
- (|||) :: Set a -> Set a -> Set a
- (|*|) :: Set a -> Set b -> Set (a, b)
- (|+|) :: Set a -> Set b -> Set (Either a b)
- (|-|) :: Eq a => Set a -> Set a -> Set a
- (|^|) :: Eq a => Set a -> Int -> Set [a]
- insert :: a -> Set a -> Set a
- delete :: Eq a => a -> Set a -> Set a
- alterF :: (Eq a, Functor f) => (Bool -> f Bool) -> a -> Set a -> f (Set a)
- isIn :: Eq a => a -> Set a -> Bool
- member :: Eq a => a -> Set a -> Bool
- notMember :: Eq a => a -> Set a -> Bool
- cardinal :: Eq a => Set a -> Int
- size :: Eq a => Set a -> Int
- isIncludedIn :: Eq a => Set a -> Set a -> Bool
- isSubsetOf :: Eq a => Set a -> Set a -> Bool
- isProperSubsetOf :: Eq a => Set a -> Set a -> Bool
- disjoint :: Eq a => Set a -> Set a -> Bool
- union :: Set a -> Set a -> Set a
- unions :: Foldable f => f (Set a) -> Set a
- difference :: Eq a => Set a -> Set a -> Set a
- (\\) :: Eq a => Set a -> Set a -> Set a
- intersection :: Eq a => Set a -> Set a -> Set a
- cartesianProduct :: Set a -> Set b -> Set (a, b)
- disjointUnion :: Set a -> Set b -> Set (Either a b)
- filter :: (a -> Bool) -> Set a -> Set a
- partition :: (a -> Bool) -> Set a -> (Set a, Set a)
- lookupIndex :: Eq a => a -> Set a -> Maybe Int
- findIndex :: Eq a => a -> Set a -> Int
- elemAt :: Eq a => Int -> Set a -> a
- deleteAt :: Eq a => Int -> Set a -> Set a
- take :: Eq a => Int -> Set a -> Set a
- drop :: Eq a => Int -> Set a -> Set a
- splitAt :: Eq a => Int -> Set a -> (Set a, Set a)
- map :: (a -> b) -> Set a -> Set b
- mapMonotonic :: (a -> b) -> Set a -> Set b
- foldr' :: (a -> b -> b) -> b -> Set a -> b
- foldl' :: (a -> b -> a) -> a -> Set b -> a
- setToList :: Eq a => Set a -> [a]
- toList :: Eq a => Set a -> [a]
- nubSetBy :: (a -> a -> Bool) -> Set a -> [a]
- setToMaybe :: Set a -> Maybe a
- maybeToSet :: Maybe a -> Set a
- catMaybes :: Set (Maybe a) -> Set a
- mapMaybe :: (a -> Maybe b) -> Set a -> Set b
- mapEither :: (a -> Either b c) -> Set a -> (Set b, Set c)
- catEither :: Set (Either a b) -> (Set a, Set b)
- traverseSet :: (Applicative f, Eq a) => (a -> f b) -> Set a -> f (Set b)
- sequenceSet :: (Applicative f, Eq (f a)) => Set (f a) -> f (Set a)
Documentation
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.
Instances
Monad Set Source # | |
Functor Set Source # | |
Applicative Set Source # | |
Foldable Set Source # | |
Defined in Data.WeakSet fold :: Monoid m => Set m -> m foldMap :: Monoid m => (a -> m) -> Set a -> m foldMap' :: Monoid m => (a -> m) -> Set a -> m foldr :: (a -> b -> b) -> b -> Set a -> b foldr' :: (a -> b -> b) -> b -> Set a -> b foldl :: (b -> a -> b) -> b -> Set a -> b foldl' :: (b -> a -> b) -> b -> Set a -> b foldr1 :: (a -> a -> a) -> Set a -> a foldl1 :: (a -> a -> a) -> Set a -> a elem :: Eq a => a -> Set a -> Bool maximum :: Ord a => Set a -> a | |
Eq a => Eq (Set a) Source # | |
Show a => Show (Set a) Source # | |
Semigroup (Set a) Source # | |
Monoid (Set a) Source # | |
Construction
fromList :: [a] -> Set a Source #
O(1). This smart constructor is provided to allow backward compatibility with Data.Set.
fromAscList :: [a] -> Set a Source #
O(1). Defined for backward compatibility with Data.Set.
fromDescList :: [a] -> Set a Source #
O(1). Defined for backward compatibility with Data.Set.
fromDistinctAscList :: [a] -> Set a Source #
O(1). Defined for backward compatibility with Data.Set.
fromDistinctDescList :: [a] -> Set a Source #
O(1). Defined for backward compatibility with Data.Set.
powerSet :: Set a -> Set (Set a) Source #
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])])
Operators
(|^|) :: Eq a => Set a -> Int -> Set [a] Source #
Returns the cartesian product of a set with itself n times.
Insertion
insert :: a -> Set a -> Set a Source #
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.
Deletion
Generalized insertion/deletion
alterF :: (Eq a, Functor f) => (Bool -> f Bool) -> a -> Set a -> f (Set a) Source #
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.
member :: Eq a => a -> Set a -> Bool Source #
O(n). Alias of isIn
. Defined for backward compatibility with Data.Set.
notMember :: Eq a => a -> Set a -> Bool Source #
O(n). Negation of member
. Defined for backward compatibility with Data.Set.
isIncludedIn :: Eq a => Set a -> Set a -> Bool Source #
O(n^2). Return a boolean indicating if a Set
is included in another one.
isSubsetOf :: Eq a => Set a -> Set a -> Bool Source #
O(n^2). Return a boolean indicating if a Set
is included in another one.
isProperSubsetOf :: Eq a => Set a -> Set a -> Bool Source #
O(n^2). x is a proper subset of y if x is included in y and x is different from y.
disjoint :: Eq a => Set a -> Set a -> Bool Source #
O(n^2). Check whether two sets are disjoint (i.e., their intersection is empty).
Combine
union :: Set a -> Set a -> Set a Source #
O(n). The union of two sets, preferring the first set when equal elements are encountered.
intersection :: Eq a => Set a -> Set a -> Set a Source #
O(m*n). Return the intersection of two sets. Elements of the result come from the first set.
cartesianProduct :: Set a -> Set b -> Set (a, b) Source #
O(m*n). Return the cartesian product of two sets.
disjointUnion :: Set a -> Set b -> Set (Either a b) Source #
O(n). Return the disjoint union of two sets.
Filter
filter :: (a -> Bool) -> Set a -> Set a Source #
O(n). Filter all elements that satisfy the predicate.
partition :: (a -> Bool) -> Set a -> (Set a, Set a) Source #
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
.
Indexed
lookupIndex :: Eq a => a -> Set a -> Maybe Int Source #
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.
findIndex :: Eq a => a -> Set a -> Int Source #
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.
elemAt :: Eq a => Int -> Set a -> a Source #
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.
deleteAt :: Eq a => Int -> Set a -> Set a Source #
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.
splitAt :: Eq a => Int -> Set a -> (Set a, Set a) Source #
O(n^2). Split a set at a particular index.
Map
map :: (a -> b) -> Set a -> Set b Source #
O(n). Alias of fmap
for backward compatibility with Data.Set. Note that a WeakSet is a functor.
mapMonotonic :: (a -> b) -> Set a -> Set b Source #
O(n). Alias of fmap
for backward compatibility with Data.Set.
Folds
Strict folds
Conversion
List
setToList :: Eq a => Set a -> [a] Source #
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.
toList :: Eq a => Set a -> [a] Source #
O(n^2). Alias of setToList
for backward compatibility with Data.Set.
nubSetBy :: (a -> a -> Bool) -> Set a -> [a] Source #
O(n^2). Remove duplicates in the set using your own equality function.
Maybe interaction
setToMaybe :: Set a -> Maybe a Source #
O(1). Set version of listToMaybe.
maybeToSet :: Maybe a -> Set a Source #
O(1). Set version of maybeToList.
catMaybes :: Set (Maybe a) -> Set a Source #
O(n). Set version of catMaybes. Only keeps the Just values of a set and extract them.
mapMaybe :: (a -> Maybe b) -> Set a -> Set b Source #
O(n). Set version of mapMaybe. A map which throws out elements which are mapped to nothing.
Either interaction
mapEither :: (a -> Either b c) -> Set a -> (Set b, Set c) Source #
O(n). Map a function to a set, return a couple composed of the set of left elements and the set of right elements.
catEither :: Set (Either a b) -> (Set a, Set b) Source #
O(n). Map a function to a set and separate Left and Right values.
Others
traverseSet :: (Applicative f, Eq a) => (a -> f b) -> Set a -> f (Set b) Source #
Set is not a Traversable because of the Eq typeclass requirement.
sequenceSet :: (Applicative f, Eq (f a)) => Set (f a) -> f (Set a) Source #
Set is not a Traversable because of the Eq typeclass requirement.