data-ordlist-0.0.1: Set and bag operations on ordered lists

Portabilityportable
Stabilityexperimental
Maintainerleon at melding-monads dot com

Data.OrdList

Description

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.

Synopsis

Documentation

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

Returns True if the element appears in the list

memberBy :: (a -> a -> Ordering) -> a -> [a] -> BoolSource

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

Returns True if the element appears in the list

hasBy :: (a -> a -> Ordering) -> [a] -> a -> BoolSource

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]

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

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]

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

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]

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

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]

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

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]

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

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

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

subsetBy :: (a -> a -> Ordering) -> [a] -> [a] -> BoolSource

sort :: Ord a => [a] -> [a]

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.

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

The sortBy function is the non-overloaded version of sort.

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.

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

Equivalent to nub . sort, except somewhat more efficient

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

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

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

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

Equivalent to nub on ordered lists, except faster; on unordered lists it also removes elements that are smaller than any preceding element.

 nub [2,0,1,3,3] == [2,3]

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