Ix and a few typos
[haskell-report.git] / libraries / ix.verb
1 %**<title>The Haskell 98 Library Report: Indexing Operations</title>
2 %**~header
3 \section{Indexing Operations}
4
5 \outline{
6 \inputHS{headers/Ix}
7 }
8 The @Ix@ class is used to map a continuous subrange of values in a
9 type onto integers.  It is used primarily for array indexing (see
10 Section~\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 Derived instance declarations for the class @Ix@ are only possible
38 for enumerations\index{enumeration} (i.e.~datatypes having
39 only nullary constructors) and single-constructor datatypes,
40 including arbitrarily large tuples, whose constituent types are
41 instances of @Ix@.   
42 \begin{itemize}
43 \item
44 For an {\em enumeration}, the nullary constructors are assumed to be
45 numbered left-to-right with the indices being $0$ to $n-1\/$ inclusive.
46 This is the same numbering defined by the @Enum@ class.  For example,
47 given the datatype:
48 \bprog
49 @
50 data Colour = Red | Orange | Yellow | Green | Blue | Indigo | Violet
51 @
52 \eprog
53 we would have:
54 \bprog
55 @
56 range   (Yellow,Blue)        ==  [Yellow,Green,Blue]
57 index   (Yellow,Blue) Green  ==  1
58 inRange (Yellow,Blue) Red    ==  False
59 @
60 \eprog
61 \item
62 For {\em single-constructor datatypes}, the derived instance declarations
63 are as shown for tuples in
64 Figure~\ref{prelude-index}.
65 \end{itemize}
66
67 \begin{figure}[tb]
68 \outline{
69 @
70 instance  (Ix a, Ix b)  => Ix (a,b) where
71         range ((l,l'),(u,u'))
72                 = [(i,i') | i <- range (l,u), i' <- range (l',u')]
73         index ((l,l'),(u,u')) (i,i')
74                 =  index (l,u) i * rangeSize (l',u') + index (l',u') i'
75         inRange ((l,l'),(u,u')) (i,i')
76                 = inRange (l,u) i && inRange (l',u') i'
77
78 -- Instances for other tuples are obtained from this scheme:
79 --
80 --  instance  (Ix a1, Ix a2, ... , Ix ak) => Ix (a1,a2,...,ak)  where
81 --      range ((l1,l2,...,lk),(u1,u2,...,uk)) =
82 --          [(i1,i2,...,ik) | i1 <- range (l1,u1),
83 --                            i2 <- range (l2,u2),
84 --                            ...
85 --                            ik <- range (lk,uk)]
86 --
87 --      index ((l1,l2,...,lk),(u1,u2,...,uk)) (i1,i2,...,ik) =
88 --        index (lk,uk) ik + rangeSize (lk,uk) * (
89 --         index (lk-1,uk-1) ik-1 + rangeSize (lk-1,uk-1) * (
90 --          ...
91 --           index (l1,u1)))
92 --
93 --      inRange ((l1,l2,...lk),(u1,u2,...,uk)) (i1,i2,...,ik) =
94 --          inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
95 --              ... && inRange (lk,uk) ik
96 @
97 }
98 \ecaption{Derivation of Ix instances}
99 \label{prelude-index}
100 \indextt{Ix}                                                
101 \indextt{range}\indextt{index}\indextt{inRange}   
102 \indextt{rangeSize}                                         
103 \end{figure}
104
105 \clearpage
106 \subsection{Library {\tt Ix}}
107 \inputHS{code/Ix}
108
109 %**~footer