/usr/share/doc/haskell98-report/html/haskell98-report-html/derived.html is in haskell98-report 20080907-4.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 343 344 345 346 347 348 349 350 351 352 353 354 355 356 | <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="sect10"></a>
<h2>10<tt> </tt>Specification of Derived Instances</h2>
<p>
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 chapter, 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 be 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>cx'</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).<p>
The context <I>cx'</I> is the smallest context satisfying point (2) above.
For mutually recusive data types, the compiler may need to perform a
fixpoint calculation to compute it.<p>
The remaining details of the derived
instances for each of the derivable Prelude classes are now given.
Free variables and constructors used in these translations
always refer to entities defined by the <tt>Prelude</tt>.<p>
<a name="sect10.1"></a>
<h3>10.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>
</tt>All derived operations of class <tt>Eq</tt> and <tt>Ord</tt> are strict in both arguments.
For example, <tt>False <= </tt><I>_|_</I> is <I>_|_</I>, even though <tt>False</tt> is the first constructor
of the <tt>Bool</tt> type.<p>
<a name="sect10.2"></a>
<h3>10.2<tt> </tt>Derived instances of <tt>Enum</tt></h3>
Derived instance declarations for the class <tt>Enum</tt> are only
possible for enumerations (data types with only nullary constructors).<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; <tt>toEnum</tt> raises a runtime error if the <tt>Int</tt> argument
is not the index of one of the constructors.<p>
The definitions of the remaining methods are
<tt><br>
<br>
enumFrom x = enumFromTo x lastCon<br>
enumFromThen x y = enumFromThenTo x y bound<br>
where<br>
bound | fromEnum y >= fromEnum x = lastCon<br>
| otherwise = firstCon<br>
enumFromTo x y = map toEnum [fromEnum x .. fromEnum y]<br>
enumFromThenTo x y z = map toEnum [fromEnum x, fromEnum y .. fromEnum z]<br>
<br>
</tt>where <tt>firstCon</tt> and <tt>lastCon</tt> are respectively the first and last
constructors listed in the <tt>data</tt> declaration.
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="sect10.3"></a>
<h3>10.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>
<a name="derived-text"></a><p>
</tt><a name="sect10.4"></a>
<h3>10.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>11</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 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>11</tt> it is always surrounded in parentheses, unless it is an
atomic expression (recall that function application has precedence <tt>10</tt>).
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.
Parsing of an un-parenthesised infix operator application succeeds only
if the precedence of the operator is greater than or equal to <tt>d</tt>.<p>
It should be the case that
<div align=center><tt>(x,"")</tt> is an element of <tt>(readsPrec d (showsPrec d x ""))
</tt></div>
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 strings, for which only quoted strings are accepted, and other lists,
for which only the bracketed form <tt>[</tt>...<tt>]</tt> is accepted. See
Chapter <a href="standard-prelude.html#stdprelude">8</a> for full details.<p>
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. It 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. Parentheses
are only added where needed, <I>ignoring associativity</I>. No line breaks
are added. 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.)<p>
Derived instances of <tt>Read</tt> make the following assumptions,
which derived instances of <tt>Show</tt> obey:
<UL><LI>If the constructor is defined to be an infix operator, then
the derived <tt>Read</tt> instance will parse only infix applications of the
constructor (not the prefix form).<p>
<LI>Associativity is not used to reduce the occurrence of
parentheses, although precedence may be. For example, given
<tt><br>
<br>
infixr 4 :$<br>
data T = Int :$ T | NT<br>
<br>
</tt>then:
<UL><LI><tt>show (1 :$ 2 :$ NT)</tt> produces the string <tt>"1 :$ (2 :$ NT)"</tt>.
<LI><tt>read "1 :$ (2 :$ NT)"</tt> succeeds, with the obvious result.
<LI><tt>read "1 :$ 2 :$ NT"</tt> fails.
</UL><p>
<LI>
If the constructor is defined using record syntax, the derived <tt>Read</tt>
will parse only the record-syntax form, and furthermore, the fields must be
given in the same order as the original declaration.<p>
<LI>The derived <tt>Read</tt> instance allows arbitrary Haskell whitespace between
tokens of the input string. Extra parentheses are also allowed.
</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="sect10.5"></a>
<h3>10.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">10.1</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">6.1</a>
(page ).<p>
<table border=2 cellpadding=3>
<tr><td>
<div align=center><table border=2 cellpadding=3>
<tr><td>
<tt><br>
infixr 5 :^:<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 > app_prec) showStr<br>
where<br>
showStr = showString "Leaf " . showsPrec (app_prec+1) m<br>
<br>
showsPrec d (u :^: v) = showParen (d > up_prec) showStr<br>
where<br>
showStr = showsPrec (up_prec+1) u . <br>
showString " :^: " .<br>
showsPrec (up_prec+1) v<br>
-- Note: right-associativity of :^: ignored<br>
<br>
instance (Read a) => Read (Tree a) where<br>
<br>
readsPrec d r = readParen (d > up_prec)<br>
(\r -> [(u:^:v,w) |<br>
(u,s) <- readsPrec (up_prec+1) r,<br>
(":^:",t) <- lex s,<br>
(v,w) <- readsPrec (up_prec+1) t]) r<br>
<br>
++ readParen (d > app_prec)<br>
(\r -> [(Leaf m,t) |<br>
("Leaf",s) <- lex r,<br>
(m,t) <- readsPrec (app_prec+1) s]) r<br>
<br>
up_prec = 5 -- Precedence of :^:<br>
app_prec = 10 -- Application has precedence one more than<br>
-- the most tightly-binding operator<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>December 2002</font>
|