Safe Haskell	None
Language	GHC2021

Data.Multiset

Synopsis

newtype Multiset a = Multiset {
- getMultiset :: Map a Int
}
emptyMS :: Multiset a
singletonMS :: a -> Multiset a
replicateMS :: Int -> a -> Multiset a
fromListMS :: Ord a => [a] -> Multiset a
fromAscListMS :: Eq a => [a] -> Multiset a
fromDistinctAscListMS :: [a] -> Multiset a
fromDescListMS :: Eq a => [a] -> Multiset a
fromDistinctDescListMS :: [a] -> Multiset a
toListMS :: Multiset a -> [a]
toAscListMS :: Multiset a -> [a]
toDescListMS :: Multiset a -> [a]
insertMS :: Ord a => a -> Multiset a -> Multiset a
deleteMS :: Ord a => a -> Multiset a -> Multiset a
deleteAllMS :: Ord a => a -> Multiset a -> Multiset a
memberMS :: Ord a => a -> Multiset a -> Bool
notMemberMS :: Ord a => a -> Multiset a -> Bool
countMS :: Ord a => a -> Multiset a -> Int
lookupLTMS :: Ord a => a -> Multiset a -> Maybe a
lookupGTMS :: Ord a => a -> Multiset a -> Maybe a
lookupLEMS :: Ord a => a -> Multiset a -> Maybe a
lookupGEMS :: Ord a => a -> Multiset a -> Maybe a
nullMS :: Multiset a -> Bool
sizeMS :: Multiset a -> Int
distinctSizeMS :: Multiset a -> Int
findMinMS :: Multiset a -> a
findMaxMS :: Multiset a -> a
deleteMinMS :: Multiset a -> Multiset a
deleteMaxMS :: Multiset a -> Multiset a
deleteFindMinMS :: Ord a => Multiset a -> (a, Multiset a)
deleteFindMaxMS :: Ord a => Multiset a -> (a, Multiset a)
minViewMS :: Ord a => Multiset a -> Maybe (a, Multiset a)
maxViewMS :: Ord a => Multiset a -> Maybe (a, Multiset a)
splitMS :: Ord a => a -> Multiset a -> (Multiset a, Multiset a)
splitLookupMS :: Ord a => a -> Multiset a -> (Multiset a, [a], Multiset a)

Documentation

newtype Multiset a Source #

Constructors

Multiset
Fields getMultiset :: Map a Int

Instances

Instances details

Ord a => IsList (Multiset a) Source #

Instance details

Defined in Data.Multiset

Associated Types

type Item (Multiset a)
Instance details Defined in Data.Multiset type Item (Multiset a) = a

Methods

fromList :: [Item (Multiset a)] -> Multiset a #

fromListN :: Int -> [Item (Multiset a)] -> Multiset a #

toList :: Multiset a -> [Item (Multiset a)] #

(Show a, Ord a) => Show (Multiset a) Source #

Instance details

Defined in Data.Multiset

Methods

showsPrec :: Int -> Multiset a -> ShowS #

show :: Multiset a -> String #

showList :: [Multiset a] -> ShowS #

Eq a => Eq (Multiset a) Source #

Instance details

Defined in Data.Multiset

Methods

(==) :: Multiset a -> Multiset a -> Bool #

(/=) :: Multiset a -> Multiset a -> Bool #

type Item (Multiset a) Source #

Instance details

Defined in Data.Multiset

type Item (Multiset a) = a

emptyMS :: Multiset a Source #

singletonMS :: a -> Multiset a Source #

replicateMS :: Int -> a -> Multiset a Source #

O(1)

>>> replicateMS 3 1
[1,1,1]
>>> nullMS $ replicateMS 0 1
True
>>> nullMS $ replicateMS (-1) 1
True

fromListMS :: Ord a => [a] -> Multiset a Source #

O(n log n)

>>> fromListMS [0,1,2,1,0]
[0,0,1,1,2]

fromAscListMS :: Eq a => [a] -> Multiset a Source #

O(n)

>>> fromAscListMS [0,0,1,2]
[0,0,1,2]

fromDistinctAscListMS :: [a] -> Multiset a Source #

O(n)

>>> fromDistinctAscListMS [0,1,2]
[0,1,2]

fromDescListMS :: Eq a => [a] -> Multiset a Source #

O(n)

>>> fromDescListMS [2,1,0,0]
[0,0,1,2]

fromDistinctDescListMS :: [a] -> Multiset a Source #

O(n)

>>> fromDistinctDescListMS [2,1,0]
[0,1,2]

toListMS :: Multiset a -> [a] Source #

O(n)

>>> toListMS (fromListMS [0,1,0,2])
[0,0,1,2]

toAscListMS :: Multiset a -> [a] Source #

O(n)

>>> toAscListMS (fromListMS [0,1,0,2])
[0,0,1,2]

toDescListMS :: Multiset a -> [a] Source #

O(n)

>>> toDescListMS (fromListMS [0,1,0,2])
[2,1,0,0]

insertMS :: Ord a => a -> Multiset a -> Multiset a Source #

O(log n)

deleteMS :: Ord a => a -> Multiset a -> Multiset a Source #

O(log n)

>>> deleteMS 0 (fromList [0, 0, 1, 2])
[0,1,2]
>>> deleteMS 3 (fromList [0, 0, 1, 2])
[0,0,1,2]

deleteAllMS :: Ord a => a -> Multiset a -> Multiset a Source #

