Data.Discrimination.Grouping

Documentation

newtype Group a

Discriminator

Constructors

Group

Fields

runGroup :: forall b. [(a, b)] -> [[b]]

Instances

Divisible Group

Decidable Group

Contravariant Group

Discriminating Group

Monoid (Group a)

Typeable (* -> *) Group

class Grouping a where

Eq equipped with a compatible stable unordered discriminator.

Minimal complete definition

Nothing

Methods

grouping :: Group a

For every surjection f,

contramap f grouping ≡ grouping

Instances

Grouping Bool

Grouping Int

Grouping Int8

Grouping Int16

Grouping Int32

Grouping Int64

Grouping Word

Grouping Word8

Grouping Word16

Grouping Word32

Grouping Word64

Grouping Void

Grouping a => Grouping [a]

(Grouping a, Integral a) => Grouping (Ratio a)

Grouping a => Grouping (Complex a)

Grouping a => Grouping (Maybe a)

(Grouping a, Grouping b) => Grouping (Either a b)

(Grouping a, Grouping b) => Grouping (a, b)

(Grouping a, Grouping b, Grouping c) => Grouping (a, b, c)

(Grouping1 f, Grouping1 g, Grouping a) => Grouping (Compose f g a)

(Grouping a, Grouping b, Grouping c, Grouping d) => Grouping (a, b, c, d)

class Grouping1 f where

Minimal complete definition

Nothing

Methods

grouping1 :: Group a -> Group (f a)

Instances

Grouping1 []

Grouping1 Complex

Grouping1 Maybe

Grouping a => Grouping1 (Either a)

Grouping a => Grouping1 ((,) a)

(Grouping a, Grouping b) => Grouping1 ((,,) a b)

(Grouping1 f, Grouping1 g) => Grouping1 (Compose f g)

(Grouping a, Grouping b, Grouping c) => Grouping1 ((,,,) a b c)

Combinators

nub :: Grouping a => [a] -> [a]

O(n). This upgrades nub from Data.List from O(n^2) to O(n) by using unordered discrimination.

nub = nubWith id
nub as = head <$> group as

nubWith :: Grouping b => (a -> b) -> [a] -> [a]

O(n). nub with a Schwartzian transform.

nubWith f as = head <$> groupWith f as

group :: Grouping a => [a] -> [[a]]

O(n). Similar to group, except we do not require groups to be clustered.

This combinator still operates in linear time, at the expense of productivity.

The result equivalence classes are _not_ sorted, but the grouping is stable.

group = groupWith id

groupWith :: Grouping b => (a -> b) -> [a] -> [[a]]

O(n). This is a replacement for groupWith using discrimination.

The result equivalence classes are _not_ sorted, but the grouping is stable.

groupingEq :: Grouping a => a -> a -> Bool

Valid definition for (==) in terms of Grouping.

Internals

groupingBag :: Foldable f => Group k -> Group (f k)

Construct an stable unordered discriminator that partitions into equivalence classes based on the equivalence of keys as a multiset.

groupingSet :: Foldable f => Group k -> Group (f k)

Construct an stable unordered discriminator that partitions into equivalence classes based on the equivalence of keys as a set.

groupingShort :: Group Int

Shared bucket set for small integers

groupingNat :: Int -> Group Int

Perform stable unordered discrimination by bucket.

This reuses arrays unlike the more obvious ST implementation, so it wins by a huge margin in a race, especially when we have a large keyspace, sparsely used, with low contention. This will leak a number of arrays equal to the maximum concurrent contention for this resource. If this becomes a bottleneck we can make multiple stacks of working pads and index the stack with the hash of the current thread id to reduce contention at the expense of taking more memory.

You should create a thunk that holds the discriminator from groupingNat n for a known n and then reuse it.