--------------------------------------------------------------------------------
-- |
-- Module      :  Data.SignedMultiset
-- Copyright   :  (c) 2012 Stefan Holdermans
-- License     :  BSD-style
-- Maintainer  :  stefan@vectorfabrics.com
-- Stability   :  provisional
-- Portability :  non-portable (DeriveDataTypeable)
--
-- An efficient implementation of signed multisets.
--
-- A signed multiset is like a multiset (or bag), but additionally allows for
-- /negative membership/.
-- That is, in a signed multiset, an object can occur a negative number of
-- times.
--
-- For a theory of signed multisets, see
--
-- * Wayne D. Blizard. Negative membership.
--   /Notre Dame Journal of Formal Logic/, 31(3):346--368, 1990.
--
-- Since many function names (but not the type name) clash with Prelude names,
-- this module is usually imported @qualified@, e.g.,
--
-- >  import Data.SignedMultiset (SignedMultiset)
-- >  import qualified Data.SignedMultiset as SignedMultiset
--
-- Function comments contain the function's time complexity in so-called big-O
-- notation, with /n/ referring to the number of multiset members involved.
--
-- Signed-multiset types are constructed by the type constructor
-- 'SignedMultiset'.
-- The number of times an object appears in a signed multiset is called its
-- 'multiplicity'.
-- An object is said to be a 'member' of a signed multiset if it has a nonzero
-- multiplicity.
-- The number of members of a signed multiset is referred to as its 'size',
-- while the 'cardinality' of a signed multiset is the sum of the multiplicities
-- of its members.
-- A signed multiset is 'empty' if it is without members.
--
-- Textually, signed multisets are represented by listing their members and, in
-- parentheses, their multiplicities between curly brackets.
-- For instance, the signed multiset that contains -1 copies of 2, 2 copies of
-- 3, and -4 copies of 5 is denoted by @\"{2(-1),3(2),5(-4)}\"@.
--
--------------------------------------------------------------------------------

