%**The Haskell 98 Library Report: Indexing Operations %**~header \section{Indexing Operations} \outline{ \inputHS{lib-hdrs/Ix} } The @Ix@ class is used to map a contiguous subrange of values in a type onto integers. It is used primarily for array indexing (see Chapter~\ref{arrays}). The @Ix@ class contains the methods @range@\indextt{range}, @index@\indextt{index}, and @inRange@\indextt{inRange}. The @index@ operation maps a bounding pair, which defines the lower and upper bounds of the range, and a subscript, to an integer. The @range@ operation enumerates all subscripts; the @inRange@ operation tells whether a particular subscript lies in the range defined by a bounding pair. An implementation is entitled to assume the following laws about these operations: \bprog @ range (l,u) !! index (l,u) i == i -- when i is in range inRange (l,u) i == i `elem` range (l,u) map index (range (l,u)) == [0..rangeSize (l,u)] @ \eprog % It is the responsibility of the programmer to enforce bounds % checking for non-derived instances of class @Ix@, if desired. % An implementation is not required to check that an index % lies within the bounds of an array when accessing that array. \subsection{Deriving Instances of @Ix@} \indexdi{Ix} It is possible to derive an instance of @Ix@ automatically, using a @deriving@ clause on a @data@ declaration (Section~\ref{derived-decls}). Such derived instance declarations for the class @Ix@ are only possible for enumerations\index{enumeration} (i.e.~datatypes having only nullary constructors) and single-constructor datatypes, whose constituent types are instances of @Ix@. A Haskell implementation must provide @Ix@ instances for tuples up to at least size 15. \begin{itemize} \item For an {\em enumeration}, the nullary constructors are assumed to be numbered left-to-right with the indices being $0$ to $n-1\/$ inclusive. This is the same numbering defined by the @Enum@ class. For example, given the datatype: \bprog @ data Colour = Red | Orange | Yellow | Green | Blue | Indigo | Violet @ \eprog we would have: \bprog @ range (Yellow,Blue) == [Yellow,Green,Blue] index (Yellow,Blue) Green == 1 inRange (Yellow,Blue) Red == False @ \eprog \item For {\em single-constructor datatypes}, the derived instance declarations are as shown for tuples in Figure~\ref{prelude-index}. \end{itemize} \begin{figure}[tb] \outline{\small @ instance (Ix a, Ix b) => Ix (a,b) where range ((l,l'),(u,u')) = [(i,i') | i <- range (l,u), i' <- range (l',u')] index ((l,l'),(u,u')) (i,i') = index (l,u) i * rangeSize (l',u') + index (l',u') i' inRange ((l,l'),(u,u')) (i,i') = inRange (l,u) i && inRange (l',u') i' -- Instances for other tuples are obtained from this scheme: -- -- instance (Ix a1, Ix a2, ... , Ix ak) => Ix (a1,a2,...,ak) where -- range ((l1,l2,...,lk),(u1,u2,...,uk)) = -- [(i1,i2,...,ik) | i1 <- range (l1,u1), -- i2 <- range (l2,u2), -- ... -- ik <- range (lk,uk)] -- -- index ((l1,l2,...,lk),(u1,u2,...,uk)) (i1,i2,...,ik) = -- index (lk,uk) ik + rangeSize (lk,uk) * ( -- index (lk-1,uk-1) ik-1 + rangeSize (lk-1,uk-1) * ( -- ... -- index (l1,u1))) -- -- inRange ((l1,l2,...lk),(u1,u2,...,uk)) (i1,i2,...,ik) = -- inRange (l1,u1) i1 && inRange (l2,u2) i2 && -- ... && inRange (lk,uk) ik @ } \ecaption{Derivation of Ix instances} \label{prelude-index} \indexclass{Ix} \indextt{range}\indextt{index}\indextt{inRange} \indextt{rangeSize} \end{figure} \clearpage \subsection{Library {\tt Ix}} \inputHS{lib-code/Ix} %**~footer