Data.Discrimination.Grouping

Documentation

newtype Group a

Productive Stable Unordered Discriminator

Constructors

Group

Fields

• getGroup :: forall m b. PrimMonad m => (b -> m (b -> m ())) -> m (a -> b -> m ())

Instances

Divisible Group

Methods

divide :: (a -> (b, c)) -> Group b -> Group c -> Group a

conquer :: Group a

Decidable Group

Methods

lose :: (a -> Void) -> Group a

choose :: (a -> Either b c) -> Group b -> Group c -> Group a

Contravariant Group

Methods

contramap :: (a -> b) -> Group b -> Group a

(>$) :: b -> Group b -> Group a

Discriminating Group

Methods

disc :: Group a -> [(a, b)] -> [[b]]

Semigroup (Group a)

Methods

(<>) :: Group a -> Group a -> Group a

sconcat :: NonEmpty (Group a) -> Group a

stimes :: Integral b => b -> Group a -> Group a

Monoid (Group a)

Methods

mempty :: Group a

mappend :: Group a -> Group a -> Group a

mconcat :: [Group a] -> Group a

class Grouping a where

Eq equipped with a compatible stable unordered discriminator.

Methods

grouping :: Group a

For every surjection f,

contramap f grouping ≡ grouping

grouping :: Deciding Grouping a => Group a

For every surjection f,

contramap f grouping ≡ grouping

Instances

Grouping Bool

Methods

grouping :: Group Bool

Grouping Char

Methods

grouping :: Group Char

Grouping Int

Methods

grouping :: Group Int

Grouping Int8

Methods

grouping :: Group Int8

Grouping Int16

Methods

grouping :: Group Int16

Grouping Int32

Methods

grouping :: Group Int32

Grouping Int64

Methods

grouping :: Group Int64

Grouping Word

Methods

grouping :: Group Word

Grouping Word8

Methods

grouping :: Group Word8

Grouping Word16

Methods

grouping :: Group Word16

Grouping Word32

Methods

grouping :: Group Word32

Grouping Word64

Methods

grouping :: Group Word64

Grouping Void

Methods

grouping :: Group Void

Grouping a => Grouping [a]

Methods

grouping :: Group [a]

Grouping a => Grouping (Maybe a)

Methods

grouping :: Group (Maybe a)

Grouping a => Grouping (Ratio a)

Methods

grouping :: Group (Ratio a)

Grouping a => Grouping (Complex a)

Methods

grouping :: Group (Complex a)

(Grouping a, Grouping b) => Grouping (Either a b)

Methods

grouping :: Group (Either a b)

(Grouping a, Grouping b) => Grouping (a, b)

Methods

grouping :: Group (a, b)

(Grouping a, Grouping b, Grouping c) => Grouping (a, b, c)

Methods

grouping :: Group (a, b, c)

(Grouping a, Grouping b, Grouping c, Grouping d) => Grouping (a, b, c, d)

Methods

grouping :: Group (a, b, c, d)

(Grouping1 f, Grouping1 g, Grouping a) => Grouping (Compose * * f g a)

Methods

grouping :: Group (Compose * * f g a)

class Grouping1 f where

Methods

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

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

Instances

Grouping1 []

Methods

grouping1 :: Group a -> Group [a]

Grouping1 Maybe

Methods

grouping1 :: Group a -> Group (Maybe a)

Grouping1 Complex

Methods

grouping1 :: Group a -> Group (Complex a)

Grouping a => Grouping1 (Either a)

Methods

grouping1 :: Group a -> Group (Either a a)

Grouping a => Grouping1 ((,) a)

Methods

grouping1 :: Group a -> Group (a, a)

(Grouping a, Grouping b) => Grouping1 ((,,) a b)

Methods

grouping1 :: Group a -> Group (a, b, a)

(Grouping a, Grouping b, Grouping c) => Grouping1 ((,,,) a b c)

Methods

grouping1 :: Group a -> Group (a, b, c, a)

(Grouping1 f, Grouping1 g) => Grouping1 (Compose * * f g)

Methods

grouping1 :: Group a -> Group (Compose * * f g a)

Combinators

nub :: Grouping a => [a] -> [a]

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]

O(n). Online nub with a Schwartzian transform.

nubWith f as = head <$> groupWith f as

group :: Grouping a => [a] -> [[a]]

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

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

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

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

Internals

hashing :: Hashable a => Group a

This may be useful for pragmatically accelerating a grouping structure by preclassifying by a hash function

Semantically,

grouping = hashing <> grouping