Productive Stable Unordered Discriminator

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.

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

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

nubWith f as = head <$> groupWith f as

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

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.

Stable Ordered Discriminator

Ord equipped with a compatible stable, ordered discriminator.

Law:

sortingCompare x y ≡ compare x y

O(n). Sort a list using discrimination.

sort = sortWith id

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

This linear time replacement for sortWith and sortOn uses discrimination.

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.

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.

Valid definition for compare in terms of Sorting.

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

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

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

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

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

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

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

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

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

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

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.

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.

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.

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.

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.