sorted-list-0.1.4.2: 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 Eq a => Eq (SortedList a) Ord a => Ord (SortedList a) Show a => Show (SortedList a) Ord a => Monoid (SortedList a) NFData a => NFData (SortedList a)

# List conversions

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

Create a `SortedList` by sorting a regular list.

fromSortedList :: SortedList a -> [a] Source

O(1). 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.

By definition:

`iterate f = unfoldr (\x -> Just (x, f x))`

# Deconstruction

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

O(1). 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.

takeWhile :: (a -> Bool) -> SortedList a -> SortedList a Source

Return the longest prefix of a sorted list of elements that satisfy the given condition.

dropWhile :: (a -> Bool) -> SortedList a -> SortedList a Source

Return the suffix remaining after dropping the longest prefix of elements that satisfy the given condition.

span :: (a -> Bool) -> SortedList a -> (SortedList a, SortedList a) Source

Return the longest prefix of a sorted list of elements that satisfy the given condition, and the rest of the list.

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

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

partition :: (a -> Bool) -> SortedList a -> (SortedList a, SortedList a) Source

O(n). Divide a sorted list into two lists, one with all the elements that satisfy the given predicate, and another list with the rest of elements.

# Queries

null :: SortedList a -> Bool Source

Check if a sorted list is empty.

This function dissappears in `base` version 4.8.0.0 in favor of `null` from Data.Foldable.

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.

findIndices :: (a -> Bool) -> SortedList a -> SortedList Int Source

Return the indices of all elements in a sorted list that satisfy the given condition.

# `map` function

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

The complexity range goes from O(n) (if the function is monotonically increasing) to O(n²) (if the function is monotonically decreasing). These are the best and worst case scenarios. We provide an alternative (`mapDec`) where monotonically decreasing functions are the best case scenario.

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

Just like `map`, but favoring functions that are monotonically decreasing instead of those that are monotonically increasing.

# Unfolding

unfoldr :: Ord a => (b -> Maybe (a, b)) -> b -> SortedList a Source

Dual (sort of) to `foldr` for sorted lists. It builds a sorted list from a generator function and an initial element. The generator function is applied to the initial element, and then it will produce either `Nothing` - meaning that the list building must stop - or `Just` applied to the value that is going to be added to the list, and a new accumulator to be fed to the generator function. The list building will stop prematurely if the generator function happens to create an element for the list that is strictly smaller than the previous value.

# Others

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

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

O(n). Reverse a sorted list. The result uses `Down`, thus it is a sorted list as well. The following equality holds for any sorted list `xs`:

`map Down xs = reverse xs`

Only available from `base` version 4.6.0.0.

O(n). Reverse a sorted list with elements embedded in the `Down` type.

Only available from `base` version 4.6.0.0.