Representation of the index of a series. An index is a sequence of sorted elements. All elements are unique, much like a Set.

You can construct an Index from a set (fromSet), from a list (fromList), or from a vector (fromVector). You can also make use of the OverloadedLists extension:

>>> :set -XOverloadedLists
>>> let (ix :: Index Int) = [1, 2, 3]
>>> ix
Index [1,2,3]

Since keys in an Index are always sorted and unique, Index is not a Functor. To map a function over an Index, use map.

\(O(1)\) Create a singleton Index.

\(O(n \log n)\) Create an Index from a seed value. Note that the order in which elements are generated does not matter; elements are stored in order. See the example below.

>>> unfoldr (\x -> if x < 1 then Nothing else Just (x, x-1)) (7 :: Int)
Index [1,2,3,4,5,6,7]

\(O(n \log n)\) Create an Index as a range of values. range f start end will generate an Index with values [start, f start, f (f start), ... ] such that the largest element less or equal to end is included. See examples below.

>>> range (+3) (1 :: Int) 10
Index [1,4,7,10]
>>> range (+3) (1 :: Int) 11
Index [1,4,7,10]

The IsIndex typeclass allow for ad-hoc definition of conversion functions, converting to / from Index.

\(O(1)\) Build an Index from a Set.

\(O(n \log n)\) Build an Index from a list. Note that since an Index is composed of unique elements, the length of the index may not be the same as the length of the input list:

>>> fromList ['c', 'a', 'b', 'b']
Index "abc"

If the list is already sorted, fromAscList is generally faster.

\(O(n \log n)\) Build an Index from a Vector. Note that since an Index is composed of unique elements, the length of the index may not be the same as the length of the input vector:

>>> import Data.Vector as V
>>> fromVector $ V.fromList ['c', 'a', 'b', 'b']
Index "abc"

If the Vector is already sorted, fromAscVector is generally faster.

\(O(1)\) Convert an Index to a Set.

\(O(n)\) Convert an Index to a list. Elements will be produced in ascending order.

\(O(n)\) Convert an Index to a list. Elements will be produced in ascending order.

\(O(1)\) Returns True for an empty Index, and False otherwise.

\(O(n \log n)\) Check whether the element is in the index.

\(O(n \log n)\) Check whether the element is NOT in the index.

\(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\) Union of two Index, containing elements either in the left index, right right index, or both.

\(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\) Intersection of two Index, containing elements which are in both the left index and the right index.

\(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\) Returns the elements of the first index which are not found in the second index.

>>> difference (fromList ['a', 'b', 'c']) (fromList ['b', 'c', 'd'])
Index "a"

\(O(n+m)\). The symmetric difference of two Index. The first element of the tuple is an Index containing all elements which are only found in the left Index, while the second element of the tuple is an Index containing all elements which are only found in the right Index:

>>> left = fromList ['a', 'b', 'c']
>>> right = fromList ['c', 'd', 'e']
>>> left `symmetricDifference` right
(Index "ab",Index "de")

\(O\bigl(m \log\bigl(\frac{n+1}{m+1}\bigr)\bigr), \; m \leq n\). (ix1 'contains' ix2) indicates whether all keys in ix2 are also in ix1.

\(O(1)\) Returns the number of keys in the index.

\(O(\log n)\). Take n elements from the index, in ascending order. Taking more than the number of elements in the index is a no-op:

>>> take 10 $ fromList [1::Int,2,3]
Index [1,2,3]

\(O(\log n)\). Drop n elements from the index, in ascending order.

\(O(n \log n)\) Map a function over keys in the index. Note that since keys in an Index are unique, the length of the resulting index may not be the same as the input:

>>> map (\x -> if even x then 0::Int else 1) $ fromList [0::Int,1,2,3,4]
Index [0,1]

If the mapping is monotonic, see mapMonotonic, which has better performance characteristics.

\(O(n)\) Filter elements satisfying a predicate.

>>> filter even $ fromList [1::Int,2,3,4,5]
Index [2,4]

\(O(n \log n)\). Map each element of an Index to an applicative action, evaluate these actions from left to right, and collect the results.

Note that the data type Index is not a member of Traversable because it is not a Functor.

\(O(\log n)\). Returns the integer index of a key, if the key is in the index.

>>> lookupIndex 'b' $ fromList ['a', 'b', 'c']
Just 1
>>> lookupIndex 'd' $ fromList ['a', 'b', 'c']
Nothing

\(O(\log n)\). Insert a key in an Index. If the key is already present, the Index will not change.

\(O(\log n)\). Delete a key from an Index, if this key is present in the index.