Copyright	(c) 2009-2011 Leon P Smith
License	BSD3
Maintainer	leon@melding-monads.com
Stability	experimental
Portability	portable
Safe Haskell	Safe-Inferred
Language	Haskell98

Data.List.Ordered

Contents

Predicates
Insertion Functions
Set-like operations
Lists to Ordered Lists
Miscellaneous folds

Description

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.

Synopsis

Predicates

member :: Ord a => a -> [a] -> Bool Source

The member function returns True if the element appears in the ordered list.

memberBy :: (a -> a -> Ordering) -> a -> [a] -> Bool Source

The memberBy function is the non-overloaded version of member.

has :: Ord a => [a] -> a -> Bool Source

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.

hasBy :: (a -> a -> Ordering) -> [a] -> a -> Bool Source

The hasBy function is the non-overloaded version of has.

subset :: Ord a => [a] -> [a] -> Bool Source

The subset function returns true if the first list is a sub-list of the second.

subsetBy :: (a -> a -> Ordering) -> [a] -> [a] -> Bool Source

The subsetBy function is the non-overloaded version of subset.

isSorted :: Ord a => [a] -> Bool Source

The isSorted predicate returns True if the elements of a list occur in non-descending order, equivalent to isSortedBy (<=).

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

The isSortedBy function returns True iff the predicate returns true for all adjacent pairs of elements in the list.

Insertion Functions

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

The insertBag function inserts an element into a list. If the element is already there, then another copy of the element is inserted.

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

The insertBagBy function is the non-overloaded version of insertBag.

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

The insertSet function inserts an element into an ordered list. If the element is already there, then the element replaces the existing element.

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

The insertSetBy function is the non-overloaded version of insertSet.

Set-like operations

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

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 ]

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

The isectBy function is the non-overloaded version of isect.

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

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 ]

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

The unionBy function is the non-overloaded version of union.

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

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 ]

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

The minusBy function is the non-overloaded version of minus.

minus' :: Ord a => [a] -> [a] -> [a] Source

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 ]

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

The minusBy' function is the non-overloaded version of minus'.

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

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 ]

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

The xunionBy function is the non-overloaded version of xunion.

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

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 ]

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

The mergeBy function is the non-overloaded version of merge.

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

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.

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

The mergeAllBy function is the non-overloaded variant of the mergeAll function.

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

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.

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

The unionAllBy function is the non-overloaded variant of the unionAll function.

Lists to Ordered Lists

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

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 (<)

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

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.

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

The sortOn function provides the decorate-sort-undecorate idiom, also known as the "Schwartzian transform".

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

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.

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

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.

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

The nubSortBy function is the non-overloaded version of nubSort.

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

The nubSortOn function provides decorate-sort-undecorate for nubSort.

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

This variant of nubSortOn recomputes the sorting key for each comparison

Miscellaneous folds

foldt :: (a -> a -> a) -> a -> [a] -> a Source

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 Source

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.