Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

## Synopsis

- data MultiSet a
- type Occur = Int
- null :: MultiSet a -> Bool
- size :: MultiSet a -> Occur
- distinctSize :: MultiSet a -> Occur
- member :: Ord a => a -> MultiSet a -> Bool
- notMember :: Ord a => a -> MultiSet a -> Bool
- occur :: Ord a => a -> MultiSet a -> Occur
- isSubsetOf :: Ord a => MultiSet a -> MultiSet a -> Bool
- isProperSubsetOf :: Ord a => MultiSet a -> MultiSet a -> Bool
- empty :: MultiSet a
- singleton :: a -> MultiSet a
- insert :: Ord a => a -> MultiSet a -> MultiSet a
- insertMany :: Ord a => a -> Occur -> MultiSet a -> MultiSet a
- delete :: Ord a => a -> MultiSet a -> MultiSet a
- deleteMany :: Ord a => a -> Occur -> MultiSet a -> MultiSet a
- deleteAll :: Ord a => a -> MultiSet a -> MultiSet a
- union :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
- unions :: Ord a => [MultiSet a] -> MultiSet a
- maxUnion :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
- difference :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
- intersection :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
- filter :: (a -> Bool) -> MultiSet a -> MultiSet a
- partition :: (a -> Bool) -> MultiSet a -> (MultiSet a, MultiSet a)
- split :: Ord a => a -> MultiSet a -> (MultiSet a, MultiSet a)
- splitOccur :: Ord a => a -> MultiSet a -> (MultiSet a, Occur, MultiSet a)
- map :: Ord b => (a -> b) -> MultiSet a -> MultiSet b
- mapMonotonic :: (a -> b) -> MultiSet a -> MultiSet b
- mapMaybe :: Ord b => (a -> Maybe b) -> MultiSet a -> MultiSet b
- mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MultiSet a -> (MultiSet b, MultiSet c)
- concatMap :: Ord b => (a -> [b]) -> MultiSet a -> MultiSet b
- unionsMap :: Ord b => (a -> MultiSet b) -> MultiSet a -> MultiSet b
- bind :: Ord b => MultiSet a -> (a -> MultiSet b) -> MultiSet b
- join :: Ord a => MultiSet (MultiSet a) -> MultiSet a
- fold :: (a -> b -> b) -> b -> MultiSet a -> b
- foldOccur :: (a -> Occur -> b -> b) -> b -> MultiSet a -> b
- findMin :: MultiSet a -> a
- findMax :: MultiSet a -> a
- deleteMin :: MultiSet a -> MultiSet a
- deleteMax :: MultiSet a -> MultiSet a
- deleteMinAll :: MultiSet a -> MultiSet a
- deleteMaxAll :: MultiSet a -> MultiSet a
- deleteFindMin :: MultiSet a -> (a, MultiSet a)
- deleteFindMax :: MultiSet a -> (a, MultiSet a)
- maxView :: MultiSet a -> Maybe (a, MultiSet a)
- minView :: MultiSet a -> Maybe (a, MultiSet a)
- elems :: MultiSet a -> [a]
- distinctElems :: MultiSet a -> [a]
- toList :: MultiSet a -> [a]
- toAscList :: MultiSet a -> [a]
- toOccurList :: MultiSet a -> [(a, Occur)]
- toAscOccurList :: MultiSet a -> [(a, Occur)]
- fromList :: Ord a => [a] -> MultiSet a
- fromAscList :: Eq a => [a] -> MultiSet a
- fromDistinctAscList :: [a] -> MultiSet a
- fromOccurList :: Ord a => [(a, Occur)] -> MultiSet a
- fromAscOccurList :: Eq a => [(a, Occur)] -> MultiSet a
- fromDistinctAscOccurList :: [(a, Occur)] -> MultiSet a
- toMap :: MultiSet a -> Map a Occur
- fromMap :: Map a Occur -> MultiSet a
- fromOccurMap :: Map a Occur -> MultiSet a
- toSet :: MultiSet a -> Set a
- fromSet :: Set a -> MultiSet a

# MultiSet

A multiset of values `a`

.
The same value can occur multiple times.

## Instances

Foldable MultiSet | |

Defined in Data.MultiSet fold :: Monoid m => MultiSet m -> m # foldMap :: Monoid m => (a -> m) -> MultiSet a -> m # foldr :: (a -> b -> b) -> b -> MultiSet a -> b # foldr' :: (a -> b -> b) -> b -> MultiSet a -> b # foldl :: (b -> a -> b) -> b -> MultiSet a -> b # foldl' :: (b -> a -> b) -> b -> MultiSet a -> b # foldr1 :: (a -> a -> a) -> MultiSet a -> a # foldl1 :: (a -> a -> a) -> MultiSet a -> a # elem :: Eq a => a -> MultiSet a -> Bool # maximum :: Ord a => MultiSet a -> a # minimum :: Ord a => MultiSet a -> a # | |

