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

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

Minimal complete definition

Nothing

Methods

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