{-# LANGUAGE DeriveDataTypeable #-}

module Data.SignedMultiset (

    -- * Type
    SignedMultiset,         -- :: * -> *, abstract, instances: Eq, Ord, Show,
                            --   Read, Semigroup, Monoid, Typeable1, Data

    -- * Construction
    empty,                  -- :: SignedMultiset a
    singleton,              -- :: a -> SignedMultiset a
    insert,                 -- :: Ord a =>
                            --    a -> SignedMultiset a -> SignedMultiset a
    insertMany,             -- :: Ord a =>
                            --    a -> Int -> SignedMultiset a ->
                            --    SignedMultiset a
    delete,                 -- :: Ord a =>
                            --    a -> SignedMultiset a -> SignedMultiset a
    deleteMany,             -- :: Ord a =>
                            --    a -> Int -> SignedMultiset a ->
                            --    SignedMultiset a
    deleteAll,              -- :: Ord a =>
                            --    a -> SignedMultiset a -> SignedMultiset a

    -- * Queries
    null,                   -- :: SignedMultiset a -> Bool
    isSet,                  -- :: SignedMultiset a -> Bool
    isPositive,             -- :: SignedMultiset a -> Bool
    isNegative,             -- :: SignedMultiset a -> Bool
    size,                   -- :: SignedMultiset a -> Int
    cardinality,            -- :: SignedMultiset a -> Int
    member,                 -- :: Ord a => a -> SignedMultiset a -> Bool
    notMember,              -- :: Ord a => a -> SignedMultiset a -> Bool
    multiplicity,           -- :: Ord a => a -> SignedMultiset a -> Int
    isSubmultisetOf,        -- :: Ord a =>
                            --    SignedMultiset a -> SignedMultiset a -> Bool

    -- * Combining
    union,                  -- :: Ord a =>
                            --    SignedMultiset a -> SignedMultiset a ->
                            --    SignedMultiset a
    additiveUnion,          -- :: Ord a =>
                            --    SignedMultiset a -> SignedMultiset a ->
                            --    SignedMultiset a
    intersection,           -- :: Ord a =>
                            --    SignedMultiset a -> SignedMultiset a ->
                            --    SignedMultiset a

    -- * Memberwise operations
    root,                   -- :: SignedMultiset a -> SignedMultiset a
    shadow,                 -- :: SignedMultiset a -> SignedMultiset a
    modulus,                -- :: SignedMultiset a -> SignedMultiset a
    signum,                 -- :: SignedMultiset a -> SignedMultiset a
    unitstep,               -- :: Ord a => SignedMultiset a -> SignedMultiset a
    multiply,               -- :: Ord a =>
                            --    Int -> SignedMultiset a -> SignedMultiset a

    -- * Traversals
    map,                    -- :: (Ord a, Ord b) =>
                            --    (a -> b) ->
                            --    SignedMultiset a -> SignedMultiset b
    additiveMap,            -- :: (Ord a, Ord b) =>
                            --    (a -> b) ->
                            --    SignedMultiset a -> SignedMultiset b
    filter,                 -- :: Ord a =>
                            --    (a -> Int -> Bool) -> SignedMultiset a ->
                            --    SignedMultiset a
    partition,              -- :: Ord a =>
                            --    (a -> Int -> Bool) -> SignedMultiset a ->
                            --    (SignedMultiset a, SignedMultiset a)
    split,                  -- :: Ord a =>
                            --    (a -> Int -> Bool) -> SignedMultiset a ->
                            --    (SignedMultiset a, SignedMultiset a)
    foldr,                  -- :: (a -> b -> b) -> b -> SignedMultiset a -> b
    foldr',                 -- :: (a -> b -> b) -> b -> SignedMultiset a -> b
    foldl,                  -- :: (a -> b -> a) -> a -> SignedMultiset b -> a
    foldl',                 -- :: (a -> b -> a) -> a -> SignedMultiset b -> a

    -- * Conversion
    toList,                 -- :: SignedMultiset a -> [(a, Int)]
    toLists,                -- :: SignedMultiset a -> ([a], [a])
    fromList,               -- :: Ord a => [(a, Int)] -> SignedMultiset a
    fromLists,              -- :: Ord a => [a] -> [a] -> SignedMultiset a

    -- * Additive wrapper
    Additive (..)           -- :: * -> *, instances: Eq, Ord, Show, Read,
                            --   Semigroup, Monoid

  ) where

import Prelude hiding (signum, null, map, filter, foldr, foldl)
import qualified Prelude (signum, filter, foldr)
import Control.Arrow ((***))
import Data.Function (on)
import Data.Data (Data (..), mkNoRepType)
import Data.Typeable (Typeable)
import Data.Map (Map)
import qualified Data.Map as Map
import Data.SignedMultiset.Show (showsMembers)
import Data.SignedMultiset.Read (readsMembers, mapReadS)

--------------------------------------------------------------------------------
-- Type
--------------------------------------------------------------------------------

-- Signed multisets are implemented as maps from objects to their
-- multiplicities.
-- We maintain the invariant that all objects are mapped to nonzero
-- multiplicities; i.e., if an object is not a member of the multiset, it does
-- not appear as a key in the corresponding map.

-- | A signed multiset over objects of type @a@.
newtype SignedMultiset a = SMS {forall a. SignedMultiset a -> Map a Int
unSMS :: Map a Int} deriving Typeable

-- /O(n)/.
norm :: Map a Int -> SignedMultiset a
norm :: forall a. Map a Int -> SignedMultiset a
norm = forall a. Map a Int -> SignedMultiset a
SMS forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a k. (a -> Bool) -> Map k a -> Map k a
Map.filter (forall a. Eq a => a -> a -> Bool
/= Int
0)

instance Ord a => Eq (SignedMultiset a) where
  == :: SignedMultiset a -> SignedMultiset a -> Bool
(==) = forall a. Eq a => a -> a -> Bool
(==) forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` forall a. SignedMultiset a -> Map a Int
unSMS

instance Ord a => Ord (SignedMultiset a) where
  compare :: SignedMultiset a -> SignedMultiset a -> Ordering
compare = forall a. Ord a => a -> a -> Ordering
compare forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` forall a. SignedMultiset a -> Map a Int
unSMS

instance Show a => Show (SignedMultiset a) where
  showsPrec :: Int -> SignedMultiset a -> ShowS
showsPrec Int
_ = forall a. Show a => [(a, Int)] -> ShowS
showsMembers forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> [(a, Int)]
toList

instance (Ord a, Read a) => Read (SignedMultiset a) where
  readsPrec :: Int -> ReadS (SignedMultiset a)
readsPrec = forall a b. (a -> b) -> ReadS a -> ReadS b
mapReadS forall a. Ord a => [(a, Int)] -> SignedMultiset a
fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Read a => Int -> ReadS [(a, Int)]
readsMembers

-- | Semigroup under 'union'.
instance Ord a => Semigroup (SignedMultiset a) where
  <> :: SignedMultiset a -> SignedMultiset a -> SignedMultiset a
(<>) = forall a.
Ord a =>
SignedMultiset a -> SignedMultiset a -> SignedMultiset a
union

-- | Monoid under 'union'.
instance Ord a => Monoid (SignedMultiset a) where
  mempty :: SignedMultiset a
mempty  = forall a. SignedMultiset a
empty
  mappend :: SignedMultiset a -> SignedMultiset a -> SignedMultiset a
mappend = forall a. Semigroup a => a -> a -> a
(<>)

instance (Ord a, Data a) => Data (SignedMultiset a) where
  gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SignedMultiset a -> c (SignedMultiset a)
gfoldl forall d b. Data d => c (d -> b) -> d -> c b
f forall g. g -> c g
z   = forall d b. Data d => c (d -> b) -> d -> c b
f (forall g. g -> c g
z forall a. Ord a => [(a, Int)] -> SignedMultiset a
fromList) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> [(a, Int)]
toList
  gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SignedMultiset a)
