Safe Haskell	Trustworthy
Language	Haskell2010

Data.Discrimination.Grouping

Contents

Combinators
Internals

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

Divisible Group Source #
Methods divide :: (a -> (b, c)) -> Group b -> Group c -> Group a # conquer :: Group a #
Decidable Group Source #
Methods lose :: (a -> Void) -> Group a # choose :: (a -> Either b c) -> Group b -> Group c -> Group a #
Contravariant Group Source #
Methods contramap :: (a -> b) -> Group b -> Group a # (>$) :: b -> Group b -> Group a #
Discriminating Group Source #
Methods disc :: Group a -> [(a, b)] -> [[b]] Source #
Semigroup (Group a) Source #
Methods (<>) :: Group a -> Group a -> Group a # sconcat :: NonEmpty (Group a) -> Group a # stimes :: Integral b => b -> Group a -> Group a #
Monoid (Group a) Source #
Methods mempty :: Group a # mappend :: Group a -> Group a -> Group a # mconcat :: [Group a] -> Group a #

class Grouping a where Source #

Eq equipped with a compatible stable unordered discriminator.

Methods

grouping :: Group a Source #

For every surjection f,

contramap f grouping ≡ grouping

grouping :: Deciding Grouping a => Group a Source #

For every surjection f,

contramap f grouping ≡ grouping

Instances

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

class Grouping1 f where Source #

Methods

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

grouping1 :: Deciding1 Grouping f => Group a -> Group (f a) Source #

Instances

Grouping1 [] Source #
Methods grouping1 :: Group a -> Group [a] Source #
Grouping1 Maybe Source #
Methods grouping1 :: Group a -> Group (Maybe a) Source #
Grouping1 Complex Source #
Methods grouping1 :: Group a -> Group (Complex a) Source #
Grouping a => Grouping1 (Either a) Source #
Methods grouping1 :: Group a -> Group (Either a a) Source #
Grouping a => Grouping1 ((,) a) Source #
Methods grouping1 :: Group a -> Group (a, a) Source #
(Grouping a, Grouping b) => Grouping1 ((,,) a b) Source #
Methods grouping1 :: Group a -> Group (a, b, a) Source #
(Grouping a, Grouping b, Grouping c) => Grouping1 ((,,,) a b c) Source #
Methods grouping1 :: Group a -> Group (a, b, c, a) Source #
(Grouping1 f, Grouping1 g) => Grouping1 (Compose * * f g) Source #
Methods grouping1 :: Group a -> Group (Compose * * f g 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