1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
%**<title>The Haskell 98 Library Report: Indexing Operations</title>
%**~header
\section{Indexing Operations}
\outline{
\inputHS{headers/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
Section~\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@}
\index{Ix@@{\tt Ix}!derived instance}
It is possible to derive an instance of @Ix@ automatically, using
a @deriving@ clause on a @data@ declaration (Section~4.3.3
of the Language Report).
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{
@
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}
\indextt{Ix}
\indextt{range}\indextt{index}\indextt{inRange}
\indextt{rangeSize}
\end{figure}
\clearpage
\subsection{Library {\tt Ix}}
\inputHS{code/Ix}
%**~footer
|
