HORIZON HASKELLDocslts/ghc-9.10.xc74966e2026-09-27Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · c74966e · 2026-09-27

ModuleAgda-2.7.0.1Haskell2010

Agda.Utils.Bag

A simple overlay over Data.Map to manage unordered sets with duplicates.

  • 1 type
  • 19 values
  • PackageAgda-2.7.0.1
  • Exports20
  • LanguageHaskell2010
  • LicenceMIT
  • SourceBag.hs
newtypenewtype Bag a
#

A set with duplicates. Faithfully stores elements which are equal with regard to (==).

Constructors

  • Bag
    • bag :: Map a [a]

      The list contains all occurrences of a (not just the duplicates!). Hence, the invariant: the list is never empty.

Instances7Foldable, Eq, Ord, Show, Semigroup, Monoid, …
  • Foldable BagDefined in Agda-2.7.0.1 · Agda.Utils.Bag
  • Eq a => Eq (Bag a)Defined in Agda-2.7.0.1 · Agda.Utils.Bag
  • Ord a => Ord (Bag a)Defined in Agda-2.7.0.1 · Agda.Utils.Bag
  • Show a => Show (Bag a)Defined in Agda-2.7.0.1 · Agda.Utils.Bag
  • Ord a => Semigroup (Bag a)Defined in Agda-2.7.0.1 · Agda.Utils.Bag
  • Ord a => Monoid (Bag a)Defined in Agda-2.7.0.1 · Agda.Utils.Bag
  • Null (Bag a)Defined in Agda-2.7.0.1 · Agda.Utils.Null

Query

6 declarations
valuesize :: Bag a -> Int
#

Number of elements in the bag. Duplicates count. O(n).

value(!) :: Ord a => Bag a -> a -> [a]
#

(bag ! a) finds all elements equal to a. O(log n). Total function, returns [] if none are.

valuecount :: Ord a => a -> Bag a -> Int
#

Return the multiplicity of the given element. O(log n + count _ _).

Construction

6 declarations
valueinsert :: Ord a => a -> Bag a -> Bag a
#
insert a b = union b (singleton a)
valuefromList :: Ord a => [a] -> Bag a
#
fromList = unions . map singleton

Destruction

5 declarations
valuegroups :: Bag a -> [[a]]
#

Returns the elements of the bag, grouped by equality (==).

valuetoList :: Bag a -> [a]
#

Returns the bag, with duplicates.

valuekeys :: Bag a -> [a]
#

Returns the bag without duplicates.

valueelems :: Bag a -> [a]
#

Returns the bag, with duplicates.

Traversal

2 declarations