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