Safe Haskell | None |
---|---|

Language | Haskell2010 |

## 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 Source #

Nothing

#### Instances

class Grouping1 f => Sorting1 f where Source #

Nothing

# Combinators

Useful combinators.

sortingCompare :: Sorting a => a -> a -> Ordering Source #

# 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.

`>>>`

fromList []`toMap []`

`>>>`

fromList [(3,"b"),(5,"c")]`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,"a")]`toMap [(5,"c"), (3,"b"), (5 :: Int, "a")]`

`>>>`

fromList [(3,"b"),(5,"a")]`Map.fromList [(5,"c"), (3,"b"), (5 :: Int, "a")]`

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`

)

`>>>`

fromList [(3,"ab"),(5,"cba")]`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 []`toMapWith (++) []`

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`

`>>>`

fromList [(3,"3:a|b"),(5,"5:c|5:b|a")]`toMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")]`

`>>>`

fromList []`toMapWithKey f []`

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

*O(n)*. Construct an `IntMap`

.

`>>>`

fromList []`toIntMap []`

`>>>`

fromList [(3,"b"),(5,"c")]`toIntMap [(5,"a"), (3,"b"), (5, "c")]`

`>>>`

fromList [(3,"b"),(5,"c")]`IntMap.fromList [(5,"a"), (3,"b"), (5, "c")]`

`>>>`

fromList [(3,"b"),(5,"a")]`toIntMap [(5,"c"), (3,"b"), (5, "a")]`

`>>>`

fromList [(3,"b"),(5,"a")]`IntMap.fromList [(5,"c"), (3,"b"), (5, "a")]`

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`

)

`>>>`

fromList [(3,"ab"),(5,"cba")]`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 []`toIntMapWith (++) []`

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`

`>>>`

fromList [(3,"3:a|b"),(5,"5:c|5:b|a")]`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 []`toIntMapWithKey f []`

# Internals

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.