gunfold forall b r. Data b => c (b -> r) -> c r
_ forall r. r -> c r
_  = forall a. HasCallStack => String -> a
error String
"Data.Data.gunfold: abstract datatype"
  toConstr :: SignedMultiset a -> Constr
toConstr SignedMultiset a
_   = forall a. HasCallStack => String -> a
error String
"Data.Data.toConstr: abstract datatype"
  dataTypeOf :: SignedMultiset a -> DataType
dataTypeOf SignedMultiset a
_ = String -> DataType
mkNoRepType String
"Data.SignedMultiset.SignedMultiset"

--------------------------------------------------------------------------------
-- Construction
--------------------------------------------------------------------------------

-- | /O(1)/. The empty signed multiset, i.e., the multiset in which every object
-- has multiplicity zero.
empty :: SignedMultiset a
empty :: forall a. SignedMultiset a
empty = forall a. Map a Int -> SignedMultiset a
SMS forall k a. Map k a
Map.empty

-- | /O(1)/. Create a signed multiset that contains exactly one copy of the
-- given object.
singleton :: a -> SignedMultiset a
singleton :: forall a. a -> SignedMultiset a
singleton a
x = forall a. Map a Int -> SignedMultiset a
SMS (forall k a. k -> a -> Map k a
Map.singleton a
x Int
1)

-- | /O(log n)/. Insert a new copy of the given object into a signed multiset,
-- i.e., increment the multiplicity of the object by 1.
insert :: Ord a => a -> SignedMultiset a -> SignedMultiset a
insert :: forall a. Ord a => a -> SignedMultiset a -> SignedMultiset a
insert a
x = forall a. Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a
insertMany a
x Int
1

-- | /O(log n)/. Insert a specified number of new copies of the given object
-- into a signed multiset, i.e., increment the multiplicity of the object by
-- the specified number. If the specified number is negative, copies are
-- deleted from the set.
insertMany :: Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a
insertMany :: forall a. Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a
insertMany a
x Int
n = forall a. Map a Int -> SignedMultiset a
SMS forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter Maybe Int -> Maybe Int
f a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS
  where
    f :: Maybe Int -> Maybe Int
f Maybe Int
Nothing  = forall a. a -> Maybe a
Just Int
n
    f (Just Int
m) = let k :: Int
k = Int
m forall a. Num a => a -> a -> a
+ Int
n in if Int
k forall a. Eq a => a -> a -> Bool
== Int
0 then forall a. Maybe a
Nothing else forall a. a -> Maybe a
Just Int
k

-- | /O(log n)/. Delete a copy of the given object from a signed multiset, i.e.,
-- decrement the multiplicity of the object by 1.
delete :: Ord a => a -> SignedMultiset a -> SignedMultiset a
delete :: forall a. Ord a => a -> SignedMultiset a -> SignedMultiset a
delete a
x = forall a. Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a
deleteMany a
x Int
1

-- | /O(log n)/. Delete a specified number of copies of the given object from
-- a signed multiset, i.e., decrement the multiplicity of the object by the
-- specified number. If the specified number is negative, new copies of the
-- object are inserted into the set.
deleteMany :: Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a
deleteMany :: forall a. Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a
deleteMany a
x Int
n = forall a. Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a
insertMany a
x (- Int
n)

