Data.Discrimination.Sorting

Documentation

newtype Sort a

Stable Ordered Discriminator

Constructors

Sort

Fields

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

Instances

Divisible Sort

Methods

divide :: (a -> (b, c)) -> Sort b -> Sort c -> Sort a

conquer :: Sort a

Decidable Sort

Methods

lose :: (a -> Void) -> Sort a

choose :: (a -> Either b c) -> Sort b -> Sort c -> Sort a

Contravariant Sort

Methods

contramap :: (a -> b) -> Sort b -> Sort a

(>$) :: b -> Sort b -> Sort a

Discriminating Sort

Methods

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

Semigroup (Sort a)

Methods

(<>) :: Sort a -> Sort a -> Sort a

sconcat :: NonEmpty (Sort a) -> Sort a

stimes :: Integral b => b -> Sort a -> Sort a

Monoid (Sort a)

Methods

mempty :: Sort a

mappend :: Sort a -> Sort a -> Sort a

mconcat :: [Sort a] -> Sort a

Sorting

class Grouping a => Sorting a where

Ord equipped with a compatible stable, ordered discriminator.

Methods

sorting :: Sort a

For every strictly monotone-increasing function f:

contramap f sorting ≡ sorting

sorting :: Deciding Sorting a => Sort a

For every strictly monotone-increasing function f:

contramap f sorting ≡ sorting

Instances

Sorting Bool

Methods

sorting :: Sort Bool

Sorting Char

Methods

sorting :: Sort Char

Sorting Int

Methods

sorting :: Sort Int

Sorting Int8

Methods

sorting :: Sort Int8

Sorting Int16

Methods

sorting :: Sort Int16

Sorting Int32

Methods

sorting :: Sort Int32

Sorting Int64

Methods

sorting :: Sort Int64

Sorting Word

Methods

sorting :: Sort Word

Sorting Word8

Methods

sorting :: Sort Word8

Sorting Word16

Methods

sorting :: Sort Word16

Sorting Word32

Methods

sorting :: Sort Word32

Sorting Word64

Methods

sorting :: Sort Word64

Sorting Void

Methods

sorting :: Sort Void

Sorting a => Sorting [a]

Methods

sorting :: Sort [a]

Sorting a => Sorting (Maybe a)

Methods

sorting :: Sort (Maybe a)

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

Methods

sorting :: Sort (Either a b)

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

Methods

sorting :: Sort (a, b)

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

Methods

sorting :: Sort (a, b, c)

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

Methods

sorting :: Sort (a, b, c, d)

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

Methods

sorting :: Sort (Compose * * f g a)

class Grouping1 f => Sorting1 f where

Methods

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

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

Instances

Sorting1 []

Methods

sorting1 :: Sort a -> Sort [a]

Sorting1 Maybe

Methods

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

Sorting a => Sorting1 (Either a)

Methods

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

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

Methods

sorting1 :: Sort a -> Sort (Compose * * f g a)

Combinators

Useful combinators.

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.

desc :: Sort a -> Sort a

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.

Internals

sortingNat :: Int -> Sort Int

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.