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.