-- | /O(log n)/. Delete all copies of the given object from a signed multiset,
-- i.e., set the multiplicity of the object to zero.
deleteAll :: Ord a => a -> SignedMultiset a -> SignedMultiset a
deleteAll :: forall a. Ord a => a -> SignedMultiset a -> SignedMultiset a
deleteAll a
x = forall a. Map a Int -> SignedMultiset a
SMS forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => k -> Map k a -> Map k a
Map.delete a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

--------------------------------------------------------------------------------
-- Queries
--------------------------------------------------------------------------------

-- | /O(1)/. Return whether the signed multiset is empty, i.e., whether every
-- object has multiplicity zero.
null :: SignedMultiset a -> Bool
null :: forall a. SignedMultiset a -> Bool
null = forall k a. Map k a -> Bool
Map.null forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Return whether the signed multiset is a set, i.e., whether all
-- object have either multiplicity zero or else multiplicity 1.
isSet :: SignedMultiset a -> Bool
isSet :: forall a. SignedMultiset a -> Bool
isSet = forall a b k. (a -> b -> b) -> b -> Map k a -> b
Map.foldr (Bool -> Bool -> Bool
(&&) forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall a. Eq a => a -> a -> Bool
== Int
1)) Bool
True forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Return whether all objects in the signed multiset have nonnegative
-- multiplicities.
isPositive :: SignedMultiset a -> Bool
isPositive :: forall a. SignedMultiset a -> Bool
isPositive = forall a b k. (a -> b -> b) -> b -> Map k a -> b
Map.foldr (Bool -> Bool -> Bool
(&&) forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall a. Ord a => a -> a -> Bool
> Int
0)) Bool
True forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Return whether all objects in the signed multiset have nonpositive
-- multiplicities.
isNegative :: SignedMultiset a -> Bool
isNegative :: forall a. SignedMultiset a -> Bool
isNegative = forall a b k. (a -> b -> b) -> b -> Map k a -> b
Map.foldr (Bool -> Bool -> Bool
(&&) forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall a. Ord a => a -> a -> Bool
< Int
0)) Bool
True forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(1)/. Return the number of members of the signed multiset, i.e., the
-- number of objects that have nonzero multiplicity.
size :: SignedMultiset a -> Int
size :: forall a. SignedMultiset a -> Int
size = forall k a. Map k a -> Int
Map.size forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Return the cardinality of the signed multiset, i.e., the sum of
-- the multiplicities of all objects.
cardinality :: SignedMultiset a -> Int
cardinality :: forall a. SignedMultiset a -> Int
cardinality = forall a b k. (a -> b -> a) -> a -> Map k b -> a
Map.foldl' forall a. Num a => a -> a -> a
(+) Int
0 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(log n)/. Return whether the given object is a member of the signed
-- multiset, i.e., whether the object has nonzero multiplicity.
member :: Ord a => a -> SignedMultiset a -> Bool
member :: forall a. Ord a => a -> SignedMultiset a -> Bool
member a
x = forall k a. Ord k => k -> Map k a -> Bool
Map.member a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(log n)/. Return whether the given object is /not/ a member of the signed
-- multiset, i.e., whether the object has multiplicity zero.
notMember :: Ord a => a -> SignedMultiset a -> Bool
notMember :: forall a. Ord a => a -> SignedMultiset a -> Bool
notMember a
x = forall k a. Ord k => k -> Map k a -> Bool
Map.notMember a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(log n)/. Return the multiplicity of the given object in the signed
-- multiset.
multiplicity :: Ord a => a -> SignedMultiset a -> Int
multiplicity :: forall a. Ord a => a -> SignedMultiset a -> Int
multiplicity a
x = forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault Int
0 a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Return whether the first signed multiset is a submultiset of the
-- second, i.e., whether each object that has nonzero multiplicity @m@ in the
-- first multiset has nonzero multiplicity @n@ with @m <= n@ in the second.
isSubmultisetOf :: Ord a => SignedMultiset a -> SignedMultiset a -> Bool
isSubmultisetOf :: forall a. Ord a => SignedMultiset a -> SignedMultiset a -> Bool
isSubmultisetOf = forall k a b.
Ord k =>
(a -> b -> Bool) -> Map k a -> Map k b -> Bool
Map.isSubmapOfBy forall a. Ord a => a -> a -> Bool
(<=) forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` forall a. SignedMultiset a -> Map a Int
unSMS

--------------------------------------------------------------------------------
-- Combining
--------------------------------------------------------------------------------

-- | /O(n)/. Return the union of two signed multisets. The multiplicity of an
-- object in the returned multiset is the maximum of its nonzero multiplicities
-- in the argument multisets.
union :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset a
union :: forall a.
Ord a =>
SignedMultiset a -> SignedMultiset a -> SignedMultiset a
union = forall a. Map a Int -> SignedMultiset a
SMS forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
`after` (forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith forall a. Ord a => a -> a -> a
max forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` forall a. SignedMultiset a -> Map a Int
unSMS)

