Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
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
- toSortedList :: Ord a => [a] -> SortedList a
- fromSortedList :: SortedList a -> [a]
- singleton :: a -> SortedList a
- repeat :: a -> SortedList a
- replicate :: Int -> a -> SortedList a
- iterate :: Ord a => (a -> a) -> a -> SortedList a
- uncons :: SortedList a -> Maybe (a, SortedList a)
- insert :: Ord a => a -> SortedList a -> SortedList a
- take :: Int -> SortedList a -> SortedList a
- drop :: Int -> SortedList a -> SortedList a
- splitAt :: Int -> SortedList a -> (SortedList a, SortedList a)
- filter :: (a -> Bool) -> SortedList a -> SortedList a
- elemOrd :: Ord a => a -> SortedList a -> Bool
- nub :: Eq a => SortedList a -> SortedList a
Type
data SortedList a Source
Type of sorted lists. Any (non-bottom) value of this type is a sorted list.
Foldable SortedList Source | |
Show a => Show (SortedList a) Source | |
Ord a => Monoid (SortedList a) Source |
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
elemOrd :: Ord a => a -> SortedList a -> Bool Source
Others
nub :: Eq a => SortedList a -> SortedList a Source
O(n). Remove duplicate elements from a sorted list.