Data.List.Ordered

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.

Predicates

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

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

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

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

has :: Ord a => [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.

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

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

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

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

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

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

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

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

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]

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]

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

insertSet :: Ord a => 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.

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

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

Set-like operations

isect :: Ord a => [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 ]

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

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

union :: Ord a => [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 ]

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

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

minus :: Ord a => [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 ]

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

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

xunion :: Ord a => [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 ]

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

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

merge :: Ord a => [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 ]

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

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

mergeAll :: Ord 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 simplification uses a linear chain of comparisons. The implementation provided uses a tree of comparisons, which is faster on a wide range of inputs.

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

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

unionAll :: Ord a => [[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.

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

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

Lists to Ordered Lists

nub :: Ord a => [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 (<)

nubBy :: (a -> a -> Bool) -> [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.

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]

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.

nubSort :: Ord a => [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.

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

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

nubSortOn :: Ord b => (a -> b) -> [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.