discrimination-0.1: Fast generic linear-time sorting, joins and container construction.

Safe HaskellTrustworthy
LanguageHaskell2010

Data.Discrimination.Grouping

Contents

Synopsis

Documentation

newtype Group a Source

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

grouping :: Group a Source

For every surjection f,

contramap f groupinggrouping

class Grouping1 f where Source

Minimal complete definition

Nothing

Methods

grouping1 :: Group a -> Group (f a) 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.

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

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

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

Internals

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