discrimination-0.4.1: Fast generic linear-time sorting, joins and container construction.

Data.Discrimination

Synopsis

# Discrimination

class Decidable f => Discriminating f where Source #

Methods

disc :: f a -> [(a, b)] -> [[b]] Source #

#### Instances

Instances details
 Source # Instance detailsDefined in Data.Discrimination.Class Methodsdisc :: Group a -> [(a, b)] -> [[b]] Source # Source # Instance detailsDefined in Data.Discrimination.Class Methodsdisc :: Sort a -> [(a, b)] -> [[b]] Source #

# Unordered

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 # 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. runGroup :: Group a -> [(a, b)] -> [[b]] Source # groupingEq :: Grouping a => a -> a -> Bool Source # Valid definition for (==) in terms of Grouping. # Ordered newtype Sort a Source # Stable Ordered Discriminator Constructors  Sort FieldsrunSort :: forall b. [(a, b)] -> [[b]] #### Instances Instances details  Source # Instance detailsDefined in Data.Discrimination.Sorting Methodscontramap :: (a -> b) -> Sort b -> Sort a #(>$) :: b -> Sort b -> Sort a # Source # Instance detailsDefined in Data.Discrimination.Sorting Methodsdivide :: (a -> (b, c)) -> Sort b -> Sort c -> Sort a #conquer :: Sort a # Source # Instance detailsDefined in Data.Discrimination.Sorting Methodslose :: (a -> Void) -> Sort a #choose :: (a -> Either b c) -> Sort b -> Sort c -> Sort a # Source # Instance detailsDefined in Data.Discrimination.Class Methodsdisc :: Sort a -> [(a, b)] -> [[b]] Source # Source # Instance detailsDefined in Data.Discrimination.Sorting Methods(<>) :: Sort a -> Sort a -> Sort a #sconcat :: NonEmpty (Sort a) -> Sort a #stimes :: Integral b => b -> Sort a -> Sort a # Monoid (Sort a) Source # Instance detailsDefined in Data.Discrimination.Sorting Methodsmempty :: Sort a #mappend :: Sort a -> Sort a -> Sort a #mconcat :: [Sort a] -> Sort a #

class Grouping a => Sorting a where Source #

Ord equipped with a compatible stable, ordered discriminator.

Law:

sortingCompare x y ≡ compare x y


Minimal complete definition

Nothing

Methods

For every strictly monotone-increasing function f:

contramap f sorting ≡ sorting


default sorting :: Deciding Sorting a => Sort a Source #

#### Instances

Instances details
 Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Sorting () Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Sorting a => Sorting [a] Source # Instance detailsDefined in Data.Discrimination.Sorting Methodssorting :: Sort [a] Source # Sorting a => Sorting (Maybe a) Source # Instance detailsDefined in Data.Discrimination.Sorting Methods Sorting a => Sorting (NonEmpty a) Source # Instance detailsDefined in Data.Discrimination.Sorting Methods (Sorting a, Sorting b) => Sorting (Either a b) Source # Instance detailsDefined in Data.Discrimination.Sorting Methodssorting :: Sort (Either a b) Source # (Sorting a, Sorting b) => Sorting (a, b) Source # Instance detailsDefined in Data.Discrimination.Sorting Methodssorting :: Sort (a, b) Source # (Sorting a, Sorting b, Sorting c) => Sorting (a, b, c) Source # Instance detailsDefined in Data.Discrimination.Sorting Methodssorting :: Sort (a, b, c) Source # (Sorting a, Sorting b, Sorting c, Sorting d) => Sorting (a, b, c, d) Source # Instance detailsDefined in Data.Discrimination.Sorting Methodssorting :: Sort (a, b, c, d) Source # (Sorting1 f, Sorting1 g, Sorting a) => Sorting (Compose f g a) Source # Instance detailsDefined in Data.Discrimination.Sorting Methodssorting :: Sort (Compose f g a) Source #

class Grouping1 f => Sorting1 f where Source #

Minimal complete definition

Nothing

Methods

