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

Data.Discrimination.Sorting

Synopsis

# Documentation

newtype Sort a Source

Stable Ordered Discriminator

Constructors

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

Instances

 Source Source Source Source Monoid (Sort a) Source Source

# Sorting

class Grouping a => Sorting a where Source

`Ord` equipped with a compatible stable, ordered discriminator.

Minimal complete definition

Nothing

Methods

For every strictly monotone-increasing function `f`:

````contramap` f `sorting` ≡ `sorting`
```

Instances

 Source Source Source Source Source Source Source Source Source Source Source Source Source Sorting a => Sorting [a] Source Sorting a => Sorting (Maybe a) Source (Sorting a, Sorting b) => Sorting (Either a b) Source (Sorting a, Sorting b) => Sorting (a, b) Source (Sorting a, Sorting b, Sorting c) => Sorting (a, b, c) Source (Sorting1 f, Sorting1 g, Sorting a) => Sorting (Compose f g a) Source (Sorting a, Sorting b, Sorting c, Sorting d) => Sorting (a, b, c, d) Source

class Grouping1 f => Sorting1 f where Source

Minimal complete definition

Nothing

Methods

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

Instances

 Sorting1 [] Source Source Sorting a => Sorting1 (Either a) Source (Sorting1 f, Sorting1 g) => Sorting1 (Compose f g) Source

# 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

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.