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

Data.Discrimination.Grouping

Contents

Synopsis

# Documentation

newtype Group a Source

Productive Stable Unordered Discriminator

Constructors

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

Instances

 Source Source Source Source Monoid (Group a) Source 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

 Source Source Source Source Source Source Source Source Source Source Source Source 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

class Grouping1 f where Source

Minimal complete definition

Nothing

Methods

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

Instances

 Source Source 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.

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
```