be1ffd1c5311760f2b686547687b23c476cf75a7
[haskell-report.git] / report / ix.verb
1 %**<title>The Haskell 98 Library Report: Indexing Operations</title>
2 %**~header
3 \section{Indexing Operations}
4
5 \outline{
6 \inputHS{lib-hdrs/Ix}
7 }
8 The @Ix@ class is used to map a contiguous subrange of values in a
9 type onto integers.  It is used primarily for array indexing (see
10 Chapter~\ref{arrays}).
11 The @Ix@ class contains the methods @range@\indextt{range},
12 @index@\indextt{index}, and @inRange@\indextt{inRange}. 
13 The @index@ operation maps a bounding pair, which defines the lower
14 and upper bounds of the range, and a 
15 subscript, to an integer.  The @range@ operation enumerates all
16 subscripts; the @inRange@ operation tells whether a particular subscript
17 lies in the range defined by a bounding pair.
18
19 An implementation is entitled to assume the following laws about these
20 operations:
21 \bprog
22 @
23    range (l,u) !! index (l,u) i == i   -- when i is in range
24    inRange (l,u) i              == i `elem` range (l,u)
25    map index (range (l,u))      == [0..rangeSize (l,u)]
26 @
27 \eprog
28
29 % It is the responsibility of the programmer to enforce bounds
30 % checking for non-derived instances of class @Ix@, if desired.
31 % An implementation is not required to check that an index
32 % lies within the bounds of an array when accessing that array.
33
34 \subsection{Deriving Instances of @Ix@}
35 \index{Ix@@{\tt Ix}!derived instance}
36
37 It is possible to derive an instance of @Ix@ automatically, using
38 a @deriving@ clause on a @data@ declaration (Section~\ref{derived-decls}).
39 Such derived instance declarations for the class @Ix@ are only possible
40 for enumerations\index{enumeration} (i.e.~datatypes having
41 only nullary constructors) and single-constructor datatypes,
42 whose constituent types are instances of @Ix@.   A Haskell implementation
43 must provide @Ix@ instances for tuples up to at least size 15.
44
45 \begin{itemize}
46 \item
47 For an {\em enumeration}, the nullary constructors are assumed to be
48 numbered left-to-right with the indices being $0$ to $n-1\/$ inclusive.
49 This is the same numbering defined by the @Enum@ class.  For example,
50 given the datatype:
51 \bprog
52 @
53 data Colour = Red | Orange | Yellow | Green | Blue | Indigo | Violet
54 @
55 \eprog
56 we would have:
57 \bprog
58 @
59 range   (Yellow,Blue)        ==  [Yellow,Green,Blue]
60 index   (Yellow,Blue) Green  ==  1
61 inRange (Yellow,Blue) Red    ==  False
62 @
63 \eprog
64 \item
65 For {\em single-constructor datatypes}, the derived instance declarations
66 are as shown for tuples in
67 Figure~\ref{prelude-index}.
68 \end{itemize}
69
70 \begin{figure}[tb]
71 \outline{\small
72 @
73 instance  (Ix a, Ix b)  => Ix (a,b) where
74         range ((l,l'),(u,u'))
75                 = [(i,i') | i <- range (l,u), i' <- range (l',u')]
76         index ((l,l'),(u,u')) (i,i')
77                 =  index (l,u) i * rangeSize (l',u') + index (l',u') i'
78         inRange ((l,l'),(u,u')) (i,i')
79                 = inRange (l,u) i && inRange (l',u') i'
80
81 -- Instances for other tuples are obtained from this scheme:
82 --
83 --  instance  (Ix a1, Ix a2, ... , Ix ak) => Ix (a1,a2,...,ak)  where
84 --      range ((l1,l2,...,lk),(u1,u2,...,uk)) =
85 --          [(i1,i2,...,ik) | i1 <- range (l1,u1),
86 --                            i2 <- range (l2,u2),
87 --                            ...
88 --                            ik <- range (lk,uk)]
89 --
90 --      index ((l1,l2,...,lk),(u1,u2,...,uk)) (i1,i2,...,ik) =
91 --        index (lk,uk) ik + rangeSize (lk,uk) * (
92 --         index (lk-1,uk-1) ik-1 + rangeSize (lk-1,uk-1) * (
93 --          ...
94 --           index (l1,u1)))
95 --
96 --      inRange ((l1,l2,...lk),(u1,u2,...,uk)) (i1,i2,...,ik) =
97 --          inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
98 --              ... && inRange (lk,uk) ik
99 @
100 }
101 \ecaption{Derivation of Ix instances}
102 \label{prelude-index}
103 \indextt{Ix}                                                
104 \indextt{range}\indextt{index}\indextt{inRange}   
105 \indextt{rangeSize}                                         
106 \end{figure}
107
108 \clearpage
109 \subsection{Library {\tt Ix}}
110 \inputHS{lib-code/Ix}
111
112 %**~footer