-- | /O(n)/. Return the additive union of two signed multisets. The
-- multiplicity of an object in the returned multiset is the sum of its
-- multiplicities in the argument multisets.
additiveUnion :: Ord a =>
                 SignedMultiset a -> SignedMultiset a -> SignedMultiset a
additiveUnion :: forall a.
Ord a =>
SignedMultiset a -> SignedMultiset a -> SignedMultiset a
additiveUnion = forall a. Map a Int -> SignedMultiset a
norm forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
`after` (forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith forall a. Num a => a -> a -> a
(+) forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` forall a. SignedMultiset a -> Map a Int
unSMS)

-- | /O(n)/. Return the intersection of two signed multisets. If an object has
-- nonzero multiplicity in both argument multisets, its multiplicity in the
-- returned multiset is the minimum of its multiplicities in the argument
-- multisets; otherwise, its multiplicity in the returned multiset is zero.
intersection :: Ord a =>
                SignedMultiset a -> SignedMultiset a -> SignedMultiset a
intersection :: forall a.
Ord a =>
SignedMultiset a -> SignedMultiset a -> SignedMultiset a
intersection = forall a. Map a Int -> SignedMultiset a
SMS forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
`after` (forall k a b c.
Ord k =>
(a -> b -> c) -> Map k a -> Map k b -> Map k c
Map.intersectionWith forall a. Ord a => a -> a -> a
min forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` forall a. SignedMultiset a -> Map a Int
unSMS)

--------------------------------------------------------------------------------
-- Memberwise operations
--------------------------------------------------------------------------------

-- | /O(n)/. Return the root of the signed multiset. The multiplicity of an
-- object in the returned multiset is zero if its multiplicity in the argument
-- multiset is zero and 1 otherwise.
root :: SignedMultiset a -> SignedMultiset a
root :: forall a. SignedMultiset a -> SignedMultiset a
root = forall a. Map a Int -> SignedMultiset a
SMS forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b k. (a -> b) -> Map k a -> Map k b
Map.map (forall a b. a -> b -> a
const Int
1) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Return the shadow of the signed multiset. The multiplicity of an
-- object in the returned multiset is the additive inverse of its multiplicity
-- in the argument multiset.
shadow :: SignedMultiset a -> SignedMultiset a
shadow :: forall a. SignedMultiset a -> SignedMultiset a
shadow = forall a. Map a Int -> SignedMultiset a
SMS forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b k. (a -> b) -> Map k a -> Map k b
Map.map forall a. Num a => a -> a
negate forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Return the modulus of the signed multiset. The multiplicity of an
-- object in the returned multiset is the absolute value of its multiplicity in
-- the argument multiset.
modulus :: SignedMultiset a -> SignedMultiset a
modulus :: forall a. SignedMultiset a -> SignedMultiset a
modulus = forall a. Map a Int -> SignedMultiset a
SMS forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b k. (a -> b) -> Map k a -> Map k b
Map.map forall a. Num a => a -> a
abs forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Return the signum of the signed multiset. The multiplicity of an
-- object in the returned multiset is -1 if it has negative multiplicity in the
-- argument multiset, zero if its multiplicity in the argument multiset is zero,
-- and 1 if it has positive multiplicity in the argument multiset.
signum :: SignedMultiset a -> SignedMultiset a
signum :: forall a. SignedMultiset a -> SignedMultiset a
signum = forall a. Map a Int -> SignedMultiset a
SMS forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b k. (a -> b) -> Map k a -> Map k b
Map.map forall a. Num a => a -> a
Prelude.signum forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Return the left-continuous unit step of the signed multiset. The
-- multiplicity of an object in the returned multiset is zero if it has negative
-- multiplicity in the argument multiset, and 1 otherwise.
unitstep :: SignedMultiset a -> SignedMultiset a
unitstep :: forall a. SignedMultiset a -> SignedMultiset a
unitstep = forall a. Map a Int -> SignedMultiset a
norm forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b k. (a -> b) -> Map k a -> Map k b
Map.map forall {a} {a}. (Ord a, Num a, Num a) => a -> a
u forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS
  where
    u :: a -> a
