Portability | portable |
---|---|

Stability | experimental |

Maintainer | leon@melding-monads.com |

This module implements bag and set operations on ordered lists.
Except for variations of the `sort`

and `isSorted`

functions,
every function assumes that any list arguments are sorted lists.
Assuming this precondition is met, every resulting list is also
sorted.

Note that these functions handle multisets, and are left-biased.
Thus, even assuming the arguments are sorted, `isect`

does not always
return the same results as Data.List.intersection, due to multiplicity.

- member :: Ord a => a -> [a] -> Bool
- memberBy :: (a -> a -> Ordering) -> a -> [a] -> Bool
- has :: Ord a => [a] -> a -> Bool
- hasBy :: (a -> a -> Ordering) -> [a] -> a -> Bool
- subset :: Ord a => [a] -> [a] -> Bool
- subsetBy :: (a -> a -> Ordering) -> [a] -> [a] -> Bool
- isSorted :: Ord a => [a] -> Bool
- isSortedBy :: (a -> a -> Bool) -> [a] -> Bool
- insertBag :: Ord a => a -> [a] -> [a]
- insertBagBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
- insertSet :: Ord a => a -> [a] -> [a]
- insertSetBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
- isect :: Ord a => [a] -> [a] -> [a]
- isectBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
- union :: Ord a => [a] -> [a] -> [a]
- unionBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
- minus :: Ord a => [a] -> [a] -> [a]
- minusBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
- xunion :: Ord a => [a] -> [a] -> [a]
- xunionBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
- merge :: Ord a => [a] -> [a] -> [a]
- mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
- mergeAll :: Ord a => [[a]] -> [a]
- mergeAllBy :: (a -> a -> Ordering) -> [[a]] -> [a]
- unionAll :: Ord a => [[a]] -> [a]
- unionAllBy :: (a -> a -> Ordering) -> [[a]] -> [a]
- nub :: Ord a => [a] -> [a]
- nubBy :: (a -> a -> Bool) -> [a] -> [a]
- sort :: Ord a => [a] -> [a]
- sortBy :: (a -> a -> Ordering) -> [a] -> [a]
- sortOn :: Ord b => (a -> b) -> [a] -> [a]
- sortOn' :: Ord b => (a -> b) -> [a] -> [a]
- nubSort :: Ord a => [a] -> [a]
- nubSortBy :: (a -> a -> Ordering) -> [a] -> [a]
- nubSortOn :: Ord b => (a -> b) -> [a] -> [a]
- nubSortOn' :: Ord b => (a -> b) -> [a] -> [a]

# Predicates

subset :: Ord a => [a] -> [a] -> BoolSource

The `subset`

function returns true if the first list is a sub-list
of the second.

isSorted :: Ord a => [a] -> BoolSource

The `isSorted`

predicate returns `True`

if the elements of a list occur in non-descending order, equivalent to

.
`isSortedBy`

(`<=`

)

isSortedBy :: (a -> a -> Bool) -> [a] -> BoolSource

The `isSortedBy`

function returns `True`

iff the predicate returns true
for all adjacent pairs of elements in the list.

# Insertion Functions

insertBag :: Ord a => a -> [a] -> [a]Source

The `insertBag`

function inserts an element into a list. If the element
is already there, then another copy of the element is inserted.

insertBagBy :: (a -> a -> Ordering) -> a -> [a] -> [a]Source

The `insertBagBy`

function is the non-overloaded version of `insertBag`

.

insertSet :: Ord a => a -> [a] -> [a]Source

The `insertSet`

function inserts an element into an ordered list.
If the element is already there, then the element replaces the existing
element.

insertSetBy :: (a -> a -> Ordering) -> a -> [a] -> [a]Source

The `insertSetBy`

function is the non-overloaded version of `insertSet`

.

# Set-like operations

isect :: Ord a => [a] -> [a] -> [a]Source

The `isect`

function computes the intersection of two ordered lists.
An element occurs in the output as many times as the minimum number of
occurences in either input. If either input is a set, then the output
is a set.

isect [ 1,2, 3,4 ] [ 3,4, 5,6 ] == [ 3,4 ] isect [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1, 2,2 ]

union :: Ord a => [a] -> [a] -> [a]Source

The `union`

function computes the union of two ordered lists.
An element occurs in the output as many times as the maximum number
of occurences in either input. If both inputs are sets, then the
output is a set.

union [ 1,2, 3,4 ] [ 3,4, 5,6 ] == [ 1,2, 3,4, 5,6 ] union [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1,1,1, 2,2,2 ]

minus :: Ord a => [a] -> [a] -> [a]Source

