module Data.MonoidMap.Examples.MultiSet
( fromList
, toList
, null
, member
, multiplicity
, root
, cardinality
, dimension
, height
, isSubsetOf
, intersection
, union
, disjointUnion
, add
, subtract
, subtractMaybe
)
where
import Prelude hiding
( null, subtract )
import Data.Function
( on )
import Data.Monoid
( Sum (..) )
import Data.Monoid.GCD
( DistributiveGCDMonoid
, GCDMonoid
, LeftDistributiveGCDMonoid
, LeftGCDMonoid
, OverlappingGCDMonoid
, RightDistributiveGCDMonoid
, RightGCDMonoid
)
import Data.Monoid.LCM
( DistributiveLCMMonoid, LCMMonoid )
import Data.Monoid.Monus
( Monus ((<\>)) )
import Data.Monoid.Null
( MonoidNull, PositiveMonoid )
import Data.MonoidMap
( MonoidMap )
import Data.Semigroup.Cancellative
( Cancellative
, Commutative
, LeftCancellative
, LeftReductive
, Reductive ((</>))
, RightCancellative
, RightReductive
)
import Data.Set
( Set )
import Numeric.Natural
( Natural )
import Text.Read
( Read (..) )
import qualified Data.Foldable as F
import qualified Data.MonoidMap as MonoidMap
newtype MultiSet a = MultiSet
{ forall a. MultiSet a -> MonoidMap a (Sum Natural)
unMultiSet :: MonoidMap a (Sum Natural)
}
deriving newtype
( MultiSet a -> MultiSet a -> Bool
(MultiSet a -> MultiSet a -> Bool)
-> (MultiSet a -> MultiSet a -> Bool) -> Eq (MultiSet a)
forall a. Eq a => MultiSet a -> MultiSet a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => MultiSet a -> MultiSet a -> Bool
== :: MultiSet a -> MultiSet a -> Bool
$c/= :: forall a. Eq a => MultiSet a -> MultiSet a -> Bool
/= :: MultiSet a -> MultiSet a -> Bool
Eq
, NonEmpty (MultiSet a) -> MultiSet a
MultiSet a -> MultiSet a -> MultiSet a
(MultiSet a -> MultiSet a -> MultiSet a)
-> (NonEmpty (MultiSet a) -> MultiSet a)
-> (forall b. Integral b => b -> MultiSet a -> MultiSet a)
-> Semigroup (MultiSet a)
forall b. Integral b => b -> MultiSet a -> MultiSet a
forall a. Ord a => NonEmpty (MultiSet a) -> MultiSet a
forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
forall a b. (Ord a, Integral b) => b -> MultiSet a -> MultiSet a
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
$c<> :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
<> :: MultiSet a -> MultiSet a -> MultiSet a
$csconcat :: forall a. Ord a => NonEmpty (MultiSet a) -> MultiSet a
sconcat :: NonEmpty (MultiSet a) -> MultiSet a
$cstimes :: forall a b. (Ord a, Integral b) => b -> MultiSet a -> MultiSet a
stimes :: forall b. Integral b => b -> MultiSet a -> MultiSet a
Semigroup
, Semigroup (MultiSet a)
Semigroup (MultiSet a) => Commutative (MultiSet a)
forall a. Ord a => Semigroup (MultiSet a)
forall g. Semigroup g => Commutative g
Commutative
, Semigroup (MultiSet a)
MultiSet a
Semigroup (MultiSet a) =>
MultiSet a
-> (MultiSet a -> MultiSet a -> MultiSet a)
-> ([MultiSet a] -> MultiSet a)
-> Monoid (MultiSet a)
[MultiSet a] -> MultiSet a
MultiSet a -> MultiSet a -> MultiSet a
forall a. Ord a => Semigroup (MultiSet a)
forall a. Ord a => MultiSet a
forall a. Ord a => [MultiSet a] -> MultiSet a
forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
forall a.
Semigroup a =>
a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
$cmempty :: forall a. Ord a => MultiSet a
mempty :: MultiSet a
$cmappend :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
mappend :: MultiSet a -> MultiSet a -> MultiSet a
$cmconcat :: forall a. Ord a => [MultiSet a] -> MultiSet a
mconcat :: [MultiSet a] -> MultiSet a
Monoid
, Monoid (MultiSet a)
Monoid (MultiSet a) =>
(MultiSet a -> Bool) -> MonoidNull (MultiSet a)
MultiSet a -> Bool
forall a. Ord a => Monoid (MultiSet a)
forall a. Ord a => MultiSet a -> Bool
forall m. Monoid m => (m -> Bool) -> MonoidNull m
$cnull :: forall a. Ord a => MultiSet a -> Bool
null :: MultiSet a -> Bool
MonoidNull
, MonoidNull (MultiSet a)
MonoidNull (MultiSet a) => PositiveMonoid (MultiSet a)
forall a. Ord a => MonoidNull (MultiSet a)
forall m. MonoidNull m => PositiveMonoid m
PositiveMonoid
, Semigroup (MultiSet a)
Semigroup (MultiSet a) =>
(MultiSet a -> MultiSet a -> Bool)
-> (MultiSet a -> MultiSet a -> Maybe (MultiSet a))
-> LeftReductive (MultiSet a)
MultiSet a -> MultiSet a -> Bool
MultiSet a -> MultiSet a -> Maybe (MultiSet a)
forall a. Ord a => Semigroup (MultiSet a)
forall a. Ord a => MultiSet a -> MultiSet a -> Bool
forall a. Ord a => MultiSet a -> MultiSet a -> Maybe (MultiSet a)
forall m.
Semigroup m =>
(m -> m -> Bool) -> (m -> m -> Maybe m) -> LeftReductive m
$cisPrefixOf :: forall a. Ord a => MultiSet a -> MultiSet a -> Bool
isPrefixOf :: MultiSet a -> MultiSet a -> Bool
$cstripPrefix :: forall a. Ord a => MultiSet a -> MultiSet a -> Maybe (MultiSet a)
stripPrefix :: MultiSet a -> MultiSet a -> Maybe (MultiSet a)
LeftReductive
, LeftReductive (MultiSet a)
LeftReductive (MultiSet a) => LeftCancellative (MultiSet a)
forall a. Ord a => LeftReductive (MultiSet a)
forall m. LeftReductive m => LeftCancellative m
LeftCancellative
, Monoid (MultiSet a)
LeftReductive (MultiSet a)
(Monoid (MultiSet a), LeftReductive (MultiSet a)) =>
(MultiSet a -> MultiSet a -> MultiSet a)
-> (MultiSet a
-> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a))
-> LeftGCDMonoid (MultiSet a)
MultiSet a -> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a)
MultiSet a -> MultiSet a -> MultiSet a
forall a. Ord a => Monoid (MultiSet a)
forall a. Ord a => LeftReductive (MultiSet a)
forall a.
Ord a =>
MultiSet a -> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a)
forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
forall m.
(Monoid m, LeftReductive m) =>
(m -> m -> m) -> (m -> m -> (m, m, m)) -> LeftGCDMonoid m
$ccommonPrefix :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
commonPrefix :: MultiSet a -> MultiSet a -> MultiSet a
$cstripCommonPrefix :: forall a.
Ord a =>
MultiSet a -> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a)
stripCommonPrefix :: MultiSet a -> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a)
LeftGCDMonoid
, LeftGCDMonoid (MultiSet a)
LeftGCDMonoid (MultiSet a) =>
LeftDistributiveGCDMonoid (MultiSet a)
forall a. Ord a => LeftGCDMonoid (MultiSet a)
forall m. LeftGCDMonoid m => LeftDistributiveGCDMonoid m
LeftDistributiveGCDMonoid
, Semigroup (MultiSet a)
Semigroup (MultiSet a) =>
(MultiSet a -> MultiSet a -> Bool)
-> (MultiSet a -> MultiSet a -> Maybe (MultiSet a))
-> RightReductive (MultiSet a)
MultiSet a -> MultiSet a -> Bool
MultiSet a -> MultiSet a -> Maybe (MultiSet a)
forall a. Ord a => Semigroup (MultiSet a)
forall a. Ord a => MultiSet a -> MultiSet a -> Bool
forall a. Ord a => MultiSet a -> MultiSet a -> Maybe (MultiSet a)
forall m.
Semigroup m =>
(m -> m -> Bool) -> (m -> m -> Maybe m) -> RightReductive m
$cisSuffixOf :: forall a. Ord a => MultiSet a -> MultiSet a -> Bool
isSuffixOf :: MultiSet a -> MultiSet a -> Bool
$cstripSuffix :: forall a. Ord a => MultiSet a -> MultiSet a -> Maybe (MultiSet a)
stripSuffix :: MultiSet a -> MultiSet a -> Maybe (MultiSet a)
RightReductive
, RightReductive (MultiSet a)
RightReductive (MultiSet a) => RightCancellative (MultiSet a)
forall a. Ord a => RightReductive (MultiSet a)
forall m. RightReductive m => RightCancellative m
RightCancellative
, Monoid (MultiSet a)
RightReductive (MultiSet a)
(Monoid (MultiSet a), RightReductive (MultiSet a)) =>
(MultiSet a -> MultiSet a -> MultiSet a)
-> (MultiSet a
-> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a))
-> RightGCDMonoid (MultiSet a)
MultiSet a -> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a)
MultiSet a -> MultiSet a -> MultiSet a
forall a. Ord a => Monoid (MultiSet a)
forall a. Ord a => RightReductive (MultiSet a)
forall a.
Ord a =>
MultiSet a -> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a)
forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
forall m.
(Monoid m, RightReductive m) =>
(m -> m -> m) -> (m -> m -> (m, m, m)) -> RightGCDMonoid m
$ccommonSuffix :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
commonSuffix :: MultiSet a -> MultiSet a -> MultiSet a
$cstripCommonSuffix :: forall a.
Ord a =>
MultiSet a -> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a)
stripCommonSuffix :: MultiSet a -> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a)
RightGCDMonoid
, RightGCDMonoid (MultiSet a)
RightGCDMonoid (MultiSet a) =>
RightDistributiveGCDMonoid (MultiSet a)
forall a. Ord a => RightGCDMonoid (MultiSet a)
forall m. RightGCDMonoid m => RightDistributiveGCDMonoid m
RightDistributiveGCDMonoid
, Commutative (MultiSet a)
RightReductive (MultiSet a)
LeftReductive (MultiSet a)
(Commutative (MultiSet a), LeftReductive (MultiSet a),
RightReductive (MultiSet a)) =>
(MultiSet a -> MultiSet a -> Maybe (MultiSet a))
-> Reductive (MultiSet a)
MultiSet a -> MultiSet a -> Maybe (MultiSet a)
forall a. Ord a => Commutative (MultiSet a)
forall a. Ord a => RightReductive (MultiSet a)
forall a. Ord a => LeftReductive (MultiSet a)
forall a. Ord a => MultiSet a -> MultiSet a -> Maybe (MultiSet a)
forall m.
(Commutative m, LeftReductive m, RightReductive m) =>
(m -> m -> Maybe m) -> Reductive m
$c</> :: forall a. Ord a => MultiSet a -> MultiSet a -> Maybe (MultiSet a)
</> :: MultiSet a -> MultiSet a -> Maybe (MultiSet a)
Reductive
, RightCancellative (MultiSet a)
LeftCancellative (MultiSet a)
Reductive (MultiSet a)
(LeftCancellative (MultiSet a), RightCancellative (MultiSet a),
Reductive (MultiSet a)) =>
Cancellative (MultiSet a)
forall a. Ord a => RightCancellative (MultiSet a)
forall a. Ord a => LeftCancellative (MultiSet a)
forall a. Ord a => Reductive (MultiSet a)
forall m.
(LeftCancellative m, RightCancellative m, Reductive m) =>
Cancellative m
Cancellative
, Monoid (MultiSet a)
Commutative (MultiSet a)
Reductive (MultiSet a)
OverlappingGCDMonoid (MultiSet a)
RightGCDMonoid (MultiSet a)
LeftGCDMonoid (MultiSet a)
(Monoid (MultiSet a), Commutative (MultiSet a),
Reductive (MultiSet a), LeftGCDMonoid (MultiSet a),
RightGCDMonoid (MultiSet a), OverlappingGCDMonoid (MultiSet a)) =>
(MultiSet a -> MultiSet a -> MultiSet a) -> GCDMonoid (MultiSet a)
MultiSet a -> MultiSet a -> MultiSet a
forall a. Ord a => Monoid (MultiSet a)
forall a. Ord a => Commutative (MultiSet a)
forall a. Ord a => Reductive (MultiSet a)
forall a. Ord a => OverlappingGCDMonoid (MultiSet a)
forall a. Ord a => RightGCDMonoid (MultiSet a)
forall a. Ord a => LeftGCDMonoid (MultiSet a)
forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
forall m.
(Monoid m, Commutative m, Reductive m, LeftGCDMonoid m,
RightGCDMonoid m, OverlappingGCDMonoid m) =>
(m -> m -> m) -> GCDMonoid m
$cgcd :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
gcd :: MultiSet a -> MultiSet a -> MultiSet a
GCDMonoid
, GCDMonoid (MultiSet a)
GCDMonoid (MultiSet a) =>
(MultiSet a -> MultiSet a -> MultiSet a) -> LCMMonoid (MultiSet a)
MultiSet a -> MultiSet a -> MultiSet a
forall a. Ord a => GCDMonoid (MultiSet a)
forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
forall m. GCDMonoid m => (m -> m -> m) -> LCMMonoid m
$clcm :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
lcm :: MultiSet a -> MultiSet a -> MultiSet a
LCMMonoid
, RightDistributiveGCDMonoid (MultiSet a)
LeftDistributiveGCDMonoid (MultiSet a)
GCDMonoid (MultiSet a)
(LeftDistributiveGCDMonoid (MultiSet a),
RightDistributiveGCDMonoid (MultiSet a), GCDMonoid (MultiSet a)) =>
DistributiveGCDMonoid (MultiSet a)
forall a. Ord a => RightDistributiveGCDMonoid (MultiSet a)
forall a. Ord a => LeftDistributiveGCDMonoid (MultiSet a)
forall a. Ord a => GCDMonoid (MultiSet a)
forall m.
(LeftDistributiveGCDMonoid m, RightDistributiveGCDMonoid m,
GCDMonoid m) =>
DistributiveGCDMonoid m
DistributiveGCDMonoid
, DistributiveGCDMonoid (MultiSet a)
LCMMonoid (MultiSet a)
(DistributiveGCDMonoid (MultiSet a), LCMMonoid (MultiSet a)) =>
DistributiveLCMMonoid (MultiSet a)
forall a. Ord a => DistributiveGCDMonoid (MultiSet a)
forall a. Ord a => LCMMonoid (MultiSet a)
forall m.
(DistributiveGCDMonoid m, LCMMonoid m) =>
DistributiveLCMMonoid m
DistributiveLCMMonoid
, Monoid (MultiSet a)
RightReductive (MultiSet a)
LeftReductive (MultiSet a)
(Monoid (MultiSet a), LeftReductive (MultiSet a),
RightReductive (MultiSet a)) =>
(MultiSet a -> MultiSet a -> MultiSet a)
-> (MultiSet a -> MultiSet a -> MultiSet a)
-> (MultiSet a -> MultiSet a -> MultiSet a)
-> (MultiSet a
-> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a))
-> OverlappingGCDMonoid (MultiSet a)
MultiSet a -> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a)
MultiSet a -> MultiSet a -> MultiSet a
forall a. Ord a => Monoid (MultiSet a)
forall a. Ord a => RightReductive (MultiSet a)
forall a. Ord a => LeftReductive (MultiSet a)
forall a.
Ord a =>
MultiSet a -> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a)
forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
forall m.
(Monoid m, LeftReductive m, RightReductive m) =>
(m -> m -> m)
-> (m -> m -> m)
-> (m -> m -> m)
-> (m -> m -> (m, m, m))
-> OverlappingGCDMonoid m
$cstripPrefixOverlap :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
stripPrefixOverlap :: MultiSet a -> MultiSet a -> MultiSet a
$cstripSuffixOverlap :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
stripSuffixOverlap :: MultiSet a -> MultiSet a -> MultiSet a
$coverlap :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
overlap :: MultiSet a -> MultiSet a -> MultiSet a
$cstripOverlap :: forall a.
Ord a =>
MultiSet a -> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a)
stripOverlap :: MultiSet a -> MultiSet a -> (MultiSet a, MultiSet a, MultiSet a)
OverlappingGCDMonoid
, Monoid (MultiSet a)
Commutative (MultiSet a)
OverlappingGCDMonoid (MultiSet a)
(Commutative (MultiSet a), Monoid (MultiSet a),
OverlappingGCDMonoid (MultiSet a)) =>
(MultiSet a -> MultiSet a -> MultiSet a) -> Monus (MultiSet a)
MultiSet a -> MultiSet a -> MultiSet a
forall a. Ord a => Monoid (MultiSet a)
forall a. Ord a => Commutative (MultiSet a)
forall a. Ord a => OverlappingGCDMonoid (MultiSet a)
forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
forall m.
(Commutative m, Monoid m, OverlappingGCDMonoid m) =>
(m -> m -> m) -> Monus m
$c<\> :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
<\> :: MultiSet a -> MultiSet a -> MultiSet a
Monus
)
instance (Ord a, Read a) => Read (MultiSet a) where
readPrec :: ReadPrec (MultiSet a)
readPrec = [(a, Natural)] -> MultiSet a
forall a. Ord a => [(a, Natural)] -> MultiSet a
fromList ([(a, Natural)] -> MultiSet a)
-> ReadPrec [(a, Natural)] -> ReadPrec (MultiSet a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ReadPrec [(a, Natural)]
forall a. Read a => ReadPrec a
readPrec
instance Show a => Show (MultiSet a) where
show :: MultiSet a -> String
show = [(a, Natural)] -> String
forall a. Show a => a -> String
show ([(a, Natural)] -> String)
-> (MultiSet a -> [(a, Natural)]) -> MultiSet a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiSet a -> [(a, Natural)]
forall a. MultiSet a -> [(a, Natural)]
toList
fromList :: Ord a => [(a, Natural)] -> MultiSet a
fromList :: forall a. Ord a => [(a, Natural)] -> MultiSet a
fromList = MonoidMap a (Sum Natural) -> MultiSet a
forall a. MonoidMap a (Sum Natural) -> MultiSet a
MultiSet (MonoidMap a (Sum Natural) -> MultiSet a)
-> ([(a, Natural)] -> MonoidMap a (Sum Natural))
-> [(a, Natural)]
-> MultiSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(a, Sum Natural)] -> MonoidMap a (Sum Natural)
forall k v. (Ord k, MonoidNull v) => [(k, v)] -> MonoidMap k v
MonoidMap.fromList ([(a, Sum Natural)] -> MonoidMap a (Sum Natural))
-> ([(a, Natural)] -> [(a, Sum Natural)])
-> [(a, Natural)]
-> MonoidMap a (Sum Natural)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, Natural) -> (a, Sum Natural))
-> [(a, Natural)] -> [(a, Sum Natural)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Natural -> Sum Natural) -> (a, Natural) -> (a, Sum Natural)
forall a b. (a -> b) -> (a, a) -> (a, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Natural -> Sum Natural
forall a. a -> Sum a
Sum)
toList :: MultiSet a -> [(a, Natural)]
toList :: forall a. MultiSet a -> [(a, Natural)]
toList = ((a, Sum Natural) -> (a, Natural))
-> [(a, Sum Natural)] -> [(a, Natural)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Sum Natural -> Natural) -> (a, Sum Natural) -> (a, Natural)
forall a b. (a -> b) -> (a, a) -> (a, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Sum Natural -> Natural
forall a. Sum a -> a
getSum) ([(a, Sum Natural)] -> [(a, Natural)])
-> (MultiSet a -> [(a, Sum Natural)])
-> MultiSet a
-> [(a, Natural)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonoidMap a (Sum Natural) -> [(a, Sum Natural)]
forall k v. MonoidMap k v -> [(k, v)]
MonoidMap.toList (MonoidMap a (Sum Natural) -> [(a, Sum Natural)])
-> (MultiSet a -> MonoidMap a (Sum Natural))
-> MultiSet a
-> [(a, Sum Natural)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiSet a -> MonoidMap a (Sum Natural)
forall a. MultiSet a -> MonoidMap a (Sum Natural)
unMultiSet
null :: MultiSet a -> Bool
null :: forall a. MultiSet a -> Bool
null = MonoidMap a (Sum Natural) -> Bool
forall k v. MonoidMap k v -> Bool
MonoidMap.null (MonoidMap a (Sum Natural) -> Bool)
-> (MultiSet a -> MonoidMap a (Sum Natural)) -> MultiSet a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiSet a -> MonoidMap a (Sum Natural)
forall a. MultiSet a -> MonoidMap a (Sum Natural)
unMultiSet
member :: Ord a => a -> MultiSet a -> Bool
member :: forall a. Ord a => a -> MultiSet a -> Bool
member a
a = a -> MonoidMap a (Sum Natural) -> Bool
forall k v. Ord k => k -> MonoidMap k v -> Bool
MonoidMap.nonNullKey a
a (MonoidMap a (Sum Natural) -> Bool)
-> (MultiSet a -> MonoidMap a (Sum Natural)) -> MultiSet a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiSet a -> MonoidMap a (Sum Natural)
forall a. MultiSet a -> MonoidMap a (Sum Natural)
unMultiSet
multiplicity :: Ord a => a -> MultiSet a -> Natural
multiplicity :: forall a. Ord a => a -> MultiSet a -> Natural
multiplicity a
a = Sum Natural -> Natural
forall a. Sum a -> a
getSum (Sum Natural -> Natural)
-> (MultiSet a -> Sum Natural) -> MultiSet a -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> MonoidMap a (Sum Natural) -> Sum Natural
forall k v. (Ord k, Monoid v) => k -> MonoidMap k v -> v
MonoidMap.get a
a (MonoidMap a (Sum Natural) -> Sum Natural)
-> (MultiSet a -> MonoidMap a (Sum Natural))
-> MultiSet a
-> Sum Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiSet a -> MonoidMap a (Sum Natural)
forall a. MultiSet a -> MonoidMap a (Sum Natural)
unMultiSet
root :: Ord a => MultiSet a -> Set a
root :: forall a. Ord a => MultiSet a -> Set a
root = MonoidMap a (Sum Natural) -> Set a
forall k v. MonoidMap k v -> Set k
MonoidMap.nonNullKeys (MonoidMap a (Sum Natural) -> Set a)
-> (MultiSet a -> MonoidMap a (Sum Natural)) -> MultiSet a -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiSet a -> MonoidMap a (Sum Natural)
forall a. MultiSet a -> MonoidMap a (Sum Natural)
unMultiSet
cardinality :: MultiSet a -> Natural
cardinality :: forall a. MultiSet a -> Natural
cardinality = Sum Natural -> Natural
forall a. Sum a -> a
getSum (Sum Natural -> Natural)
-> (MultiSet a -> Sum Natural) -> MultiSet a -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonoidMap a (Sum Natural) -> Sum Natural
forall m. Monoid m => MonoidMap a m -> m
forall (t :: * -> *) m. (Foldable t, Monoid m) => t m -> m
F.fold (MonoidMap a (Sum Natural) -> Sum Natural)
-> (MultiSet a -> MonoidMap a (Sum Natural))
-> MultiSet a
-> Sum Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiSet a -> MonoidMap a (Sum Natural)
forall a. MultiSet a -> MonoidMap a (Sum Natural)
unMultiSet
dimension :: MultiSet a -> Natural
dimension :: forall a. MultiSet a -> Natural
dimension = Int -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Natural) -> (MultiSet a -> Int) -> MultiSet a -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonoidMap a (Sum Natural) -> Int
forall k v. MonoidMap k v -> Int
MonoidMap.nonNullCount (MonoidMap a (Sum Natural) -> Int)
-> (MultiSet a -> MonoidMap a (Sum Natural)) -> MultiSet a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MultiSet a -> MonoidMap a (Sum Natural)
forall a. MultiSet a -> MonoidMap a (Sum Natural)
unMultiSet
height :: Ord a => MultiSet a -> Natural
height :: forall a. Ord a => MultiSet a -> Natural
height MultiSet a
s
| MultiSet a -> Bool
forall a. MultiSet a -> Bool
null MultiSet a
s = Natural
0
| Bool
otherwise = Sum Natural -> Natural
forall a. Sum a -> a
getSum (Sum Natural -> Natural) -> Sum Natural -> Natural
forall a b. (a -> b) -> a -> b
$ MonoidMap a (Sum Natural) -> Sum Natural
forall a. Ord a => MonoidMap a a -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
F.maximum (MonoidMap a (Sum Natural) -> Sum Natural)
-> MonoidMap a (Sum Natural) -> Sum Natural
forall a b. (a -> b) -> a -> b
$ MultiSet a -> MonoidMap a (Sum Natural)
forall a. MultiSet a -> MonoidMap a (Sum Natural)
unMultiSet MultiSet a
s
isSubsetOf :: Ord a => MultiSet a -> MultiSet a -> Bool
isSubsetOf :: forall a. Ord a => MultiSet a -> MultiSet a -> Bool
isSubsetOf = MonoidMap a (Sum Natural) -> MonoidMap a (Sum Natural) -> Bool
forall k v.
(Ord k, Monoid v, Reductive v) =>
MonoidMap k v -> MonoidMap k v -> Bool
MonoidMap.isSubmapOf (MonoidMap a (Sum Natural) -> MonoidMap a (Sum Natural) -> Bool)
-> (MultiSet a -> MonoidMap a (Sum Natural))
-> MultiSet a
-> MultiSet a
-> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` MultiSet a -> MonoidMap a (Sum Natural)
forall a. MultiSet a -> MonoidMap a (Sum Natural)
unMultiSet
intersection :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
intersection :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
intersection (MultiSet MonoidMap a (Sum Natural)
s1) (MultiSet MonoidMap a (Sum Natural)
s2) =
MonoidMap a (Sum Natural) -> MultiSet a
forall a. MonoidMap a (Sum Natural) -> MultiSet a
MultiSet (MonoidMap a (Sum Natural)
-> MonoidMap a (Sum Natural) -> MonoidMap a (Sum Natural)
forall k v.
(Ord k, MonoidNull v, GCDMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
MonoidMap.intersection MonoidMap a (Sum Natural)
s1 MonoidMap a (Sum Natural)
s2)
union :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
union :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
union (MultiSet MonoidMap a (Sum Natural)
s1) (MultiSet MonoidMap a (Sum Natural)
s2) =
MonoidMap a (Sum Natural) -> MultiSet a
forall a. MonoidMap a (Sum Natural) -> MultiSet a
MultiSet (MonoidMap a (Sum Natural)
-> MonoidMap a (Sum Natural) -> MonoidMap a (Sum Natural)
forall k v.
(Ord k, MonoidNull v, LCMMonoid v) =>
MonoidMap k v -> MonoidMap k v -> MonoidMap k v
MonoidMap.union MonoidMap a (Sum Natural)
s1 MonoidMap a (Sum Natural)
s2)
disjointUnion :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
disjointUnion :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
disjointUnion MultiSet a
m1 MultiSet a
m2 = (MultiSet a
m1 MultiSet a -> MultiSet a -> MultiSet a
forall m. Monus m => m -> m -> m
<\> MultiSet a
m2) MultiSet a -> MultiSet a -> MultiSet a
forall a. Semigroup a => a -> a -> a
<> (MultiSet a
m2 MultiSet a -> MultiSet a -> MultiSet a
forall m. Monus m => m -> m -> m
<\> MultiSet a
m1)
add :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
add :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
add = MultiSet a -> MultiSet a -> MultiSet a
forall a. Semigroup a => a -> a -> a
(<>)
subtract :: Ord a => MultiSet a -> MultiSet a -> MultiSet a
subtract :: forall a. Ord a => MultiSet a -> MultiSet a -> MultiSet a
subtract = MultiSet a -> MultiSet a -> MultiSet a
forall m. Monus m => m -> m -> m
(<\>)
subtractMaybe :: Ord a => MultiSet a -> MultiSet a -> Maybe (MultiSet a)
subtractMaybe :: forall a. Ord a => MultiSet a -> MultiSet a -> Maybe (MultiSet a)
subtractMaybe = MultiSet a -> MultiSet a -> Maybe (MultiSet a)
forall m. Reductive m => m -> m -> Maybe m
(</>)