-- 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 -- | 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. 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 occurences 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 -> a -> Ordering) -> [a] -> [a] -> [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 -- occurences in either input. If both inputs are sets, then the output -- is a set. -- -- 
--   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 -> a -> Ordering) -> [a] -> [a] -> [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 -- occurences in the lists. -- -- 
--   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 generalizes "foldr merge -- []" to a (possibly infinite) list of (possibly infinite) ordered -- lists. To make this possible, it adds the assumption that the heads of -- the non-empty lists themselves form a sorted list. -- -- The implementation is based on the article "Implicit Heaps" by -- Heinrich Apfelmus, which simplifies an algorithm by Dave Bayer. -- -- http://apfelmus.nfshost.com/articles/implicit-heaps.html -- -- The following definition is a simple and reasonably efficient -- implementation that is faster for inputs whose smallest elements are -- highly biased towards the first few lists: -- -- 
--   mergeAll' = foldr merge' []
--     where  merge' []     ys = ys
--            merge' (x:xs) ys = x : merge xs ys
--
-- -- This definition uses a linear chain of comparisons whereas the -- provided implementation uses a tree of comparisons, which is faster on -- a wide range of inputs. 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 function generalizes "foldr union -- []" to a (possibly infinite) list of (possibly infinite) ordered -- lists. To make this possible, it adds the assumption that the heads of -- the non-empty lists themselves form a sorted list. -- -- The library implementation is based on some of the same techniques as -- used in mergeAll. However, the analogous simple definition is -- not entirely satisfactory, because -- -- 
--   unionAll' = foldr union' []
--     where  union' []     ys = ys
--            union' (x:xs) ys = x : union xs ys
--   
--   unionAll' [[1,2],[1,2]] == [1,1,2]
--
-- -- whereas we really want the result -- -- 
--   unionAll [[1,2],[1,2]] == foldr union [] [[1,2],[1,2]] == [1,2]
--
-- -- The first equality is only true when both sets of assumptions are met: -- "foldr union []" assumes the outer list is finite, and unionAll -- assumes that the heads of the inner lists are sorted. 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 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 (<)
--
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. sort :: (Ord a) => [a] -> [a] -- | The sortBy function is the non-overloaded version of -- sort. sortBy :: (a -> a -> Ordering) -> [a] -> [a] -- | The sortOn function provides the decorate-sort-undecorate -- idiom, also known as the "Schwartzian transform". 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 somewhat more efficient as duplicates are removed -- as it sorts. It is essentially Data.List.sort, a mergesort by Ian -- Lynagh, with merge replaced by union. 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 for each comparison. nubSortOn' :: (Ord b) => (a -> b) -> [a] -> [a]