u a
n = if a
n forall a. Ord a => a -> a -> Bool
> a
0 then a
1 else a
0

-- | /O(n)/. Return the additive union of the given number of copies of the
-- signed multiset.
multiply :: Int -> SignedMultiset a -> SignedMultiset a
multiply :: forall a. Int -> SignedMultiset a -> SignedMultiset a
multiply Int
n = forall a. Map a Int -> SignedMultiset a
norm forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b k. (a -> b) -> Map k a -> Map k b
Map.map (Int
n forall a. Num a => a -> a -> a
*) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

--------------------------------------------------------------------------------
-- Traversals
--------------------------------------------------------------------------------

-- | /O(n * log n)/. Apply the given function to all objects of the signed
-- multiset. If the the function maps distinct objects to the same new object,
-- the multiplicity of the new object is the maximum of the nonzero 
-- multiplicities of the two original objects.
map :: Ord b => (a -> b) -> SignedMultiset a -> SignedMultiset b
map :: forall b a.
Ord b =>
(a -> b) -> SignedMultiset a -> SignedMultiset b
map a -> b
f = forall a. Map a Int -> SignedMultiset a
SMS forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysWith forall a. Ord a => a -> a -> a
max a -> b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n * log n)/. Apply the given function to all objects of the signed
-- multiset. If the the function maps distinct objects to the same new object,
-- the multiplicity of the new object is the sum of the multiplicities of the
-- two original objects.
additiveMap :: Ord b => (a -> b) -> SignedMultiset a -> SignedMultiset b
additiveMap :: forall b a.
Ord b =>
(a -> b) -> SignedMultiset a -> SignedMultiset b
additiveMap a -> b
f = forall a. Map a Int -> SignedMultiset a
norm forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysWith forall a. Num a => a -> a -> a
(+) a -> b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Apply the given predicate to the members of the signed multiset and
-- their multiplicities. The returned multiset contains the copies of the
-- members that satisfy the predicate.
filter :: (a -> Int -> Bool) -> SignedMultiset a -> SignedMultiset a
filter :: forall a.
(a -> Int -> Bool) -> SignedMultiset a -> SignedMultiset a
filter a -> Int -> Bool
p = forall a. Map a Int -> SignedMultiset a
SMS forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. (k -> a -> Bool) -> Map k a -> Map k a
Map.filterWithKey a -> Int -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Apply the given predicate to the members of the signed multiset and
-- their multiplicity. The first returned multiset contains the copies of the
-- members that satisfy the predicate, while the second returned multiset
-- contains the copies of the members that do not satisfy the predicate.
partition :: (a -> Int -> Bool) -> SignedMultiset a ->
             (SignedMultiset a, SignedMultiset a)
partition :: forall a.
(a -> Int -> Bool)
-> SignedMultiset a -> (SignedMultiset a, SignedMultiset a)
partition a -> Int -> Bool
p = (forall a. Map a Int -> SignedMultiset a
SMS forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** forall a. Map a Int -> SignedMultiset a
SMS) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
Map.partitionWithKey a -> Int -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Split the signed multiset into a multiset containing the copies of
-- the members with a multiplicity less than or equal to the given number and a
-- multiset containing the copies of the members with a multiplicity greater
-- than the given number.
split :: Int -> SignedMultiset a -> (SignedMultiset a, SignedMultiset a)
split :: forall a.
Int -> SignedMultiset a -> (SignedMultiset a, SignedMultiset a)
split Int
n = forall a.
(a -> Int -> Bool)
-> SignedMultiset a -> (SignedMultiset a, SignedMultiset a)
partition forall {b}. b -> Int -> Bool
p
  where
    p :: b -> Int -> Bool
p = forall a b. a -> b -> a
const (forall a. Ord a => a -> a -> Bool
< Int
n)

