derived.verb 19.6 KB
Newer Older
Simon Peyton Jones's avatar
Simon Peyton Jones committed
1
%
2
% $Header: /home/cvs/root/haskell-report/report/derived.verb,v 1.13 2003/04/08 08:18:19 simonpj Exp $
Simon Peyton Jones's avatar
Simon Peyton Jones committed
3
4
5
6
7
8
9
10
11
12
13
14
%
% The paragraph describing the formats of standard representations might
% be deleted, since the info is already in the Prelude.  
% Note that there is a difference in the way readsPrec and showsPrec are defined.
% showsPrec is exact Haskell text, readsPrec uses an auxiliary function which
% isn't quite Haskell.  

%**<title>The Haskell 98 Report: Derived Instances</title>
%**~header

\section{Specification of Derived Instances}
\label{derived-appendix}
15
16
\index{derived instance}

Simon Peyton Jones's avatar
Simon Peyton Jones committed
17
18
19
20
21
A {\em derived instance} is an instance declaration that is generated
automatically in conjunction with a @data@ or @newtype@ 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
Simon Peyton Jones's avatar
Simon Peyton Jones committed
22
either the Prelude or a standard library.  In this chapter, we
Simon Peyton Jones's avatar
Simon Peyton Jones committed
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
describe the derivation of classes defined by the Prelude.

If "T" is an algebraic datatype declared by:\index{algebraic datatype}
\[\ba{lcl}
"@data @cx@ =>@ T u_1 ... u_k"&@=@&"K_1 t_{11} ... t_{1k_1} @|@ \cdots @|@ K_n t_{n1} ... t_{nk_n}"\\
& & "@deriving (@C_1@,@ ...@,@ C_m@)@"
\ea\]
(where "m\geq0" and the parentheses may be omitted if "m=1") then
a derived instance declaration is possible for a class "C" 
if these conditions hold:
\begin{enumerate}
\item
"C" is one of @Eq@, @Ord@, @Enum@, @Bounded@, @Show@, or @Read@.

\item
There is a context "cx'" such that "cx' \Rightarrow C t_{ij}"
holds for each of the constituent types "t_{ij}".

\item
If "C" is @Bounded@, the type must be either an enumeration (all
Simon Peyton Jones's avatar
Simon Peyton Jones committed
43
constructors must be nullary) or have only one constructor.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
44
45
46
47
48
49
50
51

\item
If "C" is @Enum@, the type must be an enumeration.

\item
There must be no explicit instance declaration elsewhere in the program that
makes "T u_1 ... u_k" an instance of "C".
% or of any of "C"'s superclasses.
Simon Marlow's avatar
Simon Marlow committed
52
53
54
55

\item
\hprime{If the data declaration has no constructors (i.e. when "n=0"),
then no classes are derivable (i.e. "m=0")}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
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
\end{enumerate}
For the purposes of derived instances, a @newtype@ declaration is
treated as a @data@ declaration with a single constructor.

If the @deriving@ form is present,
an instance declaration is automatically generated for "T u_1 ... u_k"
over each class "C_i".
If the derived instance declaration is impossible for any of the "C_i"
then a static error results.
If no derived instances are required, the @deriving@ form may be
omitted or the form @deriving ()@ may be used.

% OLD:
%If the @deriving@ form is omitted then instance
%declarations are derived for the datatype in as many of the six
%classes mentioned above as is possible; that is, no static error can occur.
%Since datatypes may be recursive, the implied inclusion in
%these classes may also be recursive, and the largest
%possible set of derived instances is generated.  For example,
%\bprog
%@@%@@
%data  T1 a = C1 (T2 a) | Nil1
%data  T2 a = C2 (T1 a) | Nil2
%@@%@@
%\eprog
%Because the @deriving@ form is omitted, we would expect derived
%instances for @Eq@ (for example).  But @T1@ is in @Eq@ only if @T2@
%is, and @T2@ is in @Eq@ only if @T1@ is.  The largest solution has
%both types in @Eq@, and thus both derived instances are generated.

