HORIZON HASKELLDocslts/ghc-10.0.x8fef28d2026-11-02Search packagesCtrl K
Theme: |

GHC 10.0.0.20260917 · lts/ghc-10.0.x · 8fef28d · 2026-11-02

ModuleAgda-2.8.0.2Haskell2010

Agda.Utils.Bag

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

Contents
  1. Query
  2. Construction
  3. Destruction
  4. Traversal
Synopsis
  • PackageAgda-2.8.0.2
  • Exports20
  • LanguageHaskell2010
  • LicenceMIT
  • SourceBag.hs
newtypenewtype Bag a
Source#

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

Constructors

  • Bag
    • bag :: Map a (NonEmpty 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.8.0.2 · Agda.Utils.Bag
  • Eq a => Eq (Bag a)Defined in Agda-2.8.0.2 · Agda.Utils.Bag
  • Ord a => Ord (Bag a)Defined in Agda-2.8.0.2 · Agda.Utils.Bag
  • Show a => Show (Bag a)Defined in Agda-2.8.0.2 · Agda.Utils.Bag
  • Ord a => Semigroup (Bag a)Defined in Agda-2.8.0.2 · Agda.Utils.Bag
  • Ord a => Monoid (Bag a)Defined in Agda-2.8.0.2 · Agda.Utils.Bag
  • Null (Bag a)Defined in Agda-2.8.0.2 · Agda.Utils.Null

Query

valuesize :: Bag a -> Int
Source#

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

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

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

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

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

Construction

Destruction

valuekeys :: Bag a -> [a]
Source#

Returns the bag without duplicates.

Traversal