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

`subset`

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

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

`isSorted`

returns `True`

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

(`<=`

)

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

`isSortedBy`

returns `True`

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

# Insertion Functions

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

`insertBag`

inserts an element into a list, allowing for duplicate elements

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

`insertBagBy`

is the non-overloaded version of `insertBag`

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

`insertSet`

inserts an element into an ordered list, or replaces the first occurrence if it is already there.

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

`insertSetBy`

is the non-overloaded version of `insertSet`

# Set-like operations

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

`isect`

computes the intersection of two ordered lists.
The result contains those elements contained in both arguments

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

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

`union`

computes the union of two ordered lists.
The result contains those elements contained in either argument;
elements that appear in both lists are appear in the result only once.

union [1,3,5] [2,4,6] == [1..6] union [2,4,6,8] [3,6,9] == [2,3,4,6,8,9] union [1,2,2,2] [1,1,1,2,2] == [1,1,1,2,2,2]

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

`minus`

computes the multiset difference of two ordered lists.
Each occurence of an element in the second argument is removed from the first list, if it is there.

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

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

`xunion`

computes the multiset exclusive union of two ordered lists.
The result contains those elements that appear in either list, but not both.

xunion [1,3,5] [2,4,6] == [1..6] xunion [2,4,6,8] [3,6,9] == [2,3,4,8] xunion [1,2,2,2] [1,1,1,2,2] == [1,1,2]

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

`merge`

combines all elements of two ordered lists. The result contains those elements that appear in either list; elements that appear in both lists appear in the result multiple times.

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

# 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

`nubBy`

is the greedy algorithm that returns a sublist of its
input such that `isSortedBy`

is true.

isSortedBy pred (nubBy pred xs) == True

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

`sortOn`

provides the decorate-sort-undecorate idiom, aka the "Schwartzian transform"

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

This variant of `sortOn`

recomputes the function to sort on every comparison. This can is better
for functions that are cheap to compute, including projections.

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

This variant of `nubSortOn`

recomputes the function for each comparison.