Copyright | (c) 2009-2011 Leon P Smith |
---|---|

License | BSD3 |

Maintainer | leon@melding-monads.com |

Stability | experimental |

Portability | portable |

Safe Haskell | Safe |

Language | Haskell98 |

This module implements bag and set operations on ordered lists. For the purposes of this module, a "bag" (or "multiset") is a non-decreasing list, whereas a "set" is a strictly ascending list. Bags are sorted lists that may contain duplicates, whereas sets are sorted lists that do not contain duplicates.

Except for the `nub`

, `sort`

, `nubSort`

, and `isSorted`

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

Because `isect`

handles multisets correctly, it does not return results
comparable to `Data.List.`

on them. Thus `intersect`

`isect`

is more than just a more efficient `intersect`

on ordered lists. Similar
statements apply to other associations between functions this module and
functions in `Data.List`

, such as `union`

and `Data.List.`

.`union`

All functions in this module are left biased. Elements that appear in earlier arguments have priority over equal elements that appear in later arguments, and elements that appear earlier in a single list have priority over equal elements that appear later in that list.

## Synopsis

- 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 -> b -> Ordering) -> [a] -> [b] -> [a]
- union :: Ord a => [a] -> [a] -> [a]
- unionBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
- minus :: Ord a => [a] -> [a] -> [a]
- minusBy :: (a -> b -> Ordering) -> [a] -> [b] -> [a]
- minus' :: Ord a => [a] -> [a] -> [a]
- minusBy' :: (a -> b -> Ordering) -> [a] -> [b] -> [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]
- foldt :: (a -> a -> a) -> a -> [a] -> a
- foldt' :: (a -> a -> a) -> a -> [a] -> a

# Predicates

subset :: Ord a => [a] -> [a] -> Bool #

The `subset`

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

isSorted :: Ord a => [a] -> Bool #

The `isSorted`

predicate returns `True`

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

.`isSortedBy`

(`<=`

)

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

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

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

The `insertBagBy`

function is the non-overloaded version of `insertBag`

.

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

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

The `insertSetBy`

function is the non-overloaded version of `insertSet`

.

# Set-like operations

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

The `isect`

function computes the intersection of two ordered lists.
An element occurs in the output as many times as the minimum number of
occurrences 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] #

The `union`

function computes the union of two ordered lists.
An element occurs in the output as many times as the maximum number
of occurrences in either input. The output is a set if and only if
both inputs are sets.

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

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 ]

minus' :: Ord a => [a] -> [a] -> [a] #

The `minus'`

function computes the difference of two ordered lists.
The result consists of elements from the first list that do not appear
in the second list. 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 ] == [] minus' [ 1,1, 2,2 ] [ 2 ] == [ 1,1 ]

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

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

The `merge`

function combines all elements of two ordered lists.
An element occurs in the output as many times as the sum of the
occurrences in both lists. The output is a set if and only if
the inputs are disjoint sets.

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

The `mergeAll`

function merges a (potentially) infinite number of
ordered lists, under the assumption that the heads of the inner lists
are sorted. An element is duplicated in the result as many times as
the total number of occurrences in all inner lists.

The `mergeAll`

function is closely related to

.
The former does not assume that the outer list is finite, whereas
the latter does not assume that the heads of the inner lists are sorted.
When both sets of assumptions are met, these two functions are
equivalent.`foldr`

`merge`

[]

This implementation of `mergeAll`

uses a tree of comparisons, and is
based on input from Dave Bayer, Heinrich Apfelmus, Omar Antolin Camarena,
and Will Ness. See `CHANGES`

for details.

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

The `mergeAllBy`

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

function.

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

The `unionAll`

computes the union of a (potentially) infinite number
of lists, under the assumption that the heads of the inner lists
are sorted. The result will duplicate an element as many times as
the maximum number of occurrences in any single list. Thus, the result
is a set if and only if every inner list is a set.

The `unionAll`

function is closely related to

.
The former does not assume that the outer list is finite, whereas
the latter does not assume that the heads of the inner lists are sorted.
When both sets of assumptions are met, these two functions are
equivalent.`foldr`

`union`

[]

Note that there is no simple way to express `unionAll`

in terms of
`mergeAll`

or vice versa on arbitrary valid inputs. They are related
via `nub`

however, as

.
If every list is a set, then `nub`

. `mergeAll`

== `unionAll`

. `map`

`nub`

`map nub == id`

, and in this special case
(and only in this special case) does `nub . mergeAll == unionAll`

.

This implementation of `unionAll`

uses a tree of comparisons, and is
based on input from Dave Bayer, Heinrich Apfelmus, Omar Antolin Camarena,
and Will Ness. See `CHANGES`

for details.

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

The `unionAllBy`

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

function.

# Lists to Ordered Lists

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

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.

The `sort`

function implements a stable sorting algorithm.
It is a special case of `sortBy`

, which allows the programmer to supply
their own comparison function.

Elements are arranged from from lowest to highest, keeping duplicates in the order they appeared in the input.

`>>>`

[1,2,3,4,5,6]`sort [1,6,4,3,2,5]`

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

Sort a list by comparing the results of a key function applied to each
element. `sortOn f`

is equivalent to `sortBy (comparing f)`

, but has the
performance advantage of only evaluating `f`

once for each element in the
input list. This is called the decorate-sort-undecorate paradigm, or
Schwartzian transform.

Elements are arranged from from lowest to highest, keeping duplicates in the order they appeared in the input.

`>>>`

[(1,"Hello"),(2,"world"),(4,"!")]`sortOn fst [(2, "world"), (4, "!"), (1, "Hello")]`

*Since: base-4.8.0.0*

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

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.

nubSort :: Ord a => [a] -> [a] #

The `nubSort`

function is equivalent to

, except
that duplicates are removed as it sorts. It is essentially the same
implementation as `nub`

`.`

`sort`

`Data.List.sort`

, with `merge`

replaced by `union`

.
Thus the performance of `nubSort`

should better than or nearly equal
to `sort`

alone. It is faster than both `sort`

and

when the input contains significant quantities of duplicated elements.`nub`

`.`

`sort`

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

This variant of `nubSortOn`

recomputes the sorting key for each comparison