Data.SortedList

This module defines a type for sorted lists, together with several functions to create and use values of that type. Many operations are optimized to take advantage of the list being sorted.

Type

data SortedList a

Type of sorted lists. Any (non-bottom) value of this type is a sorted list.

Instances

Foldable SortedList

Show a => Show (SortedList a)

Ord a => Monoid (SortedList a)

List conversions

toSortedList :: Ord a => [a] -> SortedList a

Create a SortedList by sorting a regular list.

fromSortedList :: SortedList a -> [a]

Create a list from a SortedList. The returned list is guaranteed to be sorted.

Construction

singleton :: a -> SortedList a

O(1). Create a sorted list with only one element.

repeat :: a -> SortedList a

An infinite list with all its elements equal to the given argument.

replicate :: Int -> a -> SortedList a

Replicate a given number of times a single element.

iterate :: Ord a => (a -> a) -> a -> SortedList a

Create a sorted list by repeatedly applying the same function to an element, until the image by that function is stricly less than its argument. In other words:

iterate f x = [x, f x, f (f x), ... ]

With the list ending whenever f (f (... (f (f x)) ...)) < f (... (f (f x)) ...). If this never happens, the list will be infinite.

Deconstruction

uncons :: SortedList a -> Maybe (a, SortedList a)

Decompose a sorted list into its minimal element and the rest. If the list is empty, it returns Nothing.

Inserting

insert :: Ord a => a -> SortedList a -> SortedList a

O(n). Insert a new element in a sorted list.

Sublists

take :: Int -> SortedList a -> SortedList a

Extract the prefix with the given length from a sorted list.

drop :: Int -> SortedList a -> SortedList a

Drop the given number of elements from a sorted list, starting from the smallest and following ascending order.

splitAt :: Int -> SortedList a -> (SortedList a, SortedList a)

Split a sorted list in two sublists, with the first one having length equal to the given argument, except when the length of the list is less than that.

filter :: (a -> Bool) -> SortedList a -> SortedList a

O(n). Extract the elements of a list that satisfy the predicate.

Queries

null :: SortedList a -> Bool

Check if a sorted list is empty.

elemOrd :: Ord a => a -> SortedList a -> Bool

O(n). An efficient implementation of elem, using the Ord instance of the elements in a sorted list. It only traverses the whole list if the requested element is greater than all the elements in the sorted list.

Others

nub :: Eq a => SortedList a -> SortedList a

O(n). Remove duplicate elements from a sorted list.