Safe Haskell	Trustworthy
Language	Haskell2010

Data.Discrimination.Grouping

Contents

Synopsis

Documentation

Productive Stable Unordered Discriminator

Constructors

Group
Fields getGroup :: forall m b. PrimMonad m => (b -> m (b -> m ())) -> m (a -> b -> m ())

Instances

Contravariant Group Source
Divisible Group Source
Decidable Group Source
Discriminating Group Source
Monoid (Group a) Source

class Grouping a where Source

Eq equipped with a compatible stable unordered discriminator.

Minimal complete definition

Nothing

Methods

For every surjection f,

contramap f grouping ≡ grouping

Instances

Grouping Bool Source
Grouping Int Source
Grouping Int8 Source
Grouping Int16 Source
Grouping Int32 Source
Grouping Int64 Source
Grouping Word Source
Grouping Word8 Source
Grouping Word16 Source
Grouping Word32 Source
Grouping Word64 Source
Grouping Void Source
Grouping a => Grouping [a] Source
(Grouping a, Integral a) => Grouping (Ratio a) Source
Grouping a => Grouping (Complex a) Source
Grouping a => Grouping (Maybe a) Source
(Grouping a, Grouping b) => Grouping (Either a b) Source
(Grouping a, Grouping b) => Grouping (a, b) Source
(Grouping a, Grouping b, Grouping c) => Grouping (a, b, c) Source
(Grouping1 f, Grouping1 g, Grouping a) => Grouping (Compose f g a) Source
(Grouping a, Grouping b, Grouping c, Grouping d) => Grouping (a, b, c, d) Source

Minimal complete definition

Nothing

Methods

Instances

Grouping1 [] Source
Grouping1 Complex Source
Grouping1 Maybe Source
Grouping a => Grouping1 (Either a) Source
Grouping a => Grouping1 ((,) a) Source
(Grouping a, Grouping b) => Grouping1 ((,,) a b) Source
(Grouping1 f, Grouping1 g) => Grouping1 (Compose f g) Source
(Grouping a, Grouping b, Grouping c) => Grouping1 ((,,,) a b c) Source

Combinators

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

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

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

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

O(n). Online nub with a Schwartzian transform.

nubWith f as = head <$> groupWith f as

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

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 storing history.

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

group = groupWith id

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

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

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

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

runGroup :: Group a -> [(a, b)] -> [[b]] Source

hashing :: Hashable a => Group a Source

This may be useful for pragmatically accelerating a grouping structure by preclassifying by a hash function

Semantically,

grouping = hashing <> grouping