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

-- | Set and bag operations on ordered lists
--   
--   This module provides set and multiset operations on ordered lists.
@package data-ordlist
@version 0.4.7.0

-- | This module implements bag and set operations on ordered lists. For
--   the purposes of this module, a "bag" (or "multiset") is a
--   non-decreasing list, whereas a "set" is a strictly ascending list.
--   Bags are sorted lists that may contain duplicates, whereas sets are
--   sorted lists that do not contain duplicates.
--   
--   Except for the nub, sort, nubSort, and
--   isSorted families of functions, every function assumes that any
--   list arguments are sorted lists. Assuming this precondition is met,
--   every resulting list is also sorted.
--   
--   Because isect handles multisets correctly, it does not return
--   results comparable to Data.List.intersect on them.
--   Thus isect is more than just a more efficient
--   intersect on ordered lists. Similar statements apply to other
--   associations between functions this module and functions in
--   Data.List, such as union and
--   Data.List.union.
--   
--   All functions in this module are left biased. Elements that appear in
--   earlier arguments have priority over equal elements that appear in
--   later arguments, and elements that appear earlier in a single list
--   have priority over equal elements that appear later in that list.
module Data.List.Ordered

-- | The member function returns True if the element appears
--   in the ordered list.
member :: Ord a => a -> [a] -> Bool

-- | The memberBy function is the non-overloaded version of
--   member.
memberBy :: (a -> a -> Ordering) -> a -> [a] -> Bool

-- | The has function returns True if the element appears in
--   the list; it is equivalent to member except the order of the
--   arguments is reversed, making it a function from an ordered list to
--   its characteristic function.
has :: Ord a => [a] -> a -> Bool

-- | The hasBy function is the non-overloaded version of has.
hasBy :: (a -> a -> Ordering) -> [a] -> a -> Bool

-- | The subset function returns true if the first list is a
--   sub-list of the second.
subset :: Ord a => [a] -> [a] -> Bool

-- | The subsetBy function is the non-overloaded version of
--   subset.
subsetBy :: (a -> a -> Ordering) -> [a] -> [a] -> Bool

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

-- | The isSortedBy function returns True iff the predicate
--   returns true for all adjacent pairs of elements in the list.
isSortedBy :: (a -> a -> Bool) -> [a] -> Bool

-- | The insertBag function inserts an element into a list. If the
--   element is already there, then another copy of the element is
--   inserted.
insertBag :: Ord a => a -> [a] -> [a]

-- | The insertBagBy function is the non-overloaded version of
--   insertBag.
insertBagBy :: (a -> a -> Ordering) -> a -> [a] -> [a]

-- | The insertSet function inserts an element into an ordered list.
--   If the element is already there, then the element replaces the
--   existing element.
insertSet :: Ord a => a -> [a] -> [a]

-- | The insertSetBy function is the non-overloaded version of
--   insertSet.
insertSetBy :: (a -> a -> Ordering) -> a -> [a] -> [a]

-- | The isect function computes the intersection of two ordered
--   lists. An element occurs in the output as many times as the minimum
--   number of occurrences in either input. If either input is a set, then
--   the output is a set.
--   
--   
--   isect [ 1,2, 3,4 ] [ 3,4, 5,6 ]   == [ 3,4 ]
--   isect [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1, 2,2 ]
--   
isect :: Ord a => [a] -> [a] -> [a]

-- | The isectBy function is the non-overloaded version of
--   isect.
isectBy :: (a -> b -> Ordering) -> [a] -> [b] -> [a]

-- | The union function computes the union of two ordered lists. An
--   element occurs in the output as many times as the maximum number of
--   occurrences in either input. The output is a set if and only if both
--   inputs are sets.
--   
--   
--   union [ 1,2, 3,4 ] [ 3,4, 5,6 ]   == [ 1,2, 3,4, 5,6 ]
--   union [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1,1,1, 2,2,2 ]
--   
union :: Ord a => [a] -> [a] -> [a]

-- | The unionBy function is the non-overloaded version of
--   union.
unionBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]

-- | The minus function computes the difference of two ordered
--   lists. An element occurs in the output as many times as it occurs in
--   the first input, minus the number of occurrences in the second input.
--   If the first input is a set, then the output is a set.
--   
--   
--   minus [ 1,2, 3,4 ] [ 3,4, 5,6 ]   == [ 1,2 ]
--   minus [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 2 ]
--   
minus :: Ord a => [a] -> [a] -> [a]

-- | The minusBy function is the non-overloaded version of
--   minus.
minusBy :: (a -> b -> Ordering) -> [a] -> [b] -> [a]

