Safe Haskell	Trustworthy
Language	Haskell2010

Data.Discrimination.Grouping

Contents

Combinators
Internals

Synopsis

newtype Group a = Group {
- getGroup :: forall m b. PrimMonad m => (b -> m (b -> m ())) -> m (a -> b -> m ())
}
class Eq a => Grouping a where
- grouping :: Group a
class Eq1 f => Grouping1 f where
- grouping1 :: Group a -> Group (f a)
nub :: Grouping a => [a] -> [a]
nubWith :: Grouping b => (a -> b) -> [a] -> [a]
group :: Grouping a => [a] -> [[a]]
groupWith :: Grouping b => (a -> b) -> [a] -> [[a]]
groupingEq :: Grouping a => a -> a -> Bool
runGroup :: Group a -> [(a, b)] -> [[b]]
hashing :: Hashable a => Group a

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

Instances details

Contravariant Group Source #
Instance details Defined in Data.Discrimination.Grouping Methods contramap :: (a -> b) -> Group b -> Group a # (>$) :: b -> Group b -> Group a #
Divisible Group Source #
Instance details Defined in Data.Discrimination.Grouping Methods divide :: (a -> (b, c)) -> Group b -> Group c -> Group a # conquer :: Group a #
Decidable Group Source #
Instance details Defined in Data.Discrimination.Grouping Methods lose :: (a -> Void) -> Group a # choose :: (a -> Either b c) -> Group b -> Group c -> Group a #
Discriminating Group Source #
Instance details Defined in Data.Discrimination.Class Methods disc :: Group a -> [(a, b)] -> [[b]] Source #
Semigroup (Group a) Source #
Instance details Defined in Data.Discrimination.Grouping 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 #
Instance details Defined in Data.Discrimination.Grouping Methods mempty :: Group a # mappend :: Group a -> Group a -> Group a # mconcat :: [Group a] -> Group a #

class Eq a => Grouping a where Source #

Eq equipped with a compatible stable unordered discriminator.

Law:

groupingEq x y ≡ (x == y)

Note: Eq is a moral super class of Grouping. It isn't because of some missing instances.

Minimal complete definition

Nothing

Methods

grouping :: Group a Source #

For every surjection f,

contramap f grouping ≡ grouping

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

Instances

Instances details

Grouping Bool Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Bool Source #
Grouping Char Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Char Source #
Grouping Int Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Int Source #
Grouping Int8 Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Int8 Source #
Grouping Int16 Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Int16 Source #
Grouping Int32 Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Int32 Source #
Grouping Int64 Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Int64 Source #
Grouping Integer Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Integer Source #
Grouping Natural Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Natural Source #
Grouping Ordering Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Ordering Source #
Grouping Word Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Word Source #
Grouping Word8 Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Word8 Source #
Grouping Word16 Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Word16 Source #
Grouping Word32 Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Word32 Source #
Grouping Word64 Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Word64 Source #
Grouping () Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group () Source #
Grouping Void Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group Void Source #
Grouping a => Grouping [a] Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group [a] Source #
Grouping a => Grouping (Maybe a) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group (Maybe a) Source #
Grouping a => Grouping (Ratio a) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group (Ratio a) Source #
Grouping a => Grouping (Complex a) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group (Complex a) Source #
Grouping a => Grouping (NonEmpty a) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group (NonEmpty a) Source #
(Grouping a, Grouping b) => Grouping (Either a b) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group (Either a b) Source #
(Grouping a, Grouping b) => Grouping (a, b) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group (a, b) Source #
(Grouping a, Grouping b, Grouping c) => Grouping (a, b, c) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group (a, b, c) Source #
(Grouping a, Grouping b, Grouping c, Grouping d) => Grouping (a, b, c, d) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group (a, b, c, d) Source #
(Grouping1 f, Grouping1 g, Grouping a) => Grouping (Compose f g a) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping :: Group (Compose f g a) Source #

class Eq1 f => Grouping1 f where Source #

Minimal complete definition

Nothing

Methods

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

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

Instances

Instances details

Grouping1 [] Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping1 :: Group a -> Group [a] Source #
Grouping1 Maybe Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping1 :: Group a -> Group (Maybe a) Source #
Grouping1 Complex Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping1 :: Group a -> Group (Complex a) Source #
Grouping1 NonEmpty Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping1 :: Group a -> Group (NonEmpty a) Source #
Grouping a => Grouping1 (Either a) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping1 :: Group a0 -> Group (Either a a0) Source #
Grouping a => Grouping1 ((,) a) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping1 :: Group a0 -> Group (a, a0) Source #
(Grouping a, Grouping b) => Grouping1 ((,,) a b) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping1 :: Group a0 -> Group (a, b, a0) Source #
(Grouping a, Grouping b, Grouping c) => Grouping1 ((,,,) a b c) Source #
Instance details Defined in Data.Discrimination.Grouping Methods grouping1 :: Group a0 -> Group (a, b, c, a0) Source #
(Grouping1 f, Grouping1 g) => Grouping1 (Compose f g) Source #
Instance details Defined in Data.Discrimination.Grouping 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