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

Safe HaskellNone




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.



data SortedList a Source

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


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.


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.


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.


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

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


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.


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.


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.