-- | The minus' function computes the difference of two ordered
--   lists. The result consists of elements from the first list that do not
--   appear in the second list. If the first input is a set, then the
--   output is a set.
--   
--   
--   minus' [ 1,2, 3,4 ] [ 3,4, 5,6 ]   == [ 1,2 ]
--   minus' [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == []
--   minus' [ 1,1, 2,2 ] [ 2 ]          == [ 1,1 ]
--   
minus' :: Ord a => [a] -> [a] -> [a]

-- | The minusBy' function is the non-overloaded version of
--   minus'.
minusBy' :: (a -> b -> Ordering) -> [a] -> [b] -> [a]

-- | The xunion function computes the exclusive union of two ordered
--   lists. An element occurs in the output as many times as the absolute
--   difference between the number of occurrences in the inputs. If both
--   inputs are sets, then the output is a set.
--   
--   
--   xunion [ 1,2, 3,4 ] [ 3,4, 5,6 ]   == [ 1,2, 5,6 ]
--   xunion [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1,1, 2 ]
--   
xunion :: Ord a => [a] -> [a] -> [a]

-- | The xunionBy function is the non-overloaded version of
--   xunion.
xunionBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]

-- | The merge function combines all elements of two ordered lists.
--   An element occurs in the output as many times as the sum of the
--   occurrences in both lists. The output is a set if and only if the
--   inputs are disjoint sets.
--   
--   
--   merge [ 1,2, 3,4 ] [ 3,4, 5,6 ]   == [ 1,2,  3,3,4,4,  5,6 ]
--   merge [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1,1,1,1,  2,2,2,2,2 ]
--   
merge :: Ord a => [a] -> [a] -> [a]

-- | The mergeBy function is the non-overloaded version of
--   merge.
mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]

-- | The mergeAll function merges a (potentially) infinite number of
--   ordered lists, under the assumption that the heads of the inner lists
--   are sorted. An element is duplicated in the result as many times as
--   the total number of occurrences in all inner lists.
--   
--   The mergeAll function is closely related to foldr
--   merge []. The former does not assume that the outer list
--   is finite, whereas the latter does not assume that the heads of the
--   inner lists are sorted. When both sets of assumptions are met, these
--   two functions are equivalent.
--   
--   This implementation of mergeAll uses a tree of comparisons, and
--   is based on input from Dave Bayer, Heinrich Apfelmus, Omar Antolin
--   Camarena, and Will Ness. See CHANGES for details.
mergeAll :: Ord a => [[a]] -> [a]

-- | The mergeAllBy function is the non-overloaded variant of the
--   mergeAll function.
mergeAllBy :: (a -> a -> Ordering) -> [[a]] -> [a]

-- | The unionAll computes the union of a (potentially) infinite
--   number of lists, under the assumption that the heads of the inner
--   lists are sorted. The result will duplicate an element as many times
--   as the maximum number of occurrences in any single list. Thus, the
--   result is a set if and only if every inner list is a set.
--   
--   The unionAll function is closely related to foldr
--   union []. The former does not assume that the outer list
--   is finite, whereas the latter does not assume that the heads of the
--   inner lists are sorted. When both sets of assumptions are met, these
--   two functions are equivalent.
--   
--   Note that there is no simple way to express unionAll in terms
--   of mergeAll or vice versa on arbitrary valid inputs. They are
--   related via nub however, as nub . mergeAll ==
--   unionAll . map nub. If every list is a set,
--   then map nub == id, and in this special case (and only in
--   this special case) does nub . mergeAll == unionAll.
--   
--   This implementation of unionAll uses a tree of comparisons, and
--   is based on input from Dave Bayer, Heinrich Apfelmus, Omar Antolin
--   Camarena, and Will Ness. See CHANGES for details.
unionAll :: Ord a => [[a]] -> [a]

-- | The unionAllBy function is the non-overloaded variant of the
--   unionAll function.
unionAllBy :: (a -> a -> Ordering) -> [[a]] -> [a]

-- | On ordered lists, nub is equivalent to 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 (<)
--   
nub :: Ord a => [a] -> [a]

