5b750dbed0e1657b90921354f5ea1040a90d2263
[haskell-report.git] / report / derived.verb
1 %
2 % $Header: /home/cvs/root/haskell-report/report/derived.verb,v 1.1 2001/03/28 14:13:42 simonpj Exp $
3 %
4 % The paragraph describing the formats of standard representations might
5 % be deleted, since the info is already in the Prelude.  
6 % Note that there is a difference in the way readsPrec and showsPrec are defined.
7 % showsPrec is exact Haskell text, readsPrec uses an auxiliary function which
8 % isn't quite Haskell.  
9
10 %**<title>The Haskell 98 Report: Derived Instances</title>
11 %*section D
12 %**~header
13
14 \section{Specification of Derived Instances}
15 \label{derived-appendix}
16 A {\em derived instance} is an instance declaration that is generated
17 automatically in conjunction with a @data@ or @newtype@ declaration.
18 The body of a derived instance declaration is derived syntactically from
19 the definition of the associated type.  Derived instances are
20 possible only for classes known to the compiler: those defined in
21 either the Prelude or a standard library.  In this appendix, we
22 describe the derivation of classes defined by the Prelude.
23
24 If "T" is an algebraic datatype declared by:\index{algebraic datatype}
25 \[\ba{lcl}
26 "@data @cx@ =>@ T u_1 ... u_k"&@=@&"K_1 t_{11} ... t_{1k_1} @|@ \cdots @|@ K_n t_{n1} ... t_{nk_n}"\\
27 & & "@deriving (@C_1@,@ ...@,@ C_m@)@"
28 \ea\]
29 (where "m\geq0" and the parentheses may be omitted if "m=1") then
30 a derived instance declaration is possible for a class "C" 
31 if these conditions hold:
32 \begin{enumerate}
33 \item
34 "C" is one of @Eq@, @Ord@, @Enum@, @Bounded@, @Show@, or @Read@.
35
36 \item
37 There is a context "cx'" such that "cx' \Rightarrow C t_{ij}"
38 holds for each of the constituent types "t_{ij}".
39
40 \item
41 If "C" is @Bounded@, the type must be either an enumeration (all
42 constructors must by nullary) or have only one constructor.
43
44 \item
45 If "C" is @Enum@, the type must be an enumeration.
46
47 \item
48 There must be no explicit instance declaration elsewhere in the program that
49 makes "T u_1 ... u_k" an instance of "C".
50 % or of any of "C"'s superclasses.
51 \end{enumerate}
52 For the purposes of derived instances, a @newtype@ declaration is
53 treated as a @data@ declaration with a single constructor.
54
55 If the @deriving@ form is present,
56 an instance declaration is automatically generated for "T u_1 ... u_k"
57 over each class "C_i".
58 If the derived instance declaration is impossible for any of the "C_i"
59 then a static error results.
60 If no derived instances are required, the @deriving@ form may be
61 omitted or the form @deriving ()@ may be used.
62
63 % OLD:
64 %If the @deriving@ form is omitted then instance
65 %declarations are derived for the datatype in as many of the six
66 %classes mentioned above as is possible; that is, no static error can occur.
67 %Since datatypes may be recursive, the implied inclusion in
68 %these classes may also be recursive, and the largest
69 %possible set of derived instances is generated.  For example,
70 %\bprog
71 %@@%@@
72 %data  T1 a = C1 (T2 a) | Nil1
73 %data  T2 a = C2 (T1 a) | Nil2
74 %@@%@@
75 %\eprog
76 %Because the @deriving@ form is omitted, we would expect derived
77 %instances for @Eq@ (for example).  But @T1@ is in @Eq@ only if @T2@
78 %is, and @T2@ is in @Eq@ only if @T1@ is.  The largest solution has
79 %both types in @Eq@, and thus both derived instances are generated.
80
81 Each derived instance declaration will have the form:
82 \[
83 "@instance (@cx@,@ C'_1 u'_1@,@ ...@,@ C'_j u'_j @) =>@ C_i (T u_1 ... u_k) @where@ @{@ d @}@"
84 \]
85 where "d" is derived automatically depending on "C_i" and the data
86 type declaration for "T" (as will be described in the remainder of
87 this section), and "u'_1" through "u'_j" form a subset of "u_1"
88 through "u_k".
89 %% Yale nuked this:
90 %% The class assertions "C' u'" are constraints on "T"'s
91 %% type variables that are inferred from the instance declarations of the
92 %% constituent types "t_{ij}".  For example, consider:
93 %% \bprog
94 %% @@
95 %% data  T1 a = C1 (T2 a) deriving Eq
96 %% data  T2 a = C2 a      deriving ()
97 %% @@
98 %% \eprog
99 %% And consider these three different instances for @T2@ in @Eq@:\nopagebreak
100 %% \bprog
101 %% @@
102 %% instance            Eq (T2 a) where (C2 x) == (C2 y)  =  True
103 %% 
104 %% instance (Eq  a) => Eq (T2 a) where (C2 x) == (C2 y)  =  x == y
105 %% 
106 %% instance (Ord a) => Eq (T2 a) where (C2 x) == (C2 y)  =  x > y
107 %% @@
108 %% \eprog
109 %% The corresponding derived instances for @T1@ in @Eq@ are:
110 %% \bprog
111 %% @@
112 %% instance            Eq (T1 a) where (C1 x) == (C1 y)  =  x == y
113 %% 
114 %% instance (Eq  a) => Eq (T1 a) where (C1 x) == (C1 y)  =  x == y
115 %% 
116 %% instance (Ord a) => Eq (T1 a) where (C1 x) == (C1 y)  =  x == y
117 %% @@
118 %% \eprog
119 When inferring the context for the derived instances, type synonyms
120 must be expanded out first.\index{type synonym}
121 Free names in the declarations $d$ are all
122 defined in the Prelude; the qualifier `@Prelude.@' is
123 implicit here.  The remaining details of the derived
124 instances for each of the derivable Prelude classes are now given.
125
126 \subsection{Derived instances of @Eq@ and @Ord@.}
127 \indexdi{Eq}
128 \indexdi{Ord}
129 The class methods automatically introduced by derived instances
130 of @Eq@ and @Ord@ are @(==)@,
131 \index{==@@{\tt ==}}
132 @(/=)@,
133 \index{/=@@{\tt /=}}
134 @compare@\indextt{compare},
135 @(<)@,
136 \index{<@@{\tt <}}
137 @(<=)@,
138 \index{<=@@{\tt <=}}
139 @(>)@,
140 \index{>@@{\tt >}}
141 @(>=)@,
142 \index{>=@@{\tt >=}}
143 @max@\indextt{max}, and 
144 @min@\indextt{min}.  The latter seven operators are defined so
145 as to compare their arguments lexicographically with respect to
146 the constructor set given, with earlier constructors in the datatype
147 declaration counting as smaller than later ones.  For example, for the
148 @Bool@ datatype, we have that @(True > False) == True@.
149
150 Derived comparisons always traverse constructors from left to right.
151 These examples illustrate this property:
152 \bprog
153 @
154 (1,undefined) == (2,undefined) @"\Rightarrow"@    False
155 (undefined,1) == (undefined,2) @"\Rightarrow"@    @"\bot"@
156 @
157 \eprog
158
159 \subsection{Derived instances of @Enum@}
160 \indexdi{Enum}
161 Derived instance declarations for the class @Enum@ are only
162 possible for enumerations.
163 @Enum@ introduces the class methods
164 @succ@\indextt{succ},
165 @pred@\indextt{pred},
166 @toEnum@\indextt{toEnum},
167 @fromEnum@\indextt{fromEnum},
168 @enumFrom@\indextt{enumFrom},
169 @enumFromThen@\indextt{enumFromThen},
170 @enumFromTo@\indextt{enumFromTo}, and
171 @enumFromThenTo@\indextt{enumFromThenTo}.
172 The latter four are used to define arithmetic sequences as described
173 in Section~\ref{arithmetic-sequences}. 
174
175 The nullary constructors are assumed to be
176 numbered left-to-right with the indices 0 through $n-1\/$.
177 The @succ@ and @pred@ operators give the successor and predecessor
178 respectively of a value, under this numbering scheme.  It is
179 an error to apply @succ@ to the maximum element, or @pred@ to the minimum
180 element.
181
182 The @toEnum@ and @fromEnum@ operators map enumerated values to and
183 from the @Int@ type.
184
185 @enumFrom n@ returns a list corresponding to the complete enumeration
186 of @n@'s type starting at the value @n@.
187 Similarly, @enumFromThen n n'@ is the enumeration starting at @n@, but
188 with second element @n'@, and with subsequent elements generated at a
189 spacing equal to the difference between @n@ and @n'@.
190 @enumFromTo@ and @enumFromThenTo@ are as defined by the
191 default class methods
192 \index{default class method}
193 for @Enum@ (see Figure~\ref{standard-classes},
194 page~\pageref{standard-classes}).
195 For example,
196 given the datatype:
197 \bprog
198 @
199 data  Color = Red | Orange | Yellow | Green  deriving (Enum)
200 @
201 \eprog
202 we would have:
203 \bprog
204 @
205 [Orange ..]         ==  [Orange, Yellow, Green]
206 fromEnum Yellow     ==  2
207 @
208 \eprog
209
210 \subsection{Derived instances of @Bounded@.}
211 \indexdi{Bounded}
212 The @Bounded@ class introduces the class
213 methods 
214 @minBound@\indextt{maxBound} and
215 @maxBound@\indextt{minBound},
216 which define the minimal and maximal elements of the type.
217 For an enumeration, the first and last constructors listed in the
218 @data@ declaration are the bounds.  For a type with a single
219 constructor, the constructor is applied to the bounds for the
220 constituent types.  For example, the following datatype:
221 \bprog
222 @
223 data  Pair a b = Pair a b deriving Bounded
224 @
225 \eprog
226 would generate the following @Bounded@ instance:
227 \bprog
228 @
229 instance (Bounded a,Bounded b) => Bounded (Pair a b) where
230   minBound = Pair minBound minBound
231   maxBound = Pair maxBound maxBound
232 @
233 \eprog
234
235 \subsection{Derived instances of @Read@ and @Show@.}
236 \indexdi{Read}
237 \indexdi{Show}
238 The class methods automatically introduced by derived instances
239 of @Read@ and @Show@ are @showsPrec@\indextt{showsPrec},
240 @readsPrec@\indextt{readsPrec},
241 @showList@\indextt{showList}, and @readList@\indextt{readList}.
242 They are used to coerce values into strings and parse strings into
243 values.
244
245 The function @showsPrec d x r@ accepts a precedence level @d@
246 (a number from @0@ to @10@), a value @x@, and a string @r@.
247 It returns a string representing @x@ concatenated to @r@.
248 @showsPrec@ satisfies the law:
249 \[
250 "@showsPrec d x r ++ s  ==  showsPrec d x (r ++ s)@"
251 \]
252 The representation will be enclosed in parentheses if the precedence
253 of the top-level constructor operator in @x@ is less than @d@.  Thus,
254 if @d@ is @0@ then the result is never surrounded in parentheses; if
255 @d@ is @10@ it is always surrounded in parentheses, unless it is an
256 atomic expression.  The extra parameter @r@ is essential if tree-like
257 structures are to be printed in linear time rather than time quadratic
258 in the size of the tree.
259
260 The function @readsPrec d s@ accepts a precedence level @d@ (a number
261 from @0@ to @10@) and a string @s@, and attempts to parse a value 
262 from the front of the string, returning a list of (parsed value, remaining string) pairs.
263 If there is no successful parse, the returned list is empty.
264 It should be the case that
265 \bprog
266 @
267   fst (head (readsPrec d (showsPrec d x r))) == x
268 @
269 \eprog
270 That is, @readsPrec@ should be able to parse the string produced
271 by @showsPrec@, and should deliver the value that @showsPrec@ started
272 with.
273
274 @showList@ and @readList@ allow lists of objects to be represented
275 using non-standard denotations.  This is especially useful for strings
276 (lists of @Char@).
277
278 %Because a string is a list of characters, @showsPrec@ of a string
279 %such as @"abc"@ will result in the string 
280 %@"[@\fwq@a@\fwq @,@ \fwq@b@\fwq @,@ \fwq@c@\fwq @]"@.  Because
281 %@"\"abc\""@ would be a better representation,
282 %the operators @showList@
283 %and @readList@ are provided in the class @Text@ for coercing {\em
284 %lists} of values to and from strings.  In particular, @showsPrec@ of a
285 %string will yield the verbose form above, and @showList@ will yield
286 %the compact version.  For most other datatypes, @showList@ and
287 %@readList@ will yield the same result as @showsPrec@ and @readsPrec@.
288
289
290 %The instances of @Text@ for the standard types @Int@, @Integer@, @Float@,
291 %@Double@, @Char@, lists, tuples, and rational and complex numbers are
292 %defined in the  
293 %standard prelude (see Appendix~\ref{stdprelude}).
294 %For characters and strings, the control characters that have special
295 %representations (@\n@ etc.) are shown as such by @showsPrec@;
296 %otherwise, ASCII mnemonics are used.
297 %Non-ASCII characters are shown by decimal escapes.
298 %Floating point numbers are represented by decimal numbers
299 %of sufficient precision to guarantee @read . show@ is an identity
300 %function.  If $b$ is the floating-point radix and there are
301 %$w$ base-$b$ digits in the floating-point significand,
302 %the number of decimal digits required is
303 %$d = \lceil w \log_{10} b \rceil + 1$ \cite{matula70}.
304 %Numbers are shown in non-exponential format if this requires
305 %only $d$ digits; otherwise, they are shown in exponential format,
306 %with one digit before the decimal point.  @readsPrec@ allows
307 %an exponent to be unsigned or signed with @+@ or @-@; @showsPrec@
308 %shows a positive exponent without a sign.
309
310 @readsPrec@ will parse any valid representation of the standard types 
311 apart from lists, for
312 which only the bracketed form @[@\ldots@]@ is accepted. See
313 Appendix~\ref{stdprelude} for full details.
314
315 A precise definition of the derived @Read@ and @Show@ instances for
316 general types is beyond the scope of this report.  However, the
317 derived @Read@ and @Show@ instances have the following properties:
318 \begin{itemize}
319 \item The result of @show@ is a syntactically correct \Haskell{}
320       expression containing only constants
321       given the fixity declarations in force at the point where
322       the type is declared.
323 \item The result of @show@ is readable by @read@ if all component
324       types are readable.  (This is true for all instances defined in
325       the Prelude but may not be true for user-defined instances.)
326 \item The instance generated by @Read@ allows arbitrary whitespace
327       between tokens on the input string.  Extra parentheses are also 
328       allowed.
329 \item The result of @show@ contains only the constructor names defined
330       in the data type, parentheses, and spaces.  When labelled
331       constructor fields are used, braces, commas, field names, and
332       equal signs are also used.
333       Spaces and parentheses are only added where
334       needed.  No line breaks are added.
335 \item If a constructor is defined using labelled field syntax then the derived
336       @show@ for that constructor will use this same
337       syntax; the fields will be in the order declared in the
338       @data@ declaration.  The derived @Read@ instance will use
339       this same syntax: all fields must be present and the declared order
340       must be maintained.
341 \item If a constructor is defined in the infix style, the derived @Show@
342       instance will also use infix style.  The derived @Read@ instance will
343       require that the constructor be infix.
344 \end{itemize}
345
346 The derived @Read@ and @Show@ instances may be unsuitable for some
347 uses.  Some problems include:
348 \begin{itemize}
349 \item Circular structures cannot be printed or read by these
350 instances.
351 \item The printer loses shared substructure; the printed
352 representation of an object may be much larger than necessary.
353 \item The parsing techniques used by the reader are very inefficient;
354 reading a large structure may be quite slow.
355 \item There is no user control over the printing of types defined in
356 the Prelude.  For example, there is no way to change the
357 formatting of floating point numbers.
358 \end{itemize}
359
360
361 %Figure~\ref{derived-text} gives the general form of a derived instance
362 %of @Text@ for a user-defined datatype:
363 %\[
364 %"@data@ cx @=>@ T u_1 ... u_k @=@ ... "
365 %\]
366 %@showsPrec@ and @readsPrec@ are as
367 %in Appendices~\ref{showsPrec-spec} and \ref{readsPrec-spec}.  The omitted
368 %definitions of @readList@ and @showList@ in
369 %Figure~\ref{standard-classes} (page~\pageref{standard-classes})
370 %are:
371 %\bprog
372 %@@
373 %readList:: ReadS [a]
374 %readList r = [pr | ("[",s) <- lex r,
375 %                 pr      <- readl s    ]
376 %           where readl s = [([],t) | ("]",t) <- lex s] ++
377 %                          [(x:xs,v) |  (x,t) <- reads s,
378 %                                       (",",u) <- lex t,
379 %                                       (xs,v) <- readl u       ]
380 %
381 %showList:: [a] -> ShowS
382 %showList xs = showChar '[' . showl xs
383 %            where
384 %            showl [] = showChar ']'
385 %            showl (x:xs) = shows x . showChar ',' . showl xs
386 %@@
387 %\eprog
388 %\begin{figure}
389 %\outline{
390 %@@
391 %instance (C, Text u1, ..., Text uk) => Text (T u1 ... uk) where
392 %       showsPrec = ...
393 %       readsPrec = ...
394 %@@
395 %}
396 %\caption{General form of a derived instance of @Text@}
397 %\label{derived-text}
398 %\end{figure}
399
400
401 \subsection{An Example}
402
403 As a complete example, consider a tree datatype:\nopagebreak
404 %\bprog
405 %@@
406 %data Tree a = Leaf a | Tree a :^: Tree a
407 %@@
408 %\eprog\nopagebreak
409 %Since there is no @deriving@ clause, this is shorthand for:\nopagebreak
410 \bprog
411 @
412 data Tree a = Leaf a | Tree a :^: Tree a
413      deriving (Eq, Ord, Read, Show)
414 @
415 \eprog
416 Automatic derivation of
417 instance
418 declarations for @Bounded@ and @Enum@ are not possible, as @Tree@ is not
419 an enumeration or single-constructor datatype.  The complete
420 instance declarations for @Tree@ are shown in Figure~\ref{tree-inst},
421 Note the implicit use of default class method
422 \index{default class method}
423 definitions---for
424 example, only @<=@ is defined for @Ord@, with the other
425 class methods (@<@, @>@, @>=@, @max@, and @min@) being defined by the defaults given in
426 the class declaration shown in Figure~\ref{standard-classes}
427 (page~\pageref{standard-classes}).
428
429 \begin{figure}[tb]
430 \outlinec{
431 @
432 infix 4 :^:
433 data Tree a =  Leaf a  |  Tree a :^: Tree a
434
435 instance (Eq a) => Eq (Tree a) where
436         Leaf m == Leaf n  =  m==n
437         u:^:v  == x:^:y   =  u==x && v==y
438              _ == _       =  False
439
440 instance (Ord a) => Ord (Tree a) where
441         Leaf m <= Leaf n  =  m<=n
442         Leaf m <= x:^:y   =  True
443         u:^:v  <= Leaf n  =  False
444         u:^:v  <= x:^:y   =  u<x || u==x && v<=y
445
446 instance (Show a) => Show (Tree a) where
447
448         showsPrec d (Leaf m) = showParen (d >= 10) showStr
449           where
450              showStr = showString "Leaf " . showsPrec 10 m
451
452         showsPrec d (u :^: v) = showParen (d > 4) showStr
453           where
454              showStr = showsPrec 5 u . 
455                        showString " :^: " .
456                        showsPrec 5 v
457
458 instance (Read a) => Read (Tree a) where
459
460         readsPrec d r =  readParen (d > 4)
461                          (\r -> [(u:^:v,w) |
462                                  (u,s) <- readsPrec 5 r,
463                                  (":^:",t) <- lex s,
464                                  (v,w) <- readsPrec 5 t]) r
465
466                       ++ readParen (d > 9)
467                          (\r -> [(Leaf m,t) |
468                                  ("Leaf",s) <- lex r,
469                                  (m,t) <- readsPrec 10 s]) r
470 @
471 }
472 %**<div align=center> <h4>Figure 8</h4> </div>
473 \ecaption{Example of Derived Instances}
474 \label{tree-inst}
475 \end{figure}
476
477 %**~footer