discrimination-0.4.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

Instances details
 Source # Instance detailsDefined in Data.Discrimination.Grouping Methodscontramap :: (a -> b) -> Group b -> Group a #(>$) :: b -> Group b -> Group a # Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsdivide :: (a -> (b, c)) -> Group b -> Group c -> Group a # Source # Instance detailsDefined in Data.Discrimination.Grouping Methodslose :: (a -> Void) -> Group a #choose :: (a -> Either b c) -> Group b -> Group c -> Group a # Source # Instance detailsDefined in Data.Discrimination.Class Methodsdisc :: Group a -> [(a, b)] -> [[b]] Source # Source # Instance detailsDefined 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 detailsDefined in Data.Discrimination.Grouping Methodsmempty :: 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. 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 For every surjection f, contramap f grouping ≡ grouping  #### Instances Instances details  Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Grouping () Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Grouping a => Grouping [a] Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping :: Group [a] Source # Grouping a => Grouping (Maybe a) Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Grouping a => Grouping (Ratio a) Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Grouping a => Grouping (Complex a) Source # Instance detailsDefined in Data.Discrimination.Grouping Methods Grouping a => Grouping (NonEmpty a) Source # Instance detailsDefined in Data.Discrimination.Grouping Methods (Grouping a, Grouping b) => Grouping (Either a b) Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping :: Group (Either a b) Source # (Grouping a, Grouping b) => Grouping (a, b) Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping :: Group (a, b) Source # (Grouping a, Grouping b, Grouping c) => Grouping (a, b, c) Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping :: Group (a, b, c) Source # (Grouping a, Grouping b, Grouping c, Grouping d) => Grouping (a, b, c, d) Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping :: Group (a, b, c, d) Source # (Grouping1 f, Grouping1 g, Grouping a) => Grouping (Compose f g a) Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping :: Group (Compose f g a) Source # class 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  Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping1 :: Group a -> Group [a] Source # Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping1 :: Group a -> Group (Maybe a) Source # Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping1 :: Group a -> Group (Complex a) Source # Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping1 :: Group a -> Group (NonEmpty a) Source # Grouping a => Grouping1 (Either a) Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping1 :: Group a0 -> Group (Either a a0) Source # Grouping a => Grouping1 ((,) a) Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping1 :: Group a0 -> Group (a, a0) Source # (Grouping a, Grouping b) => Grouping1 ((,,) a b) Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping1 :: Group a0 -> Group (a, b, a0) Source # (Grouping a, Grouping b, Grouping c) => Grouping1 ((,,,) a b c) Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping1 :: Group a0 -> Group (a, b, c, a0) Source # (Grouping1 f, Grouping1 g) => Grouping1 (Compose f g) Source # Instance detailsDefined in Data.Discrimination.Grouping Methodsgrouping1 :: 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