Each derived instance declaration will have the form:
\[
88
"@instance (@cx@, @cx'@) =>@ C_i (T u_1 ... u_k) @where@ @{@ d @}@"
Simon Peyton Jones's avatar
Simon Peyton Jones committed
89
90
91
\]
where "d" is derived automatically depending on "C_i" and the data
type declaration for "T" (as will be described in the remainder of
92
this section).
Simon Peyton Jones's avatar
Simon Peyton Jones committed
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
%% Yale nuked this:
%% The class assertions "C' u'" are constraints on "T"'s
%% type variables that are inferred from the instance declarations of the
%% constituent types "t_{ij}".  For example, consider:
%% \bprog
%% @@
%% data  T1 a = C1 (T2 a) deriving Eq
%% data  T2 a = C2 a      deriving ()
%% @@
%% \eprog
%% And consider these three different instances for @T2@ in @Eq@:\nopagebreak
%% \bprog
%% @@
%% instance            Eq (T2 a) where (C2 x) == (C2 y)  =  True
%% 
%% instance (Eq  a) => Eq (T2 a) where (C2 x) == (C2 y)  =  x == y
%% 
%% instance (Ord a) => Eq (T2 a) where (C2 x) == (C2 y)  =  x > y
%% @@
%% \eprog
%% The corresponding derived instances for @T1@ in @Eq@ are:
%% \bprog
%% @@
%% instance            Eq (T1 a) where (C1 x) == (C1 y)  =  x == y
%% 
%% instance (Eq  a) => Eq (T1 a) where (C1 x) == (C1 y)  =  x == y
%% 
%% instance (Ord a) => Eq (T1 a) where (C1 x) == (C1 y)  =  x == y
%% @@
%% \eprog
123
124
125
126

The context "cx'" 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.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
127
128

The remaining details of the derived
Simon Peyton Jones's avatar
Simon Peyton Jones committed
129
instances for each of the derivable Prelude classes are now given.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
130
131
Free variables and constructors used in these translations
always refer to entities defined by the @Prelude@.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
132

Simon Marlow's avatar
Simon Marlow committed
133
\subsection{Derived instances of \texorpdfstring{@Eq@}{Eq} and \texorpdfstring{@Ord@}{Ord}}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
134
135
136
137
\indexdi{Eq}
\indexdi{Ord}
The class methods automatically introduced by derived instances
of @Eq@ and @Ord@ are @(==)@,
138
\indextt{==}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
139
@(/=)@,
140
\indextt{/=}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
141
142
@compare@\indextt{compare},
@(<)@,
143
\indextt{<}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
144
@(<=)@,
145
\indextt{<=}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
146
@(>)@,
147
\indextt{>}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
148
@(>=)@,
149
\indextt{>=}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
150
151
152
153
154
155
156
157
158
159
160
@max@\indextt{max}, and 
@min@\indextt{min}.  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
@Bool@ datatype, we have that @(True > False) == True@.

Derived comparisons always traverse constructors from left to right.
These examples illustrate this property:
\bprog
@
161
162
  (1,undefined) == (2,undefined) @"\Rightarrow"@    False
  (undefined,1) == (undefined,2) @"\Rightarrow"@    @"\bot"@
Simon Peyton Jones's avatar
Simon Peyton Jones committed
163
164
@
\eprog
165
All derived operations of class @Eq@ and @Ord@ are strict in both arguments.
166
For example, "@False <= @\bot" is "\bot", even though @False@ is the first constructor
167
of the @Bool@ type.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
168

Simon Marlow's avatar
Simon Marlow committed
169
\subsection{Derived instances of \texorpdfstring{@Enum@}{Enum}}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
170
171
\indexdi{Enum}
Derived instance declarations for the class @Enum@ are only
Simon Peyton Jones's avatar
Simon Peyton Jones committed
172
possible for enumerations (data types with only nullary constructors).
Simon Peyton Jones's avatar
Simon Peyton Jones committed
173
174
175
176
177
178
179
180
181

