Safe Haskell | None |
---|---|
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
- null :: SortedList a -> Bool
- elemOrd :: Ord a => a -> SortedList a -> Bool
- map :: Ord b => (a -> b) -> SortedList a -> SortedList b
- 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 | |
Eq a => Eq (SortedList a) | |
Ord a => Ord (SortedList a) | |
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
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.