The `minus`

function computes the difference of two ordered lists.
An element occurs in the output as many times as it occurs in
the first input, minus the number of occurrences in the second input.
If the first input is a set, then the output is a set.

minus [ 1,2, 3,4 ] [ 3,4, 5,6 ] == [ 1,2 ] minus [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 2 ]

xunion :: Ord a => [a] -> [a] -> [a]Source

The `xunion`

function computes the exclusive union of two ordered lists.
An element occurs in the output as many times as the absolute difference
between the number of occurrences in the inputs. If both inputs
are sets, then the output is a set.

xunion [ 1,2, 3,4 ] [ 3,4, 5,6 ] == [ 1,2, 5,6 ] xunion [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1,1, 2 ]

merge :: Ord a => [a] -> [a] -> [a]Source

The `merge`

function combines all elements of two ordered lists.
An element occurs in the output as many times as the sum of the
occurences in the lists.

merge [ 1,2, 3,4 ] [ 3,4, 5,6 ] == [ 1,2, 3,3,4,4, 5,6 ] merge [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1,1,1,1, 2,2,2,2,2 ]

mergeAll :: Ord a => [[a]] -> [a]Source

The `mergeAll`

function generalizes

to a
(possibly infinite) list of (possibly infinite) ordered lists. To make
this possible, it adds the assumption that the heads of the non-empty
lists themselves form a sorted list.
`foldr`

`merge`

[]

The implementation is based on the article "Implicit Heaps" by Heinrich Apfelmus, which simplifies an algorithm by Dave Bayer.

http://apfelmus.nfshost.com/articles/implicit-heaps.html

The following definition is a simple and reasonably efficient implementation that is faster for inputs whose smallest elements are highly biased towards the first few lists:

mergeAll' = foldr merge' [] where merge' [] ys = ys merge' (x:xs) ys = x : merge xs ys

This simplification uses a linear chain of comparisons. The implementation provided uses a tree of comparisons, which is faster on a wide range of inputs.

mergeAllBy :: (a -> a -> Ordering) -> [[a]] -> [a]Source

The `mergeAllBy`

function is the non-overloaded variant of the `mergeAll`

function.

unionAll :: Ord a => [[a]] -> [a]Source

The `unionAll`

function generalizes

to a
(possibly infinite) list of (possibly infinite) ordered lists.
To make this possible, it adds the assumption that the heads of the
non-empty lists themselves form a sorted list.
`foldr`

`union`

[]

The library implementation is based on some of the same techniques
as used in `mergeAll`

. However, the analogous simple definition
is not entirely satisfactory, because

unionAll' = foldr union' [] where union' [] ys = ys union' (x:xs) ys = x : union xs ys unionAll' [[1,2],[1,2]] == [1,1,2]

whereas we really want the result

unionAll [[1,2],[1,2]] == foldr union [] [[1,2],[1,2]] == [1,2]

The first equality is only true when both sets of assumptions are met:
`foldr union []`

assumes the outer list is finite, and `unionAll`

assumes that the heads of the inner lists are sorted.

unionAllBy :: (a -> a -> Ordering) -> [[a]] -> [a]Source

The `unionAllBy`

function is the non-overloaded variant of the `unionAll`

function.

# Lists to Ordered Lists

nub :: Ord a => [a] -> [a]Source

On ordered lists, `nub`

is equivalent to `Data.List.nub`

, except that
it runs in linear time instead of quadratic. On unordered lists it also
removes elements that are smaller than any preceding element.

nub [1,1,1,2,2] == [1,2] nub [2,0,1,3,3] == [2,3] nub = nubBy (<)

nubBy :: (a -> a -> Bool) -> [a] -> [a]Source

The `nubBy`

function is the greedy algorithm that returns a
sublist of its input such that:

isSortedBy pred (nubBy pred xs) == True

This is true for all lists, not just ordered lists, and all binary predicates, not just total orders. On infinite lists, this statement is true in a certain mathematical sense, but not a computational one.

sortOn :: Ord b => (a -> b) -> [a] -> [a]Source

The `sortOn`

function provides the decorate-sort-undecorate idiom,
also known as the "Schwartzian transform".

sortOn' :: Ord b => (a -> b) -> [a] -> [a]Source

This variant of `sortOn`

recomputes the sorting key every comparison.
This can be better for functions that are cheap to compute.
This is definitely better for projections, as the decorate-sort-undecorate
saves nothing and adds two traversals of the list and extra memory
allocation.

nubSortOn' :: Ord b => (a -> b) -> [a] -> [a]Source

This variant of `nubSortOn`

recomputes the sorting key for each comparison.