Data.Discrimination

Discrimination

class Decidable f => Discriminating f where

Methods

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

Instances

Discriminating Group

Discriminating Sort

Unordered

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

Decidable Group

Contravariant Group

Discriminating Group

Monoid (Group a)

Semigroup (Group a)

class Grouping a where

Eq equipped with a compatible stable unordered discriminator.

Minimal complete definition

Nothing

Methods

grouping :: Group a

For every surjection f,

contramap f grouping ≡ grouping

Instances

Grouping Bool

Grouping Char

Grouping Int

Grouping Int8

Grouping Int16

Grouping Int32

Grouping Int64

Grouping Word

Grouping Word8

Grouping Word16

Grouping Word32

Grouping Word64

Grouping Void

Grouping a => Grouping [a]

(Grouping a, Integral a) => Grouping (Ratio a)

Grouping a => Grouping (Complex a)

Grouping a => Grouping (Maybe a)

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

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

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

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

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

class Grouping1 f where

Minimal complete definition

Nothing

Methods

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

Instances

Grouping1 []

Grouping1 Complex

Grouping1 Maybe

Grouping a => Grouping1 (Either a)

Grouping a => Grouping1 ((,) a)

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

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

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

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.

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

groupingEq :: Grouping a => a -> a -> Bool

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

Ordered

newtype Sort a

Stable Ordered Discriminator

Constructors

Sort

Fields

runSort :: forall b. [(a, b)] -> [[b]]

Instances

Divisible Sort

Decidable Sort

Contravariant Sort

Discriminating Sort

Monoid (Sort a)

Semigroup (Sort a)

class Grouping a => Sorting a where

Ord equipped with a compatible stable, ordered discriminator.

Minimal complete definition

Nothing

Methods

sorting :: Sort a

For every strictly monotone-increasing function f:

contramap f sorting ≡ sorting

Instances

Sorting Bool

Sorting Char

Sorting Int

Sorting Int8

Sorting Int16

Sorting Int32

Sorting Int64

Sorting Word

Sorting Word8

Sorting Word16

Sorting Word32

Sorting Word64

Sorting Void

Sorting a => Sorting [a]

Sorting a => Sorting (Maybe a)

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

(Sorting a, Sorting b) => Sorting (a, b)

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

(Sorting1 f, Sorting1 g, Sorting a) => Sorting (Compose f g a)

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

class Grouping1 f => Sorting1 f where

Minimal complete definition

Nothing

Methods

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

Instances

Sorting1 []

Sorting1 Maybe

Sorting a => Sorting1 (Either a)

(Sorting1 f, Sorting1 g) => Sorting1 (Compose f g)

desc :: Sort a -> Sort a

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

O(n). Sort a list using discrimination.

sort = sortWith id

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

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)

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)

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

Valid definition for compare in terms of Sorting.

Container Construction

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

O(n). Construct a Map.

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

>>> toMap [] == empty
True

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

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

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

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

>>> toMapWith (++) [] == empty
True

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

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 [] == empty
True

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

O(n). Construct an IntMap.

>>> toIntMap [] == empty
True

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

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

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

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

>>> toIntMapWith (++) [] == empty
True

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

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

>>> toIntMapWithKey f [] == empty
True

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

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

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

toIntSet :: [Int] -> IntSet

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

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

Joins

joining

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.

inner

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.

outer

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.

leftOuter

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.

rightOuter

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.