sorted-list-0.1.2.0: Type-enforced sorted lists and related functions.

Data.SortedList

Description

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.

Synopsis

# Type

data SortedList a Source

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 Source

Create a `SortedList` by sorting a regular list.

fromSortedList :: SortedList a -> [a] Source

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

# Construction

singleton :: a -> SortedList a Source

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

repeat :: a -> SortedList a Source

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

replicate :: Int -> a -> SortedList a Source

Replicate a given number of times a single element.

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

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

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 Source

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

# Sublists

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

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

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

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

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 Source

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

# Queries

null :: SortedList a -> Bool Source

Check if a sorted list is empty.

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

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

map :: Ord b => (a -> b) -> SortedList a -> SortedList b Source

Map a function over all the elements of a sorted list. Note that `map` will hang if the argument is an infinite list.

Even though `SortedList` can't be made an instance of `Functor`, `map` does hold the `Functor` laws. The problem to write the the instance is the `Ord` instance requirement on the type of the elements of the result list. Therefore, while `SortedList` is not a functor type in general, it is when restricted to elements of orderable types.

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

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