-- | /O(n)/. Perform a right-associative fold on the members of the signed
-- multiset and their multiplicities using the given operator and start value.
foldr :: (a -> Int -> b -> b) -> b -> SignedMultiset a -> b
foldr :: forall a b. (a -> Int -> b -> b) -> b -> SignedMultiset a -> b
foldr a -> Int -> b -> b
f b
z = forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey a -> Int -> b -> b
f b
z forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Perform a strict right-associative fold on the members of the
-- signed multiset and their multiplicities using the given operator and start
-- value.
foldr' :: (a -> Int -> b -> b) -> b -> SignedMultiset a -> b
foldr' :: forall a b. (a -> Int -> b -> b) -> b -> SignedMultiset a -> b
foldr' a -> Int -> b -> b
f b
z = forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey' a -> Int -> b -> b
f b
z forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Perform a left-associative fold on the members of the signed
-- multiset and their multiplicities using the given operator and start value.
foldl :: (a -> b -> Int -> a) -> a -> SignedMultiset b -> a
foldl :: forall a b. (a -> b -> Int -> a) -> a -> SignedMultiset b -> a
foldl a -> b -> Int -> a
f a
z = forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey a -> b -> Int -> a
f a
z forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n)/. Perform a strict left-associative fold on the members of the signed
-- multiset and their multiplicities using the given operator and start value.
foldl' :: (a -> b -> Int -> a) -> a -> SignedMultiset b -> a
foldl' :: forall a b. (a -> b -> Int -> a) -> a -> SignedMultiset b -> a
foldl' a -> b -> Int -> a
f a
z = forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey' a -> b -> Int -> a
f a
z forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

--------------------------------------------------------------------------------
-- Conversion
--------------------------------------------------------------------------------

-- | /O(n)/. Convert the signed multiset to a list that associates all members
-- of the multiset with their multiplicity.
toList :: SignedMultiset a -> [(a, Int)]
toList :: forall a. SignedMultiset a -> [(a, Int)]
toList = forall k a. Map k a -> [(k, a)]
Map.toList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SignedMultiset a -> Map a Int
unSMS

-- | /O(n + k)/ (with /k/ the combined length of the returned lists). Return two
-- lists, such that: for each object with a positive multiplicity @m@ in the
-- signed multiset, the first list contains @m@ copies and the second list
-- contains no copies of the object; for each object with a negative
-- multiplicity @-n@, the first list contains no and the second list contains
-- @n@ copies of the object; and for each object with zero multiplicity,
-- neither list contains a copy of the object.
toLists :: SignedMultiset a -> ([a], [a])
toLists :: forall a. SignedMultiset a -> ([a], [a])
toLists = forall a b. (a -> Int -> b -> b) -> b -> SignedMultiset a -> b
foldr forall {a}. a -> Int -> ([a], [a]) -> ([a], [a])
f forall {a} {a}. ([a], [a])
z
  where
    z :: ([a], [a])
z              = ([], [])
    f :: a -> Int -> ([a], [a]) -> ([a], [a])
f a
x Int
n ([a]
xs, [a]
ys) =
      if Int
n forall a. Ord a => a -> a -> Bool
> Int
0 then (forall a. Int -> a -> [a]
replicate Int
n a
x forall a. [a] -> [a] -> [a]
++ [a]
xs, [a]
ys) else ([a]
xs, forall a. Int -> a -> [a]
replicate (- Int
n) a
x forall a. [a] -> [a] -> [a]
++ [a]
ys)

-- | /O(k * log n)/ (with /k/ the length of the argument list). Construct a
-- signed multiset from a list of object/multiplicity pairs.
fromList :: Ord a => [(a, Int)] -> SignedMultiset a
fromList :: forall a. Ord a => [(a, Int)] -> SignedMultiset a
fromList = forall a. Map a Int -> SignedMultiset a
norm forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith forall a. Num a => a -> a -> a
(+) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (a -> Bool) -> [a] -> [a]
Prelude.filter ((forall a. Eq a => a -> a -> Bool
/= Int
0) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> b
snd)

-- | /O(k * log n)/ (with /k/ the combined length of the argument lists).
-- Construct a signed multiset by, starting from the empty multiset, inserting
-- copies of objects from the first argument list and deleting copies of objects
-- from the second argument list.
fromLists :: Ord a => [a] -> [a] -> SignedMultiset a
fromLists :: forall a. Ord a => [a] -> [a] -> SignedMultiset a
fromLists = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Prelude.foldr forall a. Ord a => a -> SignedMultiset a -> SignedMultiset a
delete forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Prelude.foldr forall a. Ord a => a -> SignedMultiset a -> SignedMultiset a
insert forall a. SignedMultiset a
empty

