-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Set and bag operations on ordered lists
--   
--   Ordered Lists
@package data-ordlist
@version 0.2


-- | This module implements bag and set operations on ordered lists. Except
--   for variations of the <a>sort</a> and <a>isSorted</a> 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, <a>isect</a> does not always
--   return the same results as Data.List.intersection, due to
--   multiplicity.
module Data.List.Ordered

-- | <a>member</a> returns <a>True</a> if the element appears in the
--   ordered list
member :: (Ord a) => a -> [a] -> Bool

-- | <a>memberBy</a> is the non-overloaded version of <a>member</a>
memberBy :: (a -> a -> Ordering) -> a -> [a] -> Bool

-- | <a>has</a> returns <a>True</a> if the element appears in the list; it
--   is a function from an ordered list to its characteristic function.
has :: (Ord a) => [a] -> a -> Bool

-- | <a>hasBy</a> is the non-overloaded version of <a>has</a>
hasBy :: (a -> a -> Ordering) -> [a] -> a -> Bool

-- | <a>subset</a> returns true if the first list is a sub-list of the
--   second.
subset :: (Ord a) => [a] -> [a] -> Bool

-- | <a>subsetBy</a> is the non-overloaded version of <a>subset</a>
subsetBy :: (a -> a -> Ordering) -> [a] -> [a] -> Bool

-- | <a>isSorted</a> returns <a>True</a> if the elements of a list occur in
--   non-descending order, equivalent to <a>isSortedBy</a> (<a>&lt;=</a>)
isSorted :: (Ord a) => [a] -> Bool

-- | <a>isSortedBy</a> returns <a>True</a> if the predicate returns true
--   for all adjacent pairs of elements in the list
isSortedBy :: (a -> a -> Bool) -> [a] -> Bool

-- | <a>insertBag</a> inserts an element into a list, allowing for
--   duplicate elements
insertBag :: (Ord a) => a -> [a] -> [a]

-- | <a>insertBagBy</a> is the non-overloaded version of <a>insertBag</a>
insertBagBy :: (a -> a -> Ordering) -> a -> [a] -> [a]

-- | <a>insertSet</a> inserts an element into an ordered list, or replaces
--   the first occurrence if it is already there.
insertSet :: (Ord a) => a -> [a] -> [a]

-- | <a>insertSetBy</a> is the non-overloaded version of <a>insertSet</a>
insertSetBy :: (a -> a -> Ordering) -> a -> [a] -> [a]

-- | <a>isect</a> computes the intersection of two ordered lists. The
--   result contains those elements contained in both arguments
--   
--   <pre>
--   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]
--   </pre>
isect :: (Ord a) => [a] -> [a] -> [a]

-- | <a>isectBy</a> is the non-overloaded version of <a>isect</a>
isectBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]

-- | <a>union</a> 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.
--   
--   <pre>
--   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]
--   </pre>
union :: (Ord a) => [a] -> [a] -> [a]

-- | <a>unionBy</a> is the non-overloaded version of <a>union</a>
unionBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]

-- | <a>minus</a> 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.
--   
--   <pre>
--   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]
--   </pre>
minus :: (Ord a) => [a] -> [a] -> [a]

-- | <a>minusBy</a> is the non-overloaded version of <a>minus</a>
minusBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]

-- | <a>xunion</a> computes the multiset exclusive union of two ordered
--   lists. The result contains those elements that appear in either list,
--   but not both.
--   
--   <pre>
--   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]
--   </pre>
xunion :: (Ord a) => [a] -> [a] -> [a]

-- | <a>xunionBy</a> is the non-overloaded version of <a>xunion</a>
xunionBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]

-- | <a>merge</a> 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.
--   
--   <pre>
--   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]
--   </pre>
merge :: (Ord a) => [a] -> [a] -> [a]

-- | <a>mergeBy</a> is the non-overloaded version of <a>merge</a>
mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]

-- | On ordered lists, <a>nub</a> is equivalent to <tt>Data.List.nub</tt>,
--   except that it runs in linear time instead of quadratic. On unordered
--   lists it also removes elements that are smaller than any preceding
--   element.
--   
--   <pre>
--   nub [1,1,1,2,2] == [1,2]
--   nub [2,0,1,3,3] == [2,3]
--   nub = nubBy (&lt;)
--   </pre>
nub :: (Ord a) => [a] -> [a]

-- | <a>nubBy</a> is the greedy algorithm that returns a sublist of its
--   input such that <a>isSortedBy</a> is true.
--   
--   <pre>
--   isSortedBy pred (nubBy pred xs) == True
--   </pre>
nubBy :: (a -> a -> Bool) -> [a] -> [a]

-- | The <a>sort</a> function implements a stable sorting algorithm. It is
--   a special case of <a>sortBy</a>, which allows the programmer to supply
--   their own comparison function.
sort :: (Ord a) => [a] -> [a]

-- | The <a>sortBy</a> function is the non-overloaded version of
--   <a>sort</a>.
sortBy :: (a -> a -> Ordering) -> [a] -> [a]

-- | <a>sortOn</a> provides the decorate-sort-undecorate idiom, aka the
--   "Schwartzian transform"
sortOn :: (Ord b) => (a -> b) -> [a] -> [a]

-- | This variant of <a>sortOn</a> recomputes the function to sort on every
--   comparison. This can is better for functions that are cheap to
--   compute, including projections.
sortOn' :: (Ord b) => (a -> b) -> [a] -> [a]

-- | <a>nubSort</a> is equivalent to <a>nub</a> <a>.</a> <a>sort</a>,
--   except somewhat more efficient as duplicates are removed as it sorts.
--   It is essentially Data.List.sort, a mergesort by Ian Lynagh, with
--   <a>merge</a> replaced by <a>union</a>.
nubSort :: (Ord a) => [a] -> [a]

-- | <a>nubSortBy</a> is the non-overloaded version of <a>nubSort</a>
nubSortBy :: (a -> a -> Ordering) -> [a] -> [a]

-- | <a>nubSortOn</a> provides decorate-sort-undecorate for <a>nubSort</a>
nubSortOn :: (Ord b) => (a -> b) -> [a] -> [a]

-- | This variant of <a>nubSortOn</a> recomputes the function for each
--   comparison.
nubSortOn' :: (Ord b) => (a -> b) -> [a] -> [a]