Safe Haskell	Safe
Language	Haskell2010

Data.Discrimination.Sorting

Contents

Sorting
Combinators
Container Construction
Internals

Synopsis

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.