sorting1 :: Sort a -> Sort (f a) Source #

default sorting1 :: Deciding1 Sorting f => Sort a -> Sort (f a) Source #

#### Instances

Instances details
 Sorting1 [] Source # Instance detailsDefined in Data.Discrimination.Sorting Methodssorting1 :: Sort a -> Sort [a] Source # Source # Instance detailsDefined in Data.Discrimination.Sorting Methodssorting1 :: Sort a -> Sort (Maybe a) Source # Source # Instance detailsDefined in Data.Discrimination.Sorting Methodssorting1 :: Sort a -> Sort (NonEmpty a) Source # Sorting a => Sorting1 (Either a) Source # Instance detailsDefined in Data.Discrimination.Sorting Methodssorting1 :: Sort a0 -> Sort (Either a a0) Source # (Sorting1 f, Sorting1 g) => Sorting1 (Compose f g) Source # Instance detailsDefined in Data.Discrimination.Sorting Methodssorting1 :: Sort a -> Sort (Compose f g a) Source #

desc :: Sort a -> Sort a Source #

sort :: Sorting a => [a] -> [a] Source #

O(n). Sort a list using discrimination.

sort = sortWith id


sortWith :: Sorting b => (a -> b) -> [a] -> [a] Source #

O(n). Sort a list with a Schwartzian transformation by using discrimination.

This linear time replacement for sortWith and sortOn uses discrimination.

sortingBag :: Foldable f => Sort k -> Sort (f k) Source #

Construct a stable ordered discriminator that sorts a list as multisets of elements from another stable ordered discriminator.

The resulting discriminator only cares about the set of keys and their multiplicity, and is sorted as if we'd sorted each key in turn before comparing.

sortingSet :: Foldable f => Sort k -> Sort (f k) Source #

Construct a stable ordered discriminator that sorts a list as sets of elements from another stable ordered discriminator.

The resulting discriminator only cares about the set of keys, and is sorted as if we'd sorted each key in turn before comparing.

sortingCompare :: Sorting a => a -> a -> Ordering Source #

Valid definition for compare in terms of Sorting.

# Container Construction

toMap :: Sorting k => [(k, v)] -> Map k v Source #

O(n). Construct a Map.

This is an asymptotically faster version of fromList, which exploits ordered discrimination.

>>> toMap []
fromList []

>>> toMap [(5,"a"), (3 :: Int,"b"), (5, "c")]
fromList [(3,"b"),(5,"c")]

>>> Map.fromList [(5,"a"), (3 :: Int,"b"), (5, "c")]
fromList [(3,"b"),(5,"c")]

>>> toMap [(5,"c"), (3,"b"), (5 :: Int, "a")]
fromList [(3,"b"),(5,"a")]

>>> Map.fromList [(5,"c"), (3,"b"), (5 :: Int, "a")]
fromList [(3,"b"),(5,"a")]


toMapWith :: Sorting k => (v -> v -> v) -> [(k, v)] -> Map k v Source #

O(n). Construct a Map, combining values.

This is an asymptotically faster version of fromListWith, which exploits ordered discrimination.

(Note: values combine in anti-stable order for compatibility with fromListWith)

>>> toMapWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")]
fromList [(3,"ab"),(5,"cba")]

>>> Map.fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")]
fromList [(3,"ab"),(5,"cba")]

>>> toMapWith (++) []
fromList []


toMapWithKey :: Sorting k => (k -> v -> v -> v) -> [(k, v)] -> Map k v Source #

O(n). Construct a Map, combining values with access to the key.

This is an asymptotically faster version of fromListWithKey, which exploits ordered discrimination.

(Note: the values combine in anti-stable order for compatibility with fromListWithKey)

>>> let f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_value
>>> toMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")]
fromList [(3,"3:a|b"),(5,"5:c|5:b|a")]

>>> toMapWithKey f []
fromList []


toIntMap :: [(Int, v)] -> IntMap v Source #

O(n). Construct an IntMap.

>>> toIntMap []
fromList []

