-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Type-enforced sorted lists and related functions.
--   
--   Type-enforced sorted lists and related functions.
--   
--   These are useful for:
--   
--   <ul>
--   <li>Constraining the argument of a function to be a sorted list by
--   stating in your type that the input list is a sorted list.</li>
--   <li>Avoiding sorting a list twice.</li>
--   <li>Creating a list that is sorted from the moment of its
--   construction, so it doesn't have to be sorted later.</li>
--   <li>Performing list operations keeping the input list sorted.</li>
--   <li>Improving those list operations that can be benefited from the
--   ordering of its elements.</li>
--   <li>Creating infinite lists that are sorted!</li>
--   <li>And more!</li>
--   </ul>
--   
--   If you are missing a feature, do not hesitate to ask by opening an
--   issue at the bug-tracker.
@package sorted-list
@version 0.2.0.0


-- | 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.
module Data.SortedList

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

-- | Create a <a>SortedList</a> by sorting a regular list.
toSortedList :: Ord a => [a] -> SortedList a

-- | <i>O(1)</i>. Create a list from a <a>SortedList</a>. The returned list
--   is guaranteed to be sorted.
fromSortedList :: SortedList a -> [a]

-- | <i>O(1)</i>. Create a sorted list with only one element.
singleton :: a -> SortedList a

-- | An infinite list with all its elements equal to the given argument.
repeat :: a -> SortedList a

-- | Replicate a given number of times a single element.
replicate :: Int -> a -> SortedList a

-- | 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:
--   
--   <pre>
--   iterate f x = [x, f x, f (f x), ... ]
--   </pre>
--   
--   With the list ending whenever <tt>f (f (... (f (f x)) ...)) &lt; f
--   (... (f (f x)) ...)</tt>. If this never happens, the list will be
--   infinite.
--   
--   By definition:
--   
--   <pre>
--   iterate f = unfoldr (\x -&gt; Just (x, f x))
--   </pre>
iterate :: Ord a => (a -> a) -> a -> SortedList a

-- | <i>O(1)</i>. Decompose a sorted list into its minimal element and the
--   rest. If the list is empty, it returns <a>Nothing</a>.
uncons :: SortedList a -> Maybe (a, SortedList a)

-- | <i>O(n)</i>. Insert a new element in a sorted list.
insert :: Ord a => a -> SortedList a -> SortedList a

-- | Delete the first occurrence of the given element.
delete :: Eq a => a -> SortedList a -> SortedList a

-- | Extract the prefix with the given length from a sorted list.
take :: Int -> SortedList a -> SortedList a

-- | Drop the given number of elements from a sorted list, starting from
--   the smallest and following ascending order.
drop :: Int -> SortedList a -> SortedList a

-- | 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.
splitAt :: Int -> SortedList a -> (SortedList a, SortedList a)

-- | Return the longest prefix of a sorted list of elements that satisfy
--   the given condition.
takeWhile :: (a -> Bool) -> SortedList a -> SortedList a

-- | Return the suffix remaining after dropping the longest prefix of
--   elements that satisfy the given condition.
dropWhile :: (a -> Bool) -> SortedList a -> SortedList a

-- | Return the longest prefix of a sorted list of elements that satisfy
--   the given condition, and the rest of the list.
span :: (a -> Bool) -> SortedList a -> (SortedList a, SortedList a)

-- | <i>O(n)</i>. Extract the elements of a list that satisfy the
--   predicate.
filter :: (a -> Bool) -> SortedList a -> SortedList a

-- | <i>O(n)</i>. Select only elements less or equal to the argument.
filterLE :: Ord a => a -> SortedList a -> SortedList a

-- | <i>O(n)</i>. Select only elements greater or equal to the argument.
filterGE :: Ord a => a -> SortedList a -> SortedList a

-- | <i>O(n)</i>. 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.
partition :: (a -> Bool) -> SortedList a -> (SortedList a, SortedList a)

-- | <i>O(n)</i>. An efficient implementation of <a>elem</a>, using the
--   <a>Ord</a> 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.
elemOrd :: Ord a => a -> SortedList a -> Bool

-- | Return the indices of all elements in a sorted list that satisfy the
--   given condition.
findIndices :: (a -> Bool) -> SortedList a -> SortedList Int

-- | Map a function over all the elements of a sorted list. Note that
--   <a>map</a> will hang if the argument is an infinite list.
--   
--   Even though <a>SortedList</a> can't be made an instance of
--   <a>Functor</a>, <a>map</a> <i>does</i> hold the <a>Functor</a> laws
--   (for finite lists). We can't however write an instance because of the
--   <a>Ord</a> instance requirement on the type of the elements of the
--   result list. Therefore, while <a>SortedList</a> is not a functor type
--   in general, it is when restricted to elements of orderable types (for
--   finite lists).
--   
--   The complexity range goes from <i>O(n)</i> (if the function is
--   monotonically increasing) to <i>O(n²)</i> (if the function is
--   monotonically decreasing). These are the best and worst case
--   scenarios. We provide an alternative (<a>mapDec</a>) where
--   monotonically decreasing functions are the best case scenario.
map :: Ord b => (a -> b) -> SortedList a -> SortedList b

-- | Just like <a>map</a>, but favoring functions that are monotonically
--   decreasing instead of those that are monotonically increasing.
mapDec :: Ord b => (a -> b) -> SortedList a -> SortedList b

-- | Dual (sort of) to <a>foldr</a> 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 <a>Nothing</a> - meaning that the list building must stop - or
--   <a>Just</a> 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.
unfoldr :: Ord a => (b -> Maybe (a, b)) -> b -> SortedList a

-- | <i>O(n)</i>. Remove duplicate elements from a sorted list.
nub :: Eq a => SortedList a -> SortedList a

-- | <i>O(n)</i>. Reverse a sorted list. The result uses <a>Down</a>, thus
--   it is a sorted list as well. The following equality holds for any
--   sorted list <tt>xs</tt>:
--   
--   <pre>
--   map Down xs = reverse xs
--   </pre>
--   
--   <i>Only available from <tt>base</tt> version 4.6.0.0.</i>
reverse :: SortedList a -> SortedList (Down a)

-- | <i>O(n)</i>. Reverse a sorted list with elements embedded in the
--   <a>Down</a> type.
--   
--   <i>Only available from <tt>base</tt> version 4.6.0.0.</i>
reverseDown :: SortedList (Down a) -> SortedList a
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.SortedList.SortedList a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.SortedList.SortedList a)
instance GHC.Show.Show a => GHC.Show.Show (Data.SortedList.SortedList a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.SortedList.SortedList a)
instance GHC.Classes.Ord a => GHC.Exts.IsList (Data.SortedList.SortedList a)
instance GHC.Classes.Ord a => GHC.Base.Monoid (Data.SortedList.SortedList a)
instance Data.Foldable.Foldable Data.SortedList.SortedList
