Safe Haskell	Trustworthy
Language	Haskell2010

Data.Discrimination.Grouping

Contents

Synopsis

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

For every surjection f,

contramap f grouping ≡ grouping

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

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.

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

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

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

Semantically,

grouping = hashing <> grouping