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

Stability | experimental |

Maintainer | leon at melding-monads dot 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`

may not be a
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
- 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]
- subset :: Ord a => [a] -> [a] -> Bool
- subsetBy :: (a -> a -> Ordering) -> [a] -> [a] -> Bool
- 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]
- nub :: Ord a => [a] -> [a]
- nubBy :: (a -> a -> Bool) -> [a] -> [a]

# Documentation

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

Returns `True`

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

'(<=)'

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

Returns `True`

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

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

Inserts an element into a list, allowing for duplicate elements

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

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

Inserts an element into a list only if it is not already there.

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

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

Intersection of two ordered lists.

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 of two ordered lists.

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

Difference

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

Exclusive union

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 two ordered lists

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]

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

Returns true if the first list is a sub-list of the second

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

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

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

Recomputes instead; better for some things such as projections.

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