--------------------------------------------------------------------------------
-- Additive wrapper
--------------------------------------------------------------------------------

-- | An element of the free abelian group on @a@.
newtype Additive a = Additive {forall a. Additive a -> SignedMultiset a
getAdditive :: SignedMultiset a}
  deriving (Additive a -> Additive a -> Bool
forall a. Ord a => Additive a -> Additive a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Additive a -> Additive a -> Bool
$c/= :: forall a. Ord a => Additive a -> Additive a -> Bool
== :: Additive a -> Additive a -> Bool
$c== :: forall a. Ord a => Additive a -> Additive a -> Bool
Eq, Additive a -> Additive a -> Bool
Additive a -> Additive a -> Ordering
Additive a -> Additive a -> Additive a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (Additive a)
forall a. Ord a => Additive a -> Additive a -> Bool
forall a. Ord a => Additive a -> Additive a -> Ordering
forall a. Ord a => Additive a -> Additive a -> Additive a
min :: Additive a -> Additive a -> Additive a
$cmin :: forall a. Ord a => Additive a -> Additive a -> Additive a
max :: Additive a -> Additive a -> Additive a
$cmax :: forall a. Ord a => Additive a -> Additive a -> Additive a
>= :: Additive a -> Additive a -> Bool
$c>= :: forall a. Ord a => Additive a -> Additive a -> Bool
> :: Additive a -> Additive a -> Bool
$c> :: forall a. Ord a => Additive a -> Additive a -> Bool
<= :: Additive a -> Additive a -> Bool
$c<= :: forall a. Ord a => Additive a -> Additive a -> Bool
< :: Additive a -> Additive a -> Bool
$c< :: forall a. Ord a => Additive a -> Additive a -> Bool
compare :: Additive a -> Additive a -> Ordering
$ccompare :: forall a. Ord a => Additive a -> Additive a -> Ordering
Ord, Int -> Additive a -> ShowS
forall a. Show a => Int -> Additive a -> ShowS
forall a. Show a => [Additive a] -> ShowS
forall a. Show a => Additive a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Additive a] -> ShowS
$cshowList :: forall a. Show a => [Additive a] -> ShowS
show :: Additive a -> String
$cshow :: forall a. Show a => Additive a -> String
showsPrec :: Int -> Additive a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Additive a -> ShowS
Show, ReadPrec [Additive a]
ReadPrec (Additive a)
ReadS [Additive a]
forall a. (Ord a, Read a) => ReadPrec [Additive a]
forall a. (Ord a, Read a) => ReadPrec (Additive a)
forall a. (Ord a, Read a) => Int -> ReadS (Additive a)
forall a. (Ord a, Read a) => ReadS [Additive a]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [Additive a]
$creadListPrec :: forall a. (Ord a, Read a) => ReadPrec [Additive a]
readPrec :: ReadPrec (Additive a)
$creadPrec :: forall a. (Ord a, Read a) => ReadPrec (Additive a)
readList :: ReadS [Additive a]
$creadList :: forall a. (Ord a, Read a) => ReadS [Additive a]
readsPrec :: Int -> ReadS (Additive a)
$creadsPrec :: forall a. (Ord a, Read a) => Int -> ReadS (Additive a)
Read)

-- | Semigroup under 'additiveUnion'.
instance Ord a => Semigroup (Additive a) where
  <> :: Additive a -> Additive a -> Additive a
(<>) = forall a. SignedMultiset a -> Additive a
Additive forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
`after` (forall a.
Ord a =>
SignedMultiset a -> SignedMultiset a -> SignedMultiset a
additiveUnion forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` forall a. Additive a -> SignedMultiset a
getAdditive)

-- | Monoid under 'additiveUnion'.
instance Ord a => Monoid (Additive a) where
  mempty :: Additive a
mempty  = forall a. SignedMultiset a -> Additive a
Additive forall a. SignedMultiset a
empty
  mappend :: Additive a -> Additive a -> Additive a
mappend = forall a. Semigroup a => a -> a -> a
(<>)

--------------------------------------------------------------------------------
-- Utilities
--------------------------------------------------------------------------------

after :: (c -> d) -> (a -> b -> c) -> a -> b -> d
after :: forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
after c -> d
f a -> b -> c
(.+.) a
x b
y = c -> d
f (a
x a -> b -> c
.+. b
y)