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

Safe HaskellTrustworthy
LanguageHaskell2010

Data.Discrimination.Sorting

Contents

Synopsis

Documentation

newtype Sort a Source

Stable Ordered Discriminator

Constructors

Sort 

Fields

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

Instances

Contravariant Sort Source 
Divisible Sort Source 
Decidable Sort Source 
Discriminating Sort Source 
Monoid (Sort a) Source 

Sorting

class Grouping a => Sorting a where Source

Ord equipped with a compatible stable, ordered discriminator.

Minimal complete definition

Nothing

Methods

sorting :: Sort a Source

For every strictly monotone-increasing function f:

contramap f sorting ≡ sorting

Instances

class Grouping1 f => Sorting1 f where Source

Minimal complete definition

Nothing

Methods

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

Instances

Combinators

Useful combinators.

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.

desc :: Sort a -> Sort a Source

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

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

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

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

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

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

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

>>> toIntMapWithKey f [] == empty
True

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.

Internals

sortingNat :: Int -> Sort Int Source

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.