derived.verb 19.6 KB
 Simon Peyton Jones committed Mar 28, 2001 1 %  Simon Peyton Jones committed Apr 08, 2003 2 % $Header: /home/cvs/root/haskell-report/report/derived.verb,v 1.13 2003/04/08 08:18:19 simonpj Exp$  Simon Peyton Jones committed Mar 28, 2001 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. %**The Haskell 98 Report: Derived Instances %**~header \section{Specification of Derived Instances} \label{derived-appendix}  Simon Peyton Jones committed Dec 02, 2002 15 16 \index{derived instance}  Simon Peyton Jones committed Mar 28, 2001 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 committed Dec 10, 2002 22 either the Prelude or a standard library. In this chapter, we  Simon Peyton Jones committed Mar 28, 2001 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 committed May 28, 2001 43 constructors must be nullary) or have only one constructor.  Simon Peyton Jones committed Mar 28, 2001 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 committed Apr 28, 2010 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 committed Mar 28, 2001 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: $ Simon Peyton Jones committed Dec 02, 2002 88 "@instance (@cx@, @cx'@) =>@ C_i (T u_1 ... u_k) @where@ @{@ d @}@"  Simon Peyton Jones committed Mar 28, 2001 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  Simon Peyton Jones committed Dec 02, 2002 92 this section).  Simon Peyton Jones committed Mar 28, 2001 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  Simon Peyton Jones committed Dec 02, 2002 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 committed Jan 29, 2002 127 128  The remaining details of the derived  Simon Peyton Jones committed Mar 28, 2001 129 instances for each of the derivable Prelude classes are now given.  Simon Peyton Jones committed Jan 29, 2002 130 131 Free variables and constructors used in these translations always refer to entities defined by the @Prelude@.  Simon Peyton Jones committed Mar 28, 2001 132   Simon Marlow committed Jul 05, 2010 133 \subsection{Derived instances of \texorpdfstring{@Eq@}{Eq} and \texorpdfstring{@Ord@}{Ord}}  Simon Peyton Jones committed Mar 28, 2001 134 135 136 137 \indexdi{Eq} \indexdi{Ord} The class methods automatically introduced by derived instances of @Eq@ and @Ord@ are @(==)@,  Ross Paterson committed Dec 03, 2002 138 \indextt{==}  Simon Peyton Jones committed Mar 28, 2001 139 @(/=)@,  Ross Paterson committed Dec 03, 2002 140 \indextt{/=}  Simon Peyton Jones committed Mar 28, 2001 141 142 @compare@\indextt{compare}, @(<)@,  Ross Paterson committed Dec 03, 2002 143 \indextt{<}  Simon Peyton Jones committed Mar 28, 2001 144 @(<=)@,  Ross Paterson committed Dec 03, 2002 145 \indextt{<=}  Simon Peyton Jones committed Mar 28, 2001 146 @(>)@,  Ross Paterson committed Dec 03, 2002 147 \indextt{>}  Simon Peyton Jones committed Mar 28, 2001 148 @(>=)@,  Ross Paterson committed Dec 03, 2002 149 \indextt{>=}  Simon Peyton Jones committed Mar 28, 2001 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 @  Simon Peyton Jones committed Dec 02, 2002 161 162  (1,undefined) == (2,undefined) @"\Rightarrow"@ False (undefined,1) == (undefined,2) @"\Rightarrow"@ @"\bot"@  Simon Peyton Jones committed Mar 28, 2001 163 164 @ \eprog  Simon Peyton Jones committed Dec 02, 2002 165 All derived operations of class @Eq@ and @Ord@ are strict in both arguments.  Simon Peyton Jones committed Apr 08, 2003 166 For example, "@False <= @\bot" is "\bot", even though @False@ is the first constructor  Simon Peyton Jones committed Dec 02, 2002 167 of the @Bool@ type.  Simon Peyton Jones committed Mar 28, 2001 168   Simon Marlow committed Jul 05, 2010 169 \subsection{Derived instances of \texorpdfstring{@Enum@}{Enum}}  Simon Peyton Jones committed Mar 28, 2001 170 171 \indexdi{Enum} Derived instance declarations for the class @Enum@ are only  Simon Peyton Jones committed Nov 02, 2001 172 possible for enumerations (data types with only nullary constructors).  Simon Peyton Jones committed Mar 28, 2001 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 committed Nov 02, 2001 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  Simon Peyton Jones committed Dec 02, 2002 186 187 \par {\small  Simon Peyton Jones committed Nov 02, 2001 188 189 \bprog @  Simon Peyton Jones committed Dec 02, 2002 190  enumFrom x = enumFromTo x lastCon  Simon Peyton Jones committed Nov 02, 2001 191  enumFromThen x y = enumFromThenTo x y bound  Simon Peyton Jones committed Dec 02, 2002 192 193 194  where bound | fromEnum y >= fromEnum x = lastCon | otherwise = firstCon  Simon Peyton Jones committed Nov 02, 2001 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  Simon Peyton Jones committed Dec 02, 2002 199 }  Simon Peyton Jones committed Dec 02, 2002 200 201 where @firstCon@ and @lastCon@ are respectively the first and last constructors listed in the @data@ declaration.  Simon Peyton Jones committed Mar 28, 2001 202 203 204 205 For example, given the datatype: \bprog @  Simon Peyton Jones committed Dec 02, 2002 206  data Color = Red | Orange | Yellow | Green deriving (Enum)  Simon Peyton Jones committed Mar 28, 2001 207 208 209 210 211 @ \eprog we would have: \bprog @  Simon Peyton Jones committed Dec 02, 2002 212 213  [Orange ..] == [Orange, Yellow, Green] fromEnum Yellow == 2  Simon Peyton Jones committed Mar 28, 2001 214 215 216 @ \eprog  Simon Marlow committed Jul 05, 2010 217 \subsection{Derived instances of \texorpdfstring{@Bounded@}{Bounded}}  Simon Peyton Jones committed Mar 28, 2001 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 @  Simon Peyton Jones committed Dec 02, 2002 230  data Pair a b = Pair a b deriving Bounded  Simon Peyton Jones committed Mar 28, 2001 231 232 233 234 235 @ \eprog would generate the following @Bounded@ instance: \bprog @  Simon Peyton Jones committed Dec 02, 2002 236 237 238  instance (Bounded a,Bounded b) => Bounded (Pair a b) where minBound = Pair minBound minBound maxBound = Pair maxBound maxBound  Simon Peyton Jones committed Mar 28, 2001 239 240 241 @ \eprog  Simon Marlow committed Jul 05, 2010 242 \subsection{Derived instances of \texorpdfstring{@Read@}{Read} and \texorpdfstring{@Show@}{Show}}  Simon Peyton Jones committed May 29, 2001 243 \label{derived-text}  Simon Peyton Jones committed Mar 28, 2001 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@  Simon Peyton Jones committed Dec 02, 2002 254 (a number from @0@ to @11@), a value @x@, and a string @r@.  Simon Peyton Jones committed Mar 28, 2001 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  Simon Peyton Jones committed Dec 02, 2002 261 of the top-level constructor in @x@ is less than @d@. Thus,  Simon Peyton Jones committed Mar 28, 2001 262 if @d@ is @0@ then the result is never surrounded in parentheses; if  Simon Peyton Jones committed Dec 02, 2002 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 committed Mar 28, 2001 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.  Simon Peyton Jones committed Dec 02, 2002 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 committed Mar 28, 2001 276 It should be the case that  Simon Peyton Jones committed Dec 02, 2002 277 278 279 \begin{center} @(x,"")@ is an element of @(readsPrec d (showsPrec d x ""))@ \end{center}  Simon Peyton Jones committed Mar 28, 2001 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  Simon Peyton Jones committed Dec 02, 2002 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 committed Dec 10, 2002 323 Chapter~\ref{stdprelude} for full details.  Simon Peyton Jones committed Mar 28, 2001 324   Simon Peyton Jones committed Dec 02, 2002 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 committed Mar 28, 2001 338 \begin{itemize}  Simon Peyton Jones committed Dec 02, 2002 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 committed Mar 28, 2001 356 357 \end{itemize}  Simon Peyton Jones committed Dec 02, 2002 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 committed Mar 28, 2001 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,  Simon Peyton Jones committed May 30, 2001 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 committed Mar 28, 2001 432 433 434 % %showList:: [a] -> ShowS %showList xs = showChar '[' . showl xs  Simon Peyton Jones committed May 30, 2001 435 436 437 % where % showl [] = showChar ']' % showl (x:xs) = shows x . showChar ',' . showl xs  Simon Peyton Jones committed Mar 28, 2001 438 439 440 441 442 443 %@@ %\eprog %\begin{figure} %\outline{ %@@ %instance (C, Text u1, ..., Text uk) => Text (T u1 ... uk) where  Simon Peyton Jones committed May 30, 2001 444 445 % showsPrec = ... % readsPrec = ...  Simon Peyton Jones committed Mar 28, 2001 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 @  Simon Peyton Jones committed Dec 02, 2002 464 465  data Tree a = Leaf a | Tree a :^: Tree a deriving (Eq, Ord, Read, Show)  Simon Peyton Jones committed Mar 28, 2001 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  Simon Marlow committed Apr 29, 2010 478 the class declaration shown in Figure~\ref{standard-classes}.  Simon Peyton Jones committed Mar 28, 2001 479 480  \begin{figure}[tb]  Simon Marlow committed Apr 29, 2010 481 482 \begin{outlineenv} \small  Simon Peyton Jones committed Mar 28, 2001 483 @  Simon Peyton Jones committed Dec 02, 2002 484 infixr 5 :^:  Simon Peyton Jones committed Mar 28, 2001 485 486 487 data Tree a = Leaf a | Tree a :^: Tree a instance (Eq a) => Eq (Tree a) where  Simon Peyton Jones committed May 30, 2001 488 489  Leaf m == Leaf n = m==n u:^:v == x:^:y = u==x && v==y  Simon Peyton Jones committed Mar 28, 2001 490 491 492  _ == _ = False instance (Ord a) => Ord (Tree a) where  Simon Peyton Jones committed May 30, 2001 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 Show (Tree a) where  Simon Peyton Jones committed Dec 02, 2002 500  showsPrec d (Leaf m) = showParen (d > app_prec) showStr  Simon Peyton Jones committed May 30, 2001 501  where  Simon Peyton Jones committed Dec 02, 2002 502  showStr = showString "Leaf " . showsPrec (app_prec+1) m  Simon Peyton Jones committed Mar 28, 2001 503   Simon Peyton Jones committed Dec 02, 2002 504  showsPrec d (u :^: v) = showParen (d > up_prec) showStr  Simon Peyton Jones committed May 30, 2001 505  where  Simon Peyton Jones committed Dec 02, 2002 506 507 508 509  showStr = showsPrec (up_prec+1) u . showString " :^: " . showsPrec (up_prec+1) v -- Note: right-associativity of :^: ignored  Simon Peyton Jones committed Mar 28, 2001 510 511 512  instance (Read a) => Read (Tree a) where  Simon Peyton Jones committed Dec 02, 2002 513  readsPrec d r = readParen (d > up_prec)  Simon Peyton Jones committed May 30, 2001 514  (\r -> [(u:^:v,w) |  Simon Peyton Jones committed Dec 02, 2002 515  (u,s) <- readsPrec (up_prec+1) r,  Simon Peyton Jones committed May 30, 2001 516  (":^:",t) <- lex s,  Simon Peyton Jones committed Dec 02, 2002 517  (v,w) <- readsPrec (up_prec+1) t]) r  Simon Peyton Jones committed Mar 28, 2001 518   Simon Peyton Jones committed Dec 02, 2002 519  ++ readParen (d > app_prec)  Simon Peyton Jones committed May 30, 2001 520 521  (\r -> [(Leaf m,t) | ("Leaf",s) <- lex r,  Simon Peyton Jones committed Dec 02, 2002 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 committed Mar 28, 2001 527 @  Simon Marlow committed Apr 29, 2010 528 \end{outlineenv}  Simon Peyton Jones committed Mar 28, 2001 529 530 531 532 533 534 %**
\ecaption{Example of Derived Instances} \label{tree-inst} \end{figure} %**~footer