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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
|
<p>
<title>The Haskell 98 Report: Derived Instances</title>
<body bgcolor="#ffffff"> <i>The Haskell 98 Report</i><br> <a href="index.html">top</a> | <a href="literate.html">back</a> | <a href="pragmas.html">next</a> | <a href="index98.html">contents</a> | <a href="prelude-index.html">function index</a> <br><hr>
<a name="derived-appendix"></a><p>
<a name="sectD"></a>
<h2>D<tt> </tt>Specification of Derived Instances</h2>
A <I>derived instance</I> is an instance declaration that is generated
automatically in conjunction with a <tt>data</tt> or <tt>newtype</tt> declaration.
The body of a derived instance declaration is derived syntactically from
the definition of the associated type. Derived instances are
possible only for classes known to the compiler: those defined in
either the Prelude or a standard library. In this appendix, we
describe the derivation of classes defined by the Prelude.<p>
If <I>T</I> is an algebraic datatype declared by:
<p>
<table >
<tr><td>
<tt>data </tt><I>cx</I><tt> =></tt><I> T u</I><sub><I>1</I></sub><I> ... u</I><sub><I>k</I></sub></td><td align=center><tt>=</tt></td><td><I>K</I><sub><I>1</I></sub><I> t</I><sub><I>11</I></sub><I> ... t</I><sub><I>1k</I><sub><I>1</I></sub></sub><I> </I><tt>|</tt><I> ...</I><tt>|</tt><I> K</I><sub><I>n</I></sub><I> t</I><sub><I>n1</I></sub><I> ... t</I><sub><I>nk</I><sub><I>n</I></sub></sub></td></tr><tr><td></td><td align=center> </td><td> <tt>deriving (</tt><I>C</I><sub><I>1</I></sub><tt>,</tt><I> ...</I><tt>,</tt><I> C</I><sub><I>m</I></sub><tt>)
</tt></td></tr></table>
<p>
(where <I>m>=0</I> and the parentheses may be omitted if <I>m=1</I>) then
a derived instance declaration is possible for a class <I>C</I>
if these conditions hold:
<OL><LI>
<I>C</I> is one of <tt>Eq</tt>, <tt>Ord</tt>, <tt>Enum</tt>, <tt>Bounded</tt>, <tt>Show</tt>, or <tt>Read</tt>.<p>
<LI>
There is a context <I>cx'</I> such that <I>cx' =>C t</I><sub><I>ij</I></sub>
holds for each of the constituent types <I>t</I><sub><I>ij</I></sub>.<p>
<LI>
If <I>C</I> is <tt>Bounded</tt>, the type must be either an enumeration (all
constructors must by nullary) or have only one constructor.<p>
<LI>
If <I>C</I> is <tt>Enum</tt>, the type must be an enumeration.<p>
<LI>
There must be no explicit instance declaration elsewhere in the program that
makes <I>T u</I><sub><I>1</I></sub><I> ... u</I><sub><I>k</I></sub> an instance of <I>C</I>.
</OL>
For the purposes of derived instances, a <tt>newtype</tt> declaration is
treated as a <tt>data</tt> declaration with a single constructor.<p>
If the <tt>deriving</tt> form is present,
an instance declaration is automatically generated for <I>T u</I><sub><I>1</I></sub><I> ... u</I><sub><I>k</I></sub>
over each class <I>C</I><sub><I>i</I></sub>.
If the derived instance declaration is impossible for any of the <I>C</I><sub><I>i</I></sub>
then a static error results.
If no derived instances are required, the <tt>deriving</tt> form may be
omitted or the form <tt>deriving ()</tt> may be used.<p>
Each derived instance declaration will have the form:
<p>
<tt>instance (</tt><I>cx</I><tt>,</tt><I> C'</I><sub><I>1</I></sub><I> u'</I><sub><I>1</I></sub><tt>,</tt><I> ...</I><tt>,</tt><I> C'</I><sub><I>j</I></sub><I> u'</I><sub><I>j</I></sub><I> </I><tt>) =></tt><I> C</I><sub><I>i</I></sub><I> (T u</I><sub><I>1</I></sub><I> ... u</I><sub><I>k</I></sub><I>) </I><tt>where</tt><I> </I><tt>{</tt><I> d </I><tt>}
<p>
</tt>where <I>d</I> is derived automatically depending on <I>C</I><sub><I>i</I></sub> and the data
type declaration for <I>T</I> (as will be described in the remainder of
this section), and <I>u'</I><sub><I>1</I></sub> through <I>u'</I><sub><I>j</I></sub> form a subset of <I>u</I><sub><I>1</I></sub>
through <I>u</I><sub><I>k</I></sub>.
When inferring the context for the derived instances, type synonyms
must be expanded out first.
Free names in the declarations d are all
defined in the Prelude; the qualifier `<tt>Prelude.</tt>' is
implicit here. The remaining details of the derived
instances for each of the derivable Prelude classes are now given.<p>
<a name="sectD.1"></a>
<h3>D.1<tt> </tt>Derived instances of <tt>Eq</tt> and <tt>Ord</tt>.</h3>
The class methods automatically introduced by derived instances
of <tt>Eq</tt> and <tt>Ord</tt> are <tt>(==)</tt>,
<tt>(/=)</tt>,
<tt>compare</tt>,
<tt>(<)</tt>,
<tt>(<=)</tt>,
<tt>(>)</tt>,
<tt>(>=)</tt>,
<tt>max</tt>, and
<tt>min</tt>. The latter seven operators are defined so
as to compare their arguments lexicographically with respect to
the constructor set given, with earlier constructors in the datatype
declaration counting as smaller than later ones. For example, for the
<tt>Bool</tt> datatype, we have that <tt>(True > False) == True</tt>.<p>
Derived comparisons always traverse constructors from left to right.
These examples illustrate this property:
<tt><br>
<br>
(1,undefined) == (2,undefined) </tt><I>=></I><tt> False<br>
(undefined,1) == (undefined,2) </tt><I>=></I><tt> </tt><I>_|_</I><tt><br>
<br>
<p>
</tt><a name="sectD.2"></a>
<h3>D.2<tt> </tt>Derived instances of <tt>Enum</tt></h3>
Derived instance declarations for the class <tt>Enum</tt> are only
possible for enumerations.
<tt>Enum</tt> introduces the class methods
<tt>succ</tt>,
<tt>pred</tt>,
<tt>toEnum</tt>,
<tt>fromEnum</tt>,
<tt>enumFrom</tt>,
<tt>enumFromThen</tt>,
<tt>enumFromTo</tt>, and
<tt>enumFromThenTo</tt>.
The latter four are used to define arithmetic sequences as described
in Section <a href="exps.html#arithmetic-sequences">3.10</a>. <p>
The nullary constructors are assumed to be
numbered left-to-right with the indices 0 through n-1.
The <tt>succ</tt> and <tt>pred</tt> operators give the successor and predecessor
respectively of a value, under this numbering scheme. It is
an error to apply <tt>succ</tt> to the maximum element, or <tt>pred</tt> to the minimum
element.<p>
The <tt>toEnum</tt> and <tt>fromEnum</tt> operators map enumerated values to and
from the <tt>Int</tt> type.<p>
<tt>enumFrom n</tt> returns a list corresponding to the complete enumeration
of <tt>n</tt>'s type starting at the value <tt>n</tt>.
Similarly, <tt>enumFromThen n n'</tt> is the enumeration starting at <tt>n</tt>, but
with second element <tt>n'</tt>, and with subsequent elements generated at a
spacing equal to the difference between <tt>n</tt> and <tt>n'</tt>.
<tt>enumFromTo</tt> and <tt>enumFromThenTo</tt> are as defined by the
default class methods
for <tt>Enum</tt> (see Figure <a href="basic.html#standard-classes">5</a>,
page ).
For example,
given the datatype:
<tt><br>
<br>
data Color = Red | Orange | Yellow | Green deriving (Enum)<br>
<br>
</tt>we would have:
<tt><br>
<br>
[Orange ..] == [Orange, Yellow, Green]<br>
fromEnum Yellow == 2<br>
<br>
<p>
</tt><a name="sectD.3"></a>
<h3>D.3<tt> </tt>Derived instances of <tt>Bounded</tt>.</h3>
The <tt>Bounded</tt> class introduces the class
methods
<tt>minBound</tt> and
<tt>maxBound</tt>,
which define the minimal and maximal elements of the type.
For an enumeration, the first and last constructors listed in the
<tt>data</tt> declaration are the bounds. For a type with a single
constructor, the constructor is applied to the bounds for the
constituent types. For example, the following datatype:
<tt><br>
<br>
data Pair a b = Pair a b deriving Bounded<br>
<br>
</tt>would generate the following <tt>Bounded</tt> instance:
<tt><br>
<br>
instance (Bounded a,Bounded b) => Bounded (Pair a b) where<br>
minBound = Pair minBound minBound<br>
maxBound = Pair maxBound maxBound<br>
<br>
<p>
</tt><a name="sectD.4"></a>
<h3>D.4<tt> </tt>Derived instances of <tt>Read</tt> and <tt>Show</tt>.</h3>
The class methods automatically introduced by derived instances
of <tt>Read</tt> and <tt>Show</tt> are <tt>showsPrec</tt>,
<tt>readsPrec</tt>,
<tt>showList</tt>, and <tt>readList</tt>.
They are used to coerce values into strings and parse strings into
values.<p>
The function <tt>showsPrec d x r</tt> accepts a precedence level <tt>d
</tt>(a number from <tt>0</tt> to <tt>10</tt>), a value <tt>x</tt>, and a string <tt>r</tt>.
It returns a string representing <tt>x</tt> concatenated to <tt>r</tt>.
<tt>showsPrec</tt> satisfies the law:
<p>
<tt>showsPrec d x r ++ s == showsPrec d x (r ++ s)
<p>
</tt>The representation will be enclosed in parentheses if the precedence
of the top-level constructor operator in <tt>x</tt> is less than <tt>d</tt>. Thus,
if <tt>d</tt> is <tt>0</tt> then the result is never surrounded in parentheses; if
<tt>d</tt> is <tt>10</tt> it is always surrounded in parentheses, unless it is an
atomic expression. The extra parameter <tt>r</tt> is essential if tree-like
structures are to be printed in linear time rather than time quadratic
in the size of the tree.<p>
The function <tt>readsPrec d s</tt> accepts a precedence level <tt>d</tt> (a number
from <tt>0</tt> to <tt>10</tt>) and a string <tt>s</tt>, and attempts to parse a value
from the front of the string, returning a list of (parsed value, remaining string) pairs.
If there is no successful parse, the returned list is empty.
It should be the case that
<tt><br>
<br>
fst (head (readsPrec d (showsPrec d x r))) == x<br>
<br>
</tt>That is, <tt>readsPrec</tt> should be able to parse the string produced
by <tt>showsPrec</tt>, and should deliver the value that <tt>showsPrec</tt> started
with.<p>
<tt>showList</tt> and <tt>readList</tt> allow lists of objects to be represented
using non-standard denotations. This is especially useful for strings
(lists of <tt>Char</tt>).<p>
<tt>readsPrec</tt> will parse any valid representation of the standard types
apart from lists, for
which only the bracketed form <tt>[</tt>...<tt>]</tt> is accepted. See
Appendix <a href="standard-prelude.html#stdprelude">A</a> for full details.<p>
A precise definition of the derived <tt>Read</tt> and <tt>Show</tt> instances for
general types is beyond the scope of this report. However, the
derived <tt>Read</tt> and <tt>Show</tt> instances have the following properties:
<UL><LI>The result of <tt>show</tt> is a syntactically correct Haskell
expression containing only constants
given the fixity declarations in force at the point where
the type is declared.
<LI>The result of <tt>show</tt> is readable by <tt>read</tt> if all component
types are readable. (This is true for all instances defined in
the Prelude but may not be true for user-defined instances.)
<LI>The instance generated by <tt>Read</tt> allows arbitrary whitespace
between tokens on the input string. Extra parentheses are also
allowed.
<LI>The result of <tt>show</tt> contains only the constructor names defined
in the data type, parentheses, and spaces. When labelled
constructor fields are used, braces, commas, field names, and
equal signs are also used.
Spaces and parentheses are only added where
needed. No line breaks are added.
<LI>If a constructor is defined using labelled field syntax then the derived
<tt>show</tt> for that constructor will use this same
syntax; the fields will be in the order declared in the
<tt>data</tt> declaration. The derived <tt>Read</tt> instance will use
this same syntax: all fields must be present and the declared order
must be maintained.
<LI>If a constructor is defined in the infix style, the derived <tt>Show
</tt> instance will also use infix style. The derived <tt>Read</tt> instance will
require that the constructor be infix.
</UL><p>
The derived <tt>Read</tt> and <tt>Show</tt> instances may be unsuitable for some
uses. Some problems include:
<UL><LI>Circular structures cannot be printed or read by these
instances.
<LI>The printer loses shared substructure; the printed
representation of an object may be much larger than necessary.
<LI>The parsing techniques used by the reader are very inefficient;
reading a large structure may be quite slow.
<LI>There is no user control over the printing of types defined in
the Prelude. For example, there is no way to change the
formatting of floating point numbers.
</UL><p>
<a name="sectD.5"></a>
<h3>D.5<tt> </tt>An Example</h3><p>
As a complete example, consider a tree datatype:<tt><br>
<br>
data Tree a = Leaf a | Tree a :^: Tree a<br>
deriving (Eq, Ord, Read, Show)<br>
<br>
</tt>Automatic derivation of
instance
declarations for <tt>Bounded</tt> and <tt>Enum</tt> are not possible, as <tt>Tree</tt> is not
an enumeration or single-constructor datatype. The complete
instance declarations for <tt>Tree</tt> are shown in Figure <a href="derived.html#tree-inst">8</a>,
Note the implicit use of default class method
definitions---for
example, only <tt><=</tt> is defined for <tt>Ord</tt>, with the other
class methods (<tt><</tt>, <tt>></tt>, <tt>>=</tt>, <tt>max</tt>, and <tt>min</tt>) being defined by the defaults given in
the class declaration shown in Figure <a href="basic.html#standard-classes">5</a>
(page ).<p>
<table border=2 cellpadding=3>
<tr><td>
<div align=center><table border=2 cellpadding=3>
<tr><td>
<tt><br>
infix 4 :^:<br>
data Tree a = Leaf a | Tree a :^: Tree a<br>
<br>
instance (Eq a) => Eq (Tree a) where<br>
Leaf m == Leaf n = m==n<br>
u:^:v == x:^:y = u==x && v==y<br>
_ == _ = False<br>
<br>
instance (Ord a) => Ord (Tree a) where<br>
Leaf m <= Leaf n = m<=n<br>
Leaf m <= x:^:y = True<br>
u:^:v <= Leaf n = False<br>
u:^:v <= x:^:y = u<x || u==x && v<=y<br>
<br>
instance (Show a) => Show (Tree a) where<br>
<br>
showsPrec d (Leaf m) = showParen (d >= 10) showStr<br>
where<br>
showStr = showString "Leaf " . showsPrec 10 m<br>
<br>
showsPrec d (u :^: v) = showParen (d > 4) showStr<br>
where<br>
showStr = showsPrec 5 u . <br>
showString " :^: " .<br>
showsPrec 5 v<br>
<br>
instance (Read a) => Read (Tree a) where<br>
<br>
readsPrec d r = readParen (d > 4)<br>
(\r -> [(u:^:v,w) |<br>
(u,s) <- readsPrec 5 r,<br>
(":^:",t) <- lex s,<br>
(v,w) <- readsPrec 5 t]) r<br>
<br>
++ readParen (d > 9)<br>
(\r -> [(Leaf m,t) |<br>
("Leaf",s) <- lex r,<br>
(m,t) <- readsPrec 10 s]) r<br>
</tt></td></tr></table>
</div>
<div align=center> <h4>Figure 8</h4> </div>
<div align=center><h3>Example of Derived Instances</h3></div><a name="tree-inst"></a>
</td></tr></table>
<p>
<hr><i>The Haskell 98 Report</i><br><a href="index.html">top</a> | <a href="literate.html">back</a> | <a href="pragmas.html">next</a> | <a href="index98.html">contents</a> | <a href="prelude-index.html">function index</a> <br><font size=2>1 February, 1999</font>
|