The nullary constructors are assumed to be
numbered left-to-right with the indices 0 through $n-1\/$.
The @succ@ and @pred@ operators give the successor and predecessor
respectively of a value, under this numbering scheme.  It is
an error to apply @succ@ to the maximum element, or @pred@ to the minimum
element.

The @toEnum@ and @fromEnum@ operators map enumerated values to and
Simon Peyton Jones's avatar
Simon Peyton Jones committed
182
183
184
185
from the @Int@ type; @toEnum@ raises a runtime error if the @Int@ argument
is not the index of one of the constructors.

The definitions of the remaining methods are 
186
187
\par
{\small
Simon Peyton Jones's avatar
Simon Peyton Jones committed
188
189
\bprog
@
190
  enumFrom x           = enumFromTo x lastCon
Simon Peyton Jones's avatar
Simon Peyton Jones committed
191
  enumFromThen x y     = enumFromThenTo x y bound
192
193
194
                       where
                         bound | fromEnum y >= fromEnum x = lastCon
                               | otherwise                = firstCon
Simon Peyton Jones's avatar
Simon Peyton Jones committed
195
196
197
198
  enumFromTo x y       = map toEnum [fromEnum x .. fromEnum y]
  enumFromThenTo x y z = map toEnum [fromEnum x, fromEnum y .. fromEnum z]
@
\eprog
199
}
200
201
where @firstCon@ and @lastCon@ are respectively the first and last
constructors listed in the @data@ declaration.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
202
203
204
205
For example,
given the datatype:
\bprog
@
206
  data  Color = Red | Orange | Yellow | Green  deriving (Enum)
Simon Peyton Jones's avatar
Simon Peyton Jones committed
207
208
209
210
211
@
\eprog
we would have:
\bprog
@
212
213
  [Orange ..]         ==  [Orange, Yellow, Green]
  fromEnum Yellow     ==  2
Simon Peyton Jones's avatar
Simon Peyton Jones committed
214
215
216
@
\eprog

Simon Marlow's avatar
Simon Marlow committed
217
\subsection{Derived instances of \texorpdfstring{@Bounded@}{Bounded}}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
218
219
220
221
222
223
224
225
226
227
228
229
\indexdi{Bounded}
The @Bounded@ class introduces the class
methods 
@minBound@\indextt{maxBound} and
@maxBound@\indextt{minBound},
which define the minimal and maximal elements of the type.
For an enumeration, the first and last constructors listed in the
@data@ 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:
\bprog
@
230
  data  Pair a b = Pair a b deriving Bounded
Simon Peyton Jones's avatar
Simon Peyton Jones committed
231
232
233
234
235
@
\eprog
would generate the following @Bounded@ instance:
\bprog
@
236
237
238
  instance (Bounded a,Bounded b) => Bounded (Pair a b) where
    minBound = Pair minBound minBound
    maxBound = Pair maxBound maxBound
Simon Peyton Jones's avatar
Simon Peyton Jones committed
239
240
241
@
\eprog

Simon Marlow's avatar
Simon Marlow committed
242
\subsection{Derived instances of \texorpdfstring{@Read@}{Read} and \texorpdfstring{@Show@}{Show}}
243
\label{derived-text}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
244
245
246
247
248
249
250
251
252
253
\indexdi{Read}
\indexdi{Show}
The class methods automatically introduced by derived instances
of @Read@ and @Show@ are @showsPrec@\indextt{showsPrec},
@readsPrec@\indextt{readsPrec},
@showList@\indextt{showList}, and @readList@\indextt{readList}.
They are used to coerce values into strings and parse strings into
values.

