Portability	portable
Stability	experimental
Maintainer	leon@melding-monads.com

Data.List.Ordered

Contents

Description

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.

Synopsis

Predicates

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

member returns True if the element appears in the ordered list

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

memberBy is the non-overloaded version of member

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

has returns True if the element appears in the list; it is a function from an ordered list to its characteristic function.

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

hasBy is the non-overloaded version of has

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

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

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

subsetBy is the non-overloaded version of subset

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

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

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

isSortedBy returns True if the predicate returns true for all adjacent pairs of elements in the list

Insertion Functions

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

insertBag inserts an element into a list, allowing for duplicate elements

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

insertBagBy is the non-overloaded version of insertBag

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

insertSet inserts an element into an ordered list, or replaces the first occurrence if it is already there.

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

insertSetBy is the non-overloaded version of insertSet

Set-like operations

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

isect computes the intersection of two ordered lists. The result contains those elements contained in both arguments

 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]

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

isectBy is the non-overloaded version of isect

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

union 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.

 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]

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

unionBy is the non-overloaded version of union

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

minus 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.

 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]

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

minusBy is the non-overloaded version of minus

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

xunion computes the multiset exclusive union of two ordered lists. The result contains those elements that appear in either list, but not both.

 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]

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

xunionBy is the non-overloaded version of xunion

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

merge 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.

 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]

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

mergeBy is the non-overloaded version of merge

Lists to Ordered Lists

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

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]Source

nubBy is the greedy algorithm that returns a sublist of its input such that isSortedBy is true.

 isSortedBy pred (nubBy pred xs) == True

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

sortOn provides the decorate-sort-undecorate idiom, aka the "Schwartzian transform"

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

This variant of sortOn recomputes the function to sort on every comparison. This can is better for functions that are cheap to compute, including projections.

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

nubSort 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]Source

nubSortBy is the non-overloaded version of nubSort

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

nubSortOn provides decorate-sort-undecorate for nubSort

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

This variant of nubSortOn recomputes the function for each comparison.