O(log n)

>>> deleteAllMS 0 (fromList [0, 0, 1, 2])
[1,2]
>>> deleteAllMS 3 (fromList [0, 0, 1, 2])
[0,0,1,2]

memberMS :: Ord a => a -> Multiset a -> Bool Source #

O(log n)

notMemberMS :: Ord a => a -> Multiset a -> Bool Source #

O(log n)

countMS :: Ord a => a -> Multiset a -> Int Source #

O(log n)

>>> countMS 0 (fromList [0, 0, 1, 2])
2
>>> countMS 1 (fromList [0, 0, 1, 2])
1
>>> countMS (-1) (fromList [0, 0, 1, 2])
0

lookupLTMS :: Ord a => a -> Multiset a -> Maybe a Source #

O(log n)

>>> lookupLTMS 1 (fromList [0, 0, 1, 1, 2, 2])
Just 0
>>> lookupLTMS 0 (fromList [0, 0, 1, 1, 2, 2])
Nothing

lookupGTMS :: Ord a => a -> Multiset a -> Maybe a Source #

O(log n)

>>> lookupGTMS 1 (fromList [0, 0, 1, 1, 2, 2])
Just 2
>>> lookupGTMS 2 (fromList [0, 0, 1, 1, 2, 2])
Nothing

lookupLEMS :: Ord a => a -> Multiset a -> Maybe a Source #

O(log n)

>>> lookupLEMS 1 (fromList [0, 0, 1, 1, 2, 2])
Just 1
>>> lookupLEMS 0 (fromList [0, 0, 1, 1, 2, 2])
Just 0
>>> lookupLEMS (-1) (fromList [0, 0, 1, 1, 2, 2])
Nothing

lookupGEMS :: Ord a => a -> Multiset a -> Maybe a Source #

O(log n)

>>> lookupGEMS 1 (fromList [0, 0, 1, 1, 2, 2])
Just 1
>>> lookupGEMS 2 (fromList [0, 0, 1, 1, 2, 2])
Just 2
>>> lookupGEMS 3 (fromList [0, 0, 1, 1, 2, 2])
Nothing

nullMS :: Multiset a -> Bool Source #

O(1)

sizeMS :: Multiset a -> Int Source #

O(n)

>>> sizeMS (fromList [0, 0, 1, 2])
4
>>> sizeMS emptyMS
0

distinctSizeMS :: Multiset a -> Int Source #

O(1)

>>> distinctSizeMS (fromList [1,1,1,2,2,3])
3

findMinMS :: Multiset a -> a Source #

O(log n)

>>> findMinMS (fromList [0, 0, 1, 2])
0
>>> findMinMS emptyMS
*** Exception: Map.findMin: empty map has no minimal element

findMaxMS :: Multiset a -> a Source #

O(log n)

>>> findMaxMS (fromList [0, 0, 1, 2])
2

>>> findMaxMS emptyMS
*** Exception: Map.findMax: empty map has no maximal element

deleteMinMS :: Multiset a -> Multiset a Source #

O(log n)

>>> deleteMinMS (fromList [0, 0, 1, 2])
[0,1,2]
>>> deleteMinMS emptyMS
[]

deleteMaxMS :: Multiset a -> Multiset a Source #

O(log n)

>>> deleteMaxMS (fromList [0, 1, 2, 2])
[0,1,2]
>>> deleteMaxMS emptyMS
[]

deleteFindMinMS :: Ord a => Multiset a -> (a, Multiset a) Source #

O(log n)

>>> deleteFindMinMS (fromList [0, 0, 1, 2])
(0,[0,1,2])
>>> deleteFindMinMS emptyMS
*** Exception: Map.deleteFindMin: can not return the minimal element of an empty map

deleteFindMaxMS :: Ord a => Multiset a -> (a, Multiset a) Source #

O(log n)

>>> deleteFindMaxMS (fromList [0, 1, 2, 2])
(2,[0,1,2])

>>> deleteFindMaxMS emptyMS
*** Exception: Map.deleteFindMax: can not return the maximal element of an empty map

minViewMS :: Ord a => Multiset a -> Maybe (a, Multiset a) Source #

O(log n)

>>> minViewMS (fromList [0, 0, 1, 2])
Just (0,[0,1,2])

>>> minViewMS emptyMS
Nothing

maxViewMS :: Ord a => Multiset a -> Maybe (a, Multiset a) Source #

O(log n)

>>> maxViewMS (fromList [0, 1, 2, 2])
Just (2,[0,1,2])

>>> maxViewMS emptyMS
Nothing

splitMS :: Ord a => a -> Multiset a -> (Multiset a, Multiset a) Source #

O(log n)

>>> splitMS 1 (fromList [0, 0, 1, 2])
([0,0],[2])
>>> splitMS 0 (fromList [0, 0, 1, 2])
([],[1,2])
>>> splitMS (-1) (fromList [0, 0, 1, 2])
([],[0,0,1,2])

splitLookupMS :: Ord a => a -> Multiset a -> (Multiset a, [a], Multiset a) Source #

O(log n)

>>> splitLookupMS 1 (fromList [0, 0, 1, 2])
([0,0],[1],[2])
>>> splitLookupMS 0 (fromList [0, 0, 1, 2])
([],[0,0],[1,2])
>>> splitLookupMS (-1) (fromList [0, 0, 1, 2])
([],[],[0,0,1,2])