The function @showsPrec d x r@ accepts a precedence level @d@
254
(a number from @0@ to @11@), a value @x@, and a string @r@.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
255
256
257
258
259
260
It returns a string representing @x@ concatenated to @r@.
@showsPrec@ satisfies the law:
\[
"@showsPrec d x r ++ s  ==  showsPrec d x (r ++ s)@"
\]
The representation will be enclosed in parentheses if the precedence
261
of the top-level constructor in @x@ is less than @d@.  Thus,
Simon Peyton Jones's avatar
Simon Peyton Jones committed
262
if @d@ is @0@ then the result is never surrounded in parentheses; if
263
264
265
@d@ is @11@ it is always surrounded in parentheses, unless it is an
atomic expression (recall that function application has precedence @10@).
The extra parameter @r@ is essential if tree-like
Simon Peyton Jones's avatar
Simon Peyton Jones committed
266
267
268
269
270
271
272
structures are to be printed in linear time rather than time quadratic
in the size of the tree.

The function @readsPrec d s@ accepts a precedence level @d@ (a number
from @0@ to @10@) and a string @s@, 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.
273
274
275
Parsing of an un-parenthesised infix operator application succeeds only 
if the precedence of the operator is greater than or equal to @d@.

Simon Peyton Jones's avatar
Simon Peyton Jones committed
276
It should be the case that
277
278
279
\begin{center}
@(x,"")@  is an element of  @(readsPrec d (showsPrec d x ""))@
\end{center}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
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
That is, @readsPrec@ should be able to parse the string produced
by @showsPrec@, and should deliver the value that @showsPrec@ started
with.

@showList@ and @readList@ allow lists of objects to be represented
using non-standard denotations.  This is especially useful for strings
(lists of @Char@).

%Because a string is a list of characters, @showsPrec@ of a string
%such as @"abc"@ will result in the string 
%@"[@\fwq@a@\fwq @,@ \fwq@b@\fwq @,@ \fwq@c@\fwq @]"@.  Because
%@"\"abc\""@ would be a better representation,
%the operators @showList@
%and @readList@ are provided in the class @Text@ for coercing {\em
%lists} of values to and from strings.  In particular, @showsPrec@ of a
%string will yield the verbose form above, and @showList@ will yield
%the compact version.  For most other datatypes, @showList@ and
%@readList@ will yield the same result as @showsPrec@ and @readsPrec@.


%The instances of @Text@ for the standard types @Int@, @Integer@, @Float@,
%@Double@, @Char@, lists, tuples, and rational and complex numbers are
%defined in the  
%standard prelude (see Appendix~\ref{stdprelude}).
%For characters and strings, the control characters that have special
%representations (@\n@ etc.) are shown as such by @showsPrec@;
%otherwise, ASCII mnemonics are used.
%Non-ASCII characters are shown by decimal escapes.
%Floating point numbers are represented by decimal numbers
%of sufficient precision to guarantee @read . show@ is an identity
%function.  If $b$ is the floating-point radix and there are
%$w$ base-$b$ digits in the floating-point significand,
%the number of decimal digits required is
%$d = \lceil w \log_{10} b \rceil + 1$ \cite{matula70}.
%Numbers are shown in non-exponential format if this requires
%only $d$ digits; otherwise, they are shown in exponential format,
%with one digit before the decimal point.  @readsPrec@ allows
%an exponent to be unsigned or signed with @+@ or @-@; @showsPrec@
%shows a positive exponent without a sign.

@readsPrec@ will parse any valid representation of the standard types 
321
322
apart from strings, for which only quoted strings are accepted, and other lists,
for which only the bracketed form @[@\ldots@]@ is accepted. See
Simon Peyton Jones's avatar
Simon Peyton Jones committed
323
Chapter~\ref{stdprelude} for full details.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
324

325
326
327
328
329
330
331
332
333
334
335
336
337
The result of @show@ 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, {\em ignoring associativity}.  No line breaks
are added. The result of @show@ is readable by @read@ 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.)

Derived instances of @Read@ make the following assumptions, 
which derived instances of @Show@ obey:
Simon Peyton Jones's avatar
Simon Peyton Jones committed
338
\begin{itemize}
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
\item If the constructor is defined to be an infix operator, then 
the derived @Read@ instance will parse only infix applications of the 
constructor (not the prefix form).