Eq a => Eq (MultiSet a) | |

(Data a, Ord a) => Data (MultiSet a) | |

Defined in Data.MultiSet gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> MultiSet a -> c (MultiSet a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (MultiSet a) # toConstr :: MultiSet a -> Constr # dataTypeOf :: MultiSet a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (MultiSet a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (MultiSet a)) # gmapT :: (forall b. Data b => b -> b) -> MultiSet a -> MultiSet a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> MultiSet a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> MultiSet a -> r # gmapQ :: (forall d. Data d => d -> u) -> MultiSet a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> MultiSet a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> MultiSet a -> m (MultiSet a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> MultiSet a -> m (MultiSet a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> MultiSet a -> m (MultiSet a) # | |

Ord a => Ord (MultiSet a) | |

(Read a, Ord a) => Read (MultiSet a) | |

Show a => Show (MultiSet a) | |

Ord a => Semigroup (MultiSet a) | |

Ord a => Monoid (MultiSet a) | |

NFData a => NFData (MultiSet a) | |

Defined in Data.MultiSet |

distinctSize :: MultiSet a -> Occur #

*O(1)*. The number of distinct elements in the multiset.

occur :: Ord a => a -> MultiSet a -> Occur #

*O(log n)*. The number of occurrences of an element in a multiset.

isSubsetOf :: Ord a => MultiSet a -> MultiSet a -> Bool #

*O(n+m)*. Is this a subset?
`(s1 `isSubsetOf` s2)`

tells whether `s1`

is a subset of `s2`

.

isProperSubsetOf :: Ord a => MultiSet a -> MultiSet a -> Bool #

*O(n+m)*. Is this a proper subset? (ie. a subset but not equal).

insertMany :: Ord a => a -> Occur -> MultiSet a -> MultiSet a #

*O(log n)*. Insert an element in a multiset a given number of times.

Negative numbers remove occurrences of the given element.

delete :: Ord a => a -> MultiSet a -> MultiSet a #

*O(log n)*. Delete a single element from a multiset.

deleteMany :: Ord a => a -> Occur -> MultiSet a -> MultiSet a #

*O(log n)*. Delete an element from a multiset a given number of times.

Negative numbers add occurrences of the given element.

deleteAll :: Ord a => a -> MultiSet a -> MultiSet a #

*O(log n)*. Delete all occurrences of an element from a multiset.

union :: Ord a => MultiSet a -> MultiSet a -> MultiSet a #

*O(n+m)*. The union of two multisets. The union adds the occurrences together.

The implementation uses the efficient *hedge-union* algorithm.
Hedge-union is more efficient on (bigset `union`

smallset).

maxUnion :: Ord a => MultiSet a -> MultiSet a -> MultiSet a #

*O(n+m)*. The union of two multisets.
The number of occurrences of each element in the union is
the maximum of the number of occurrences in the arguments (instead of the sum).

The implementation uses the efficient *hedge-union* algorithm.
Hedge-union is more efficient on (bigset `union`

smallset).

difference :: Ord a => MultiSet a -> MultiSet a -> MultiSet a #

*O(n+m)*. Difference of two multisets.
The implementation uses an efficient *hedge* algorithm comparable with *hedge-union*.

intersection :: Ord a => MultiSet a -> MultiSet a -> MultiSet a #

*O(n+m)*. The intersection of two multisets.
Elements of the result come from the first multiset, so for example

import qualified Data.MultiSet as MS data AB = A | B deriving Show instance Ord AB where compare _ _ = EQ instance Eq AB where _ == _ = True main = print (MS.singleton A `MS.intersection` MS.singleton B, MS.singleton B `MS.intersection` MS.singleton A)

prints `(fromList [A],fromList [B])`

.

filter :: (a -> Bool) -> MultiSet a -> MultiSet a #

*O(n)*. Filter all elements that satisfy the predicate.

partition :: (a -> Bool) -> MultiSet a -> (MultiSet a, MultiSet a) #

*O(n)*. Partition the multiset into two multisets, one with all elements that satisfy
the predicate and one with all elements that don't satisfy the predicate.
See also `split`

.

split :: Ord a => a -> MultiSet a -> (MultiSet a, MultiSet a) #

*O(log n)*. The expression (

) is a pair `split`

x set`(set1,set2)`

where all elements in `set1`

are lower than `x`

and all elements in
`set2`

larger than `x`

. `x`

is not found in neither `set1`

nor `set2`

.

splitOccur :: Ord a => a -> MultiSet a -> (MultiSet a, Occur, MultiSet a) #

*O(log n)*. Performs a `split`

but also returns the number of
occurrences of the pivot element in the original set.

map :: Ord b => (a -> b) -> MultiSet a -> MultiSet b #

*O(n*log n)*.

is the multiset obtained by applying `map`

f s`f`

to each element of `s`

.

mapMonotonic :: (a -> b) -> MultiSet a -> MultiSet b #

*O(n)*. The

, but works only when `mapMonotonic`

f s == `map`

f s`f`

is strictly monotonic.
*The precondition is not checked.*
Semi-formally, we have:

and [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapMonotonic f s == map f s where ls = toList s

mapMaybe :: Ord b => (a -> Maybe b) -> MultiSet a -> MultiSet b #

*O(n)*. Map and collect the `Just`

results.

concatMap :: Ord b => (a -> [b]) -> MultiSet a -> MultiSet b #

*O(n)*. Apply a function to each element, and take the union of the results

unionsMap :: Ord b => (a -> MultiSet b) -> MultiSet a -> MultiSet b #

*O(n)*. Apply a function to each element, and take the union of the results

bind :: Ord b => MultiSet a -> (a -> MultiSet b) -> MultiSet b #

*O(n)*. The monad bind operation, (>>=), for multisets.

fold :: (a -> b -> b) -> b -> MultiSet a -> b #

*O(t)*. Fold over the elements of a multiset in an unspecified order.

foldOccur :: (a -> Occur -> b -> b) -> b -> MultiSet a -> b #

*O(n)*. Fold over the elements of a multiset with their occurrences.

deleteMinAll :: MultiSet a -> MultiSet a #

*O(log n)*. Delete all occurrences of the minimal element.

deleteMaxAll :: MultiSet a -> MultiSet a #

*O(log n)*. Delete all occurrences of the maximal element.

deleteFindMin :: MultiSet a -> (a, MultiSet a) #

*O(log n)*. Delete and find the minimal element.

deleteFindMin set = (findMin set, deleteMin set)

deleteFindMax :: MultiSet a -> (a, MultiSet a) #

*O(log n)*. Delete and find the maximal element.

deleteFindMax set = (findMax set, deleteMax set)

maxView :: MultiSet a -> Maybe (a, MultiSet a) #

*O(log n)*. Retrieves the maximal element of the multiset,
and the set with that element removed.
Returns `Nothing`

when passed an empty multiset.

Examples:

`>>>`

Just ('c',fromOccurList [('a',2),('b',1)])`maxView $ fromList ['a', 'a', 'b', 'c']`

minView :: MultiSet a -> Maybe (a, MultiSet a) #

*O(log n)*. Retrieves the minimal element of the multiset,
and the set with that element removed.
Returns `Nothing`

when passed an empty multiset.

Examples:

`>>>`

Just ('a',fromOccurList [('a',1),('b',1),('c',1)])`minView $ fromList ['a', 'a', 'b', 'c']`

distinctElems :: MultiSet a -> [a] #

*O(n)*. The distinct elements of a multiset, each element occurs only once in the list.

distinctElems = map fst . toOccurList

toOccurList :: MultiSet a -> [(a, Occur)] #

*O(n)*. Convert the multiset to a list of element/occurrence pairs.

toAscOccurList :: MultiSet a -> [(a, Occur)] #

*O(n)*. Convert the multiset to an ascending list of element/occurrence pairs.

fromAscList :: Eq a => [a] -> MultiSet a #

*O(t)*. Build a multiset from an ascending list in linear time.
*The precondition (input list is ascending) is not checked.*

fromDistinctAscList :: [a] -> MultiSet a #

*O(n)*. Build a multiset from an ascending list of distinct elements in linear time.
*The precondition (input list is strictly ascending) is not checked.*

fromOccurList :: Ord a => [(a, Occur)] -> MultiSet a #

*O(n*log n)*. Create a multiset from a list of element/occurrence pairs.
Occurrences must be positive.
*The precondition (all occurrences > 0) is not checked.*

fromAscOccurList :: Eq a => [(a, Occur)] -> MultiSet a #

*O(n)*. Build a multiset from an ascending list of element/occurrence pairs in linear time.
Occurrences must be positive.
*The precondition (input list is ascending, all occurrences > 0) is not checked.*

fromDistinctAscOccurList :: [(a, Occur)] -> MultiSet a #

*O(n)*. Build a multiset from an ascending list of elements/occurrence pairs where each elements appears only once.
Occurrences must be positive.
*The precondition (input list is strictly ascending, all occurrences > 0) is not checked.*

toMap :: MultiSet a -> Map a Occur #

*O(1)*. Convert a multiset to a `Map`

from elements to number of occurrences.

fromMap :: Map a Occur -> MultiSet a #

*O(n)*. Convert a `Map`

from elements to occurrences to a multiset.

fromOccurMap :: Map a Occur -> MultiSet a #