-- | The nubBy function is the greedy algorithm that returns a
--   sublist of its input such that:
--   
--   
--   isSortedBy pred (nubBy pred xs) == True
--   
--   
--   This is true for all lists, not just ordered lists, and all binary
--   predicates, not just total orders. On infinite lists, this statement
--   is true in a certain mathematical sense, but not a computational one.
nubBy :: (a -> a -> Bool) -> [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.
--   
--   Elements are arranged from lowest to highest, keeping duplicates in
--   the order they appeared in the input.
--   
--   The argument must be finite.
--   
--   
Examples
--   
--   
--   >>> sort [1,6,4,3,2,5]
--   [1,2,3,4,5,6]
--   
--   
--   
--   >>> sort "haskell"
--   "aehklls"
--   
--   
--   
--   >>> import Data.Semigroup(Arg(..))
--   
--   >>> sort [Arg ":)" 0, Arg ":D" 0, Arg ":)" 1, Arg ":3" 0, Arg ":D" 1]
--   [Arg ":)" 0,Arg ":)" 1,Arg ":3" 0,Arg ":D" 0,Arg ":D" 1]
--   
sort :: Ord a => [a] -> [a]

-- | The sortBy function is the non-overloaded version of
--   sort. The argument must be finite.
--   
--   The supplied comparison relation is supposed to be reflexive and
--   antisymmetric, otherwise, e. g., for _ _ -> GT, the
--   ordered list simply does not exist. The relation is also expected to
--   be transitive: if it is not then sortBy might fail to find an
--   ordered permutation, even if it exists.
--   
--   
Examples
--   
--   
--   >>> sortBy (\(a,_) (b,_) -> compare a b) [(2, "world"), (4, "!"), (1, "Hello")]
--   [(1,"Hello"),(2,"world"),(4,"!")]
--   
sortBy :: (a -> a -> Ordering) -> [a] -> [a]

-- | Sort a list by comparing the results of a key function applied to each
--   element. sortOn f is equivalent to sortBy
--   (comparing f), but has the performance advantage of only
--   evaluating f once for each element in the input list. This is
--   called the decorate-sort-undecorate paradigm, or Schwartzian
--   transform.
--   
--   Elements are arranged from lowest to highest, keeping duplicates in
--   the order they appeared in the input.
--   
--   The argument must be finite.
--   
--   
Examples
--   
--   
--   >>> sortOn fst [(2, "world"), (4, "!"), (1, "Hello")]
--   [(1,"Hello"),(2,"world"),(4,"!")]
--   
--   
--   
--   >>> sortOn length ["jim", "creed", "pam", "michael", "dwight", "kevin"]
--   ["jim","pam","creed","kevin","dwight","michael"]
--   
--   
--   
Performance notes
--   
--   This function minimises the projections performed, by materialising
--   the projections in an intermediate list.
--   
--   For trivial projections, you should prefer using sortBy with
--   comparing, for example:
--   
--   
--   >>> sortBy (comparing fst) [(3, 1), (2, 2), (1, 3)]
--   [(1,3),(2,2),(3,1)]
--   
--   
--   Or, for the exact same API as sortOn, you can use `sortBy .
--   comparing`:
--   
--   
--   >>> (sortBy . comparing) fst [(3, 1), (2, 2), (1, 3)]
--   [(1,3),(2,2),(3,1)]
--   
sortOn :: Ord b => (a -> b) -> [a] -> [a]

-- | This variant of sortOn recomputes the sorting key every
--   comparison. This can be better for functions that are cheap to
--   compute. This is definitely better for projections, as the
--   decorate-sort-undecorate saves nothing and adds two traversals of the
--   list and extra memory allocation.
sortOn' :: Ord b => (a -> b) -> [a] -> [a]

-- | The nubSort function is equivalent to nub .
--   sort, except that duplicates are removed as it sorts. It
--   is essentially the same implementation as Data.List.sort,
--   with merge replaced by union. Thus the performance of
--   nubSort should better than or nearly equal to sort
--   alone. It is faster than both sort and nub .
--   sort when the input contains significant quantities of
--   duplicated elements.
nubSort :: Ord a => [a] -> [a]

-- | The nubSortBy function is the non-overloaded version of
--   nubSort.
nubSortBy :: (a -> a -> Ordering) -> [a] -> [a]

-- | The nubSortOn function provides decorate-sort-undecorate for
--   nubSort.
nubSortOn :: Ord b => (a -> b) -> [a] -> [a]

-- | This variant of nubSortOn recomputes the sorting key for each
--   comparison
nubSortOn' :: Ord b => (a -> b) -> [a] -> [a]

-- | The function foldt plus zero computes the sum of a
--   list using a sequence of balanced trees of operations. Given an
--   appropriate plus operator, this function can be productive on
--   an infinite list, hence it is lazier than foldt'. foldt
--   is used in the implementation of mergeAll and unionAll.
foldt :: (a -> a -> a) -> a -> [a] -> a

-- | The function foldt' plus zero computes the sum of a
--   list using a balanced tree of operations. foldt' necessarily
--   diverges on infinite lists, hence it is a stricter variant of
--   foldt. foldt' is used in the implementation of
--   sort and nubSort.
foldt' :: (a -> a -> a) -> a -> [a] -> a