\item Associativity is not used to reduce the occurrence of 
parentheses, although precedence may be. For example, given
\bprog
@
  infixr 4 :$
  data T = Int :$ T  |  NT
@
\eprog
then:
\begin{itemize}
\item @show (1 :$ 2 :$ NT)@ produces the string @"1 :$ (2 :$ NT)"@.
\item @read "1 :$ (2 :$ NT)"@ succeeds, with the obvious result.
\item @read "1 :$ 2 :$ NT"@ fails.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
356
357
\end{itemize}

358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
\item 
If the constructor is defined using record syntax, the derived @Read@ 
will parse only the record-syntax form, and furthermore, the fields must be 
given in the same order as the original declaration.

\item The derived @Read@ instance allows arbitrary Haskell whitespace between 
tokens of the input string.  Extra parentheses are also allowed.
\end{itemize}


% However, the
% derived @Read@ and @Show@ instances have the following properties:
% \begin{itemize}
% \item The result of @show@ is a syntactically correct \Haskell{}
%       expression containing only constants
%       given the fixity declarations in force at the point where
%       the type is declared.
% \item The result of @show@ is readable by @read@ 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.)
% \item The instance generated by @Read@ allows arbitrary whitespace
%       between tokens on the input string.  Extra parentheses are also 
%       allowed.
% \item The result of @show@ 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.
% \item If a constructor is defined using labelled field syntax then the derived
%       @show@ for that constructor will use this same
%       syntax; the fields will be in the order declared in the
%       @data@ declaration.  The derived @Read@ instance will use
%       this same syntax: all fields must be present and the declared order
%       must be maintained.
% \item If a constructor is defined in the infix style, the derived @Show@
%       instance will also use infix style.  The derived @Read@ instance will
%       require that the constructor be infix.
% \end{itemize}

Simon Peyton Jones's avatar
Simon Peyton Jones committed
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
The derived @Read@ and @Show@ instances may be unsuitable for some
uses.  Some problems include:
\begin{itemize}
\item Circular structures cannot be printed or read by these
instances.
\item The printer loses shared substructure; the printed
representation of an object may be much larger than necessary.
\item The parsing techniques used by the reader are very inefficient;
reading a large structure may be quite slow.
\item 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.
\end{itemize}


%Figure~\ref{derived-text} gives the general form of a derived instance
%of @Text@ for a user-defined datatype:
%\[
%"@data@ cx @=>@ T u_1 ... u_k @=@ ... "
%\]
%@showsPrec@ and @readsPrec@ are as
%in Appendices~\ref{showsPrec-spec} and \ref{readsPrec-spec}.  The omitted
%definitions of @readList@ and @showList@ in
%Figure~\ref{standard-classes} (page~\pageref{standard-classes})
%are:
%\bprog
%@@
%readList:: ReadS [a]
%readList r = [pr | ("[",s) <- lex r,
427
428
429
430
431
%                 pr      <- readl s    ]
%           where readl s = [([],t) | ("]",t) <- lex s] ++
%                          [(x:xs,v) |  (x,t) <- reads s,
%                                       (",",u) <- lex t,
%                                       (xs,v) <- readl u       ]
Simon Peyton Jones's avatar
Simon Peyton Jones committed
432
433
434
%
%showList:: [a] -> ShowS
%showList xs = showChar '[' . showl xs
435
436
437
%            where
%            showl [] = showChar ']'
%            showl (x:xs) = shows x . showChar ',' . showl xs
Simon Peyton Jones's avatar
Simon Peyton Jones committed
438
439
440
441
442
443
%@@
%\eprog
%\begin{figure}
%\outline{
%@@
%instance (C, Text u1, ..., Text uk) => Text (T u1 ... uk) where
444
445
%       showsPrec = ...
%       readsPrec = ...
Simon Peyton Jones's avatar
Simon Peyton Jones committed
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
%@@
%}
%\caption{General form of a derived instance of @Text@}
%\label{derived-text}
%\end{figure}


\subsection{An Example}