>>> toIntMap [(5,"a"), (3,"b"), (5, "c")]
fromList [(3,"b"),(5,"c")]

>>> IntMap.fromList [(5,"a"), (3,"b"), (5, "c")]
fromList [(3,"b"),(5,"c")]

>>> toIntMap [(5,"c"), (3,"b"), (5, "a")]
fromList [(3,"b"),(5,"a")]

>>> IntMap.fromList [(5,"c"), (3,"b"), (5, "a")]
fromList [(3,"b"),(5,"a")]


toIntMapWith :: (v -> v -> v) -> [(Int, v)] -> IntMap v Source #

O(n). Construct an IntMap, combining values.

This is an asymptotically faster version of fromListWith, which exploits ordered discrimination.

(Note: values combine in anti-stable order for compatibility with fromListWith)

>>> toIntMapWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")]
fromList [(3,"ab"),(5,"cba")]

>>> IntMap.fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")]
fromList [(3,"ab"),(5,"cba")]

>>> toIntMapWith (++) []
fromList []


toIntMapWithKey :: (Int -> v -> v -> v) -> [(Int, v)] -> IntMap v Source #

O(n). Construct a Map, combining values with access to the key.

This is an asymptotically faster version of fromListWithKey, which exploits ordered discrimination.

(Note: the values combine in anti-stable order for compatibility with fromListWithKey)

>>> let f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_value
>>> toIntMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")]
fromList [(3,"3:a|b"),(5,"5:c|5:b|a")]

>>> IntMap.fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")]
fromList [(3,"3:a|b"),(5,"5:c|5:b|a")]

>>> toIntMapWithKey f []
fromList []


toSet :: Sorting k => [k] -> Set k Source #

O(n). Construct a Set in linear time.

This is an asymptotically faster version of fromList, which exploits ordered discrimination.

toIntSet :: [Int] -> IntSet Source #

O(n). Construct an IntSet in linear time.

This is an asymptotically faster version of fromList, which exploits ordered discrimination.

# Joins

Arguments

 :: Discriminating f => f d the discriminator to use -> ([a] -> [b] -> c) how to join two tables -> (a -> d) selector for the left table -> (b -> d) selector for the right table -> [a] left table -> [b] right table -> [c]

O(n). Perform a full outer join while explicit merging of the two result tables a table at a time.

The results are grouped by the discriminator.

Arguments

 :: Discriminating f => f d the discriminator to use -> (a -> b -> c) how to join two rows -> (a -> d) selector for the left table -> (b -> d) selector for the right table -> [a] left table -> [b] right table -> [[c]]

O(n). Perform an inner join, with operations defined one row at a time.

The results are grouped by the discriminator.

This takes operation time linear in both the input and result sets.

Arguments

 :: Discriminating f => f d the discriminator to use -> (a -> b -> c) how to join two rows -> (a -> c) row present on the left, missing on the right -> (b -> c) row present on the right, missing on the left -> (a -> d) selector for the left table -> (b -> d) selector for the right table -> [a] left table -> [b] right table -> [[c]]

O(n). Perform a full outer join with operations defined one row at a time.

The results are grouped by the discriminator.

This takes operation time linear in both the input and result sets.

Arguments

 :: Discriminating f => f d the discriminator to use -> (a -> b -> c) how to join two rows -> (a -> c) row present on the left, missing on the right -> (a -> d) selector for the left table -> (b -> d) selector for the right table -> [a] left table -> [b] right table -> [[c]]

O(n). Perform a left outer join with operations defined one row at a time.

The results are grouped by the discriminator.

This takes operation time linear in both the input and result sets.

Arguments

 :: Discriminating f => f d the discriminator to use -> (a -> b -> c) how to join two rows -> (b -> c) row present on the right, missing on the left -> (a -> d) selector for the left table -> (b -> d) selector for the right table -> [a] left table -> [b] right table -> [[c]]

O(n). Perform a right outer join with operations defined one row at a time.

The results are grouped by the discriminator.

This takes operation time linear in both the input and result sets.