| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Data.Discrimination.Sorting
Synopsis
- newtype Sort a = Sort {
- runSort :: forall b. [(a, b)] -> [[b]]
- class Grouping a => Sorting a where
- class Grouping1 f => Sorting1 f where
- sort :: Sorting a => [a] -> [a]
- sortWith :: Sorting b => (a -> b) -> [a] -> [a]
- desc :: Sort a -> Sort a
- sortingCompare :: Sorting a => a -> a -> Ordering
- toMap :: Sorting k => [(k, v)] -> Map k v
- toMapWith :: Sorting k => (v -> v -> v) -> [(k, v)] -> Map k v
- toMapWithKey :: Sorting k => (k -> v -> v -> v) -> [(k, v)] -> Map k v
- toIntMap :: [(Int, v)] -> IntMap v
- toIntMapWith :: (v -> v -> v) -> [(Int, v)] -> IntMap v
- toIntMapWithKey :: (Int -> v -> v -> v) -> [(Int, v)] -> IntMap v
- toSet :: Sorting k => [k] -> Set k
- toIntSet :: [Int] -> IntSet
- sortingNat :: Int -> Sort Int
- sortingBag :: Foldable f => Sort k -> Sort (f k)
- sortingSet :: Foldable f => Sort k -> Sort (f k)
Documentation
Stable Ordered Discriminator
Sorting
class Grouping a => Sorting a where #
Ord equipped with a compatible stable, ordered discriminator.
Methods
Instances
Combinators
Useful combinators.
sortingCompare :: Sorting a => a -> a -> Ordering #
Container Construction
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 (++) [] == emptyTrue
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 [] == emptyTrue
toIntMap :: [(Int, v)] -> IntMap v #
O(n). Construct an IntMap.
>>>toIntMap [] == emptyTrue
>>>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 (++) [] == emptyTrue
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 [] == emptyTrue
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.