As a complete example, consider a tree datatype:\nopagebreak
%\bprog
%@@
%data Tree a = Leaf a | Tree a :^: Tree a
%@@
%\eprog\nopagebreak
%Since there is no @deriving@ clause, this is shorthand for:\nopagebreak
\bprog
@
464
465
  data Tree a = Leaf a | Tree a :^: Tree a
       deriving (Eq, Ord, Read, Show)
Simon Peyton Jones's avatar
Simon Peyton Jones committed
466
467
468
469
470
471
472
473
474
475
476
477
@
\eprog
Automatic derivation of
instance
declarations for @Bounded@ and @Enum@ are not possible, as @Tree@ is not
an enumeration or single-constructor datatype.  The complete
instance declarations for @Tree@ are shown in Figure~\ref{tree-inst},
Note the implicit use of default class method
\index{default class method}
definitions---for
example, only @<=@ is defined for @Ord@, with the other
class methods (@<@, @>@, @>=@, @max@, and @min@) being defined by the defaults given in
478
the class declaration shown in Figure~\ref{standard-classes}.
Simon Peyton Jones's avatar
Simon Peyton Jones committed
479
480

\begin{figure}[tb]
481
482
\begin{outlineenv}
\small
Simon Peyton Jones's avatar
Simon Peyton Jones committed
483
@
484
infixr 5 :^:
Simon Peyton Jones's avatar
Simon Peyton Jones committed
485
486
487
data Tree a =  Leaf a  |  Tree a :^: Tree a

instance (Eq a) => Eq (Tree a) where
488
489
        Leaf m == Leaf n  =  m==n
        u:^:v  == x:^:y   =  u==x && v==y
Simon Peyton Jones's avatar
Simon Peyton Jones committed
490
491
492
             _ == _       =  False

instance (Ord a) => Ord (Tree a) where
493
494
495
496
        Leaf m <= Leaf n  =  m<=n
        Leaf m <= x:^:y   =  True
        u:^:v  <= Leaf n  =  False
        u:^:v  <= x:^:y   =  u<x || u==x && v<=y
Simon Peyton Jones's avatar
Simon Peyton Jones committed
497
498
499

instance (Show a) => Show (Tree a) where

500
        showsPrec d (Leaf m) = showParen (d > app_prec) showStr
501
          where
502
             showStr = showString "Leaf " . showsPrec (app_prec+1) m
Simon Peyton Jones's avatar
Simon Peyton Jones committed
503

504
        showsPrec d (u :^: v) = showParen (d > up_prec) showStr
505
          where
506
507
508
509
             showStr = showsPrec (up_prec+1) u . 
                       showString " :^: "      .
                       showsPrec (up_prec+1) v
                -- Note: right-associativity of :^: ignored
Simon Peyton Jones's avatar
Simon Peyton Jones committed
510
511
512

instance (Read a) => Read (Tree a) where

513
        readsPrec d r =  readParen (d > up_prec)
514
                         (\r -> [(u:^:v,w) |
515
                                 (u,s) <- readsPrec (up_prec+1) r,
516
                                 (":^:",t) <- lex s,
517
                                 (v,w) <- readsPrec (up_prec+1) t]) r
Simon Peyton Jones's avatar
Simon Peyton Jones committed
518

519
                      ++ readParen (d > app_prec)
520
521
                         (\r -> [(Leaf m,t) |
                                 ("Leaf",s) <- lex r,
522
523
524
525
526
                                 (m,t) <- readsPrec (app_prec+1) s]) r

up_prec  = 5    -- Precedence of :^:
app_prec = 10   -- Application has precedence one more than
		-- the most tightly-binding operator
Simon Peyton Jones's avatar
Simon Peyton Jones committed
527
@
528
\end{outlineenv}
Simon Peyton Jones's avatar
Simon Peyton Jones committed
529
530
531
532
533
534
%**<div align=center> <h4>Figure 8</h4> </div>
\ecaption{Example of Derived Instances}
\label{tree-inst}
\end{figure}

%**~footer