718 lines
39 KiB
HTML
718 lines
39 KiB
HTML
<?xml version="1.0" encoding="iso-8859-1" ?>
|
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
|
|
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
|
<!--http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd-->
|
|
<html xmlns="http://www.w3.org/1999/xhtml"
|
|
>
|
|
<head><title>11 Specification of Derived Instances</title>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
|
|
<meta name="generator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)" />
|
|
<meta name="originator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)" />
|
|
<!-- 2,html,xhtml -->
|
|
<meta name="src" content="haskell.tex" />
|
|
<meta name="date" content="2010-07-20 13:11:00" />
|
|
<link rel="stylesheet" type="text/css" href="haskell.css" />
|
|
</head><body
|
|
>
|
|
<!--l. 13--><div class="crosslinks"><p class="noindent">[<a
|
|
href="haskellch12.html" >next</a>] [<a
|
|
href="haskellch10.html" >prev</a>] [<a
|
|
href="haskellch10.html#tailhaskellch10.html" >prev-tail</a>] [<a
|
|
href="#tailhaskellch11.html">tail</a>] [<a
|
|
href="haskellpa1.html#haskellch11.html" >up</a>] </p></div>
|
|
<h2 class="chapterHead"><span class="titlemark">Chapter 11</span><br /><a
|
|
id="x18-18200011"></a>Specification of Derived Instances</h2> <a
|
|
id="dx18-182001"></a>
|
|
<p class="noindent"> A <span
|
|
class="ptmri7t-">derived instance </span>is an instance declaration that is generated automatically in conjunction with a <span
|
|
class="pcrr7t-">data</span> or
|
|
<span
|
|
class="pcrr7t-">newtype</span> 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 class="noindent"> If <span
|
|
class="cmmi-10">T</span> is an algebraic datatype declared by:<a
|
|
id="dx18-182002"></a>
|
|
<div class="array"> <table id="TBL-106" class="array"
|
|
cellpadding="0" cellspacing="0"
|
|
><colgroup id="TBL-106-1g"><col
|
|
id="TBL-106-1" /><col
|
|
id="TBL-106-2" /><col
|
|
id="TBL-106-3" /></colgroup><tr
|
|
style="vertical-align:baseline;"><td style="white-space:nowrap; text-align:left;"
|
|
><div class="td11"> <span
|
|
class="pcrr7t-">data</span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="cmmi-10">cx</span><span
|
|
class="pcrr7t-"> =></span><span
|
|
class="cmmi-10"> T</span><span
|
|
class="cmmi-10"> u</span><sub><span
|
|
class="cmr-7">1</span></sub><span
|
|
class="cmmi-10"> </span><span
|
|
class="cmmi-10">…</span><span
|
|
class="cmmi-10"> u</span><sub><span
|
|
class="cmmi-7">k</span></sub> </div></td><td style="white-space:nowrap; text-align:center;"
|
|
><div class="td11"> <span
|
|
class="pcrr7t-">=</span> </div></td><td style="white-space:nowrap; text-align:left;"
|
|
><div class="td11"> <span
|
|
class="cmmi-10">K</span><sub><span
|
|
class="cmr-7">1</span></sub><span
|
|
class="cmmi-10"> t</span><sub><span
|
|
class="cmr-7">11</span></sub><span
|
|
class="cmmi-10"> </span><span
|
|
class="cmmi-10">…</span><span
|
|
class="cmmi-10"> t</span><sub><span
|
|
class="cmr-7">1</span><span
|
|
class="cmmi-7">k</span><sub><span
|
|
class="cmr-5">1</span></sub></sub><span
|
|
class="cmmi-10"> </span><span
|
|
class="pcrr7t-">|</span><span
|
|
class="cmmi-10"> </span><img
|
|
src="haskell4x.png" alt="⋅⋅⋅" class="cdots" /><span
|
|
class="cmmi-10"> </span><span
|
|
class="pcrr7t-">|</span><span
|
|
class="cmmi-10"> K</span><sub><span
|
|
class="cmmi-7">n</span></sub><span
|
|
class="cmmi-10"> t</span><sub><span
|
|
class="cmmi-7">n</span><span
|
|
class="cmr-7">1</span></sub><span
|
|
class="cmmi-10"> </span><span
|
|
class="cmmi-10">…</span><span
|
|
class="cmmi-10"> t</span><sub><span
|
|
class="cmmi-7">nk</span><sub><span
|
|
class="cmmi-5">n</span></sub></sub> </div></td>
|
|
</tr><tr
|
|
style="vertical-align:baseline;"><td style="white-space:nowrap; text-align:left;"
|
|
><div class="td11"> </div></td><td style="white-space:nowrap; text-align:center;"
|
|
><div class="td11"> </div></td><td style="white-space:nowrap; text-align:left;"
|
|
><div class="td11"> <span
|
|
class="pcrr7t-">deriving</span><span
|
|
class="pcrr7t-"> (</span><span
|
|
class="cmmi-10">C</span><sub><span
|
|
class="cmr-7">1</span></sub><span
|
|
class="pcrr7t-">,</span><span
|
|
class="cmmi-10"> </span><span
|
|
class="cmmi-10">…</span><span
|
|
class="pcrr7t-">,</span><span
|
|
class="cmmi-10"> C</span><sub><span
|
|
class="cmmi-7">m</span></sub><span
|
|
class="pcrr7t-">)</span> </div></td>
|
|
</tr></table> </div>
|
|
(where <span
|
|
class="cmmi-10">m </span><span
|
|
class="cmsy-10">≥ </span><span
|
|
class="cmr-10">0</span> and the parentheses may be omitted if <span
|
|
class="cmmi-10">m </span><span
|
|
class="cmr-10">= 1</span>) then a derived instance declaration is possible for a
|
|
class <span
|
|
class="cmmi-10">C</span> if these conditions hold:
|
|
<ol class="enumerate1" >
|
|
<li
|
|
class="enumerate" id="x18-182004x1"><span
|
|
class="cmmi-10">C</span> is one of <span
|
|
class="pcrr7t-">Eq</span>, <span
|
|
class="pcrr7t-">Ord</span>, <span
|
|
class="pcrr7t-">Enum</span>, <span
|
|
class="pcrr7t-">Bounded</span>, <span
|
|
class="pcrr7t-">Show</span>, or <span
|
|
class="pcrr7t-">Read</span>.
|
|
</li>
|
|
<li
|
|
class="enumerate" id="x18-182006x2">There is a context <span
|
|
class="cmmi-10">cx</span><span
|
|
class="cmsy-10">′</span> such that <span
|
|
class="cmmi-10">cx</span><span
|
|
class="cmsy-10">′</span><span
|
|
class="cmmi-10">  </span><span
|
|
class="cmsy-10">⇒</span> <span
|
|
class="cmmi-10"> C</span><span
|
|
class="cmmi-10"> t</span><sub><span
|
|
class="cmmi-7">ij</span></sub> holds for each of the constituent types <span
|
|
class="cmmi-10">t</span><sub><span
|
|
class="cmmi-7">ij</span></sub>.
|
|
</li>
|
|
<li
|
|
class="enumerate" id="x18-182008x3">If <span
|
|
class="cmmi-10">C</span> is <span
|
|
class="pcrr7t-">Bounded</span>, the type must be either an enumeration (all constructors must be nullary) or have
|
|
only one constructor.
|
|
</li>
|
|
<li
|
|
class="enumerate" id="x18-182010x4">If <span
|
|
class="cmmi-10">C</span> is <span
|
|
class="pcrr7t-">Enum</span>, the type must be an enumeration.
|
|
</li>
|
|
<li
|
|
class="enumerate" id="x18-182012x5">There must be no explicit instance declaration elsewhere in the program that makes <span
|
|
class="cmmi-10">T</span><span
|
|
class="cmmi-10"> u</span><sub><span
|
|
class="cmr-7">1</span></sub><span
|
|
class="cmmi-10"> </span><span
|
|
class="cmmi-10">…</span><span
|
|
class="cmmi-10"> u</span><sub><span
|
|
class="cmmi-7">k</span></sub> an
|
|
instance of <span
|
|
class="cmmi-10">C</span>.
|
|
</li>
|
|
<li
|
|
class="enumerate" id="x18-182014x6">If the data declaration has no constructors (i.e. when <span
|
|
class="cmmi-10">n </span><span
|
|
class="cmr-10">= 0</span>), then no classes are derivable (i.e. <span
|
|
class="cmmi-10">m </span><span
|
|
class="cmr-10">= 0</span>)</li></ol>
|
|
<p class="noindent"> For the purposes of derived instances, a <span
|
|
class="pcrr7t-">newtype</span> declaration is treated as a <span
|
|
class="pcrr7t-">data</span> declaration with a single
|
|
constructor.
|
|
|
|
|
|
|
|
<p class="noindent"> If the <span
|
|
class="pcrr7t-">deriving</span> form is present, an instance declaration is automatically generated for <span
|
|
class="cmmi-10">T</span><span
|
|
class="cmmi-10"> u</span><sub><span
|
|
class="cmr-7">1</span></sub><span
|
|
class="cmmi-10"> </span><span
|
|
class="cmmi-10">…</span><span
|
|
class="cmmi-10"> u</span><sub><span
|
|
class="cmmi-7">k</span></sub> over each
|
|
class <span
|
|
class="cmmi-10">C</span><sub><span
|
|
class="cmmi-7">i</span></sub>. If the derived instance declaration is impossible for any of the <span
|
|
class="cmmi-10">C</span><sub><span
|
|
class="cmmi-7">i</span></sub> then a static error results. If no
|
|
derived instances are required, the <span
|
|
class="pcrr7t-">deriving</span> form may be omitted or the form <span
|
|
class="pcrr7t-">deriving</span><span
|
|
class="pcrr7t-"> ()</span> may be
|
|
used.
|
|
<p class="noindent"> Each derived instance declaration will have the form:
|
|
<span
|
|
class="pcrr7t-">instance</span><span
|
|
class="pcrr7t-"> (</span><span
|
|
class="cmmi-10">cx</span><span
|
|
class="pcrr7t-">,</span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="cmmi-10">cx</span><span
|
|
class="cmsy-10">′</span><span
|
|
class="pcrr7t-">)</span><span
|
|
class="pcrr7t-"> =></span><span
|
|
class="cmmi-10"> C</span><sub><span
|
|
class="cmmi-7">i</span></sub><span
|
|
class="cmmi-10"> </span><span
|
|
class="cmr-10">(</span><span
|
|
class="cmmi-10">T</span><span
|
|
class="cmmi-10"> u</span><sub><span
|
|
class="cmr-7">1</span></sub><span
|
|
class="cmmi-10"> </span><span
|
|
class="cmmi-10">…</span><span
|
|
class="cmmi-10"> u</span><sub><span
|
|
class="cmmi-7">k</span></sub><span
|
|
class="cmr-10">)</span><span
|
|
class="cmmi-10"> </span><span
|
|
class="pcrr7t-">where</span><span
|
|
class="cmmi-10"> </span><span
|
|
class="pcrr7t-">{</span><span
|
|
class="cmmi-10"> d</span><span
|
|
class="cmmi-10"> </span><span
|
|
class="pcrr7t-">}</span>
|
|
where <span
|
|
class="cmmi-10">d</span> is derived automatically depending on <span
|
|
class="cmmi-10">C</span><sub><span
|
|
class="cmmi-7">i</span></sub> and the data type declaration for <span
|
|
class="cmmi-10">T</span> (as will be described in the
|
|
remainder of this section).
|
|
<p class="noindent"> The context <span
|
|
class="cmmi-10">cx</span><span
|
|
class="cmsy-10">′</span> 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 class="noindent"> 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 <span
|
|
class="pcrr7t-">Prelude</span>.
|
|
<h3 class="sectionHead"><span class="titlemark">11.1 </span> <a
|
|
id="x18-18300011.1"></a>Derived instances of <span
|
|
class="pcrr7t-">Eq</span> and <span
|
|
class="pcrr7t-">Ord</span></h3>
|
|
<a
|
|
id="dx18-183001"></a>
|
|
<a
|
|
id="dx18-183002"></a>
|
|
<p class="noindent"> The class methods automatically introduced by derived instances of <span
|
|
class="pcrr7t-">Eq</span> and <span
|
|
class="pcrr7t-">Ord</span> are <span
|
|
class="pcrr7t-">(==)</span>, <a
|
|
id="dx18-183003"></a><span
|
|
class="pcrr7t-">(/=)</span>, <a
|
|
id="dx18-183004"></a><span
|
|
class="pcrr7t-">compare</span><a
|
|
id="dx18-183005"></a>,
|
|
<span
|
|
class="pcrr7t-">(<)</span>, <a
|
|
id="dx18-183006"></a><span
|
|
class="pcrr7t-">(<=)</span>, <a
|
|
id="dx18-183007"></a><span
|
|
class="pcrr7t-">(>)</span>, <a
|
|
id="dx18-183008"></a><span
|
|
class="pcrr7t-">(>=)</span>, <a
|
|
id="dx18-183009"></a><span
|
|
class="pcrr7t-">max</span><a
|
|
id="dx18-183010"></a>, and <span
|
|
class="pcrr7t-">min</span><a
|
|
id="dx18-183011"></a>. 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 <span
|
|
class="pcrr7t-">Bool</span> datatype, we have that
|
|
<span
|
|
class="pcrr7t-">(True</span><span
|
|
class="pcrr7t-"> ></span><span
|
|
class="pcrr7t-"> False)</span><span
|
|
class="pcrr7t-"> ==</span><span
|
|
class="pcrr7t-"> True</span>.
|
|
<p class="noindent"> Derived comparisons always traverse constructors from left to right. These examples illustrate this
|
|
property:
|
|
<div class="quote">
|
|
<p class="noindent"> <span
|
|
class="pcrr7t-">(1,undefined)</span><span
|
|
class="pcrr7t-"> ==</span><span
|
|
class="pcrr7t-"> (2,undefined)</span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="cmsy-10">⇒</span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="pcrr7t-"> False</span><br
|
|
class="newline" /><span
|
|
class="pcrr7t-">(undefined,1)</span><span
|
|
class="pcrr7t-"> ==</span><span
|
|
class="pcrr7t-"> (undefined,2)</span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="cmsy-10">⇒</span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="cmsy-10">⊥</span></div>
|
|
<p class="noindent"> All derived operations of class <span
|
|
class="pcrr7t-">Eq</span> and <span
|
|
class="pcrr7t-">Ord</span> are strict in both arguments. For example, <span
|
|
class="pcrr7t-">False</span><span
|
|
class="pcrr7t-"> <=</span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="cmsy-10">⊥</span> is <span
|
|
class="cmsy-10">⊥</span>, even
|
|
though <span
|
|
class="pcrr7t-">False</span> is the first constructor of the <span
|
|
class="pcrr7t-">Bool</span> type.
|
|
|
|
|
|
|
|
<p class="noindent">
|
|
<h3 class="sectionHead"><span class="titlemark">11.2 </span> <a
|
|
id="x18-18400011.2"></a>Derived instances of <span
|
|
class="pcrr7t-">Enum</span></h3>
|
|
<a
|
|
id="dx18-184001"></a>
|
|
<p class="noindent"> Derived instance declarations for the class <span
|
|
class="pcrr7t-">Enum</span> are only possible for enumerations (data types with only nullary
|
|
constructors).
|
|
<p class="noindent"> The nullary constructors are assumed to be numbered left-to-right with the indices 0 through <span
|
|
class="cmmi-10">n </span><span
|
|
class="cmsy-10">− </span><span
|
|
class="cmr-10">1</span>.
|
|
The <span
|
|
class="pcrr7t-">succ</span> and <span
|
|
class="pcrr7t-">pred</span> operators give the successor and predecessor respectively of a value, under this
|
|
numbering scheme. It is an error to apply <span
|
|
class="pcrr7t-">succ</span> to the maximum element, or <span
|
|
class="pcrr7t-">pred</span> to the minimum
|
|
element.
|
|
<p class="noindent"> The <span
|
|
class="pcrr7t-">toEnum</span> and <span
|
|
class="pcrr7t-">fromEnum</span> operators map enumerated values to and from the <span
|
|
class="pcrr7t-">Int</span> type; <span
|
|
class="pcrr7t-">toEnum</span> raises a
|
|
runtime error if the <span
|
|
class="pcrr7t-">Int</span> argument is not the index of one of the constructors.
|
|
<p class="noindent"> The definitions of the remaining methods are
|
|
<p class="noindent">
|
|
<div class="quote">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-351">
|
|
  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]
|
|
</div>
|
|
<p class="noindent"></div>
|
|
<p class="noindent"> where <span
|
|
class="pcrr7t-">firstCon</span> and <span
|
|
class="pcrr7t-">lastCon</span> are respectively the first and last constructors listed in the <span
|
|
class="pcrr7t-">data</span> declaration. For
|
|
example, given the datatype:
|
|
<div class="quote">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-352">
|
|
  data  Color = Red | Orange | Yellow | Green  deriving (Enum)
|
|
</div>
|
|
<p class="noindent"></div>
|
|
<p class="noindent"> we would have:
|
|
<div class="quote">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-353">
|
|
  [Orange ..]         ==  [Orange, Yellow, Green]
|
|
 <br />  fromEnum Yellow     ==  2
|
|
</div>
|
|
<p class="noindent"></div>
|
|
<p class="noindent">
|
|
<h3 class="sectionHead"><span class="titlemark">11.3 </span> <a
|
|
id="x18-18500011.3"></a>Derived instances of <span
|
|
class="pcrr7t-">Bounded</span></h3>
|
|
<a
|
|
id="dx18-185001"></a>
|
|
<p class="noindent"> The <span
|
|
class="pcrr7t-">Bounded</span> class introduces the class methods <span
|
|
class="pcrr7t-">minBound</span><a
|
|
id="dx18-185002"></a> and <span
|
|
class="pcrr7t-">maxBound</span><a
|
|
id="dx18-185003"></a>, which define the minimal and
|
|
maximal elements of the type. For an enumeration, the first and last constructors listed in the <span
|
|
class="pcrr7t-">data</span> 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:
|
|
<div class="quote">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-354">
|
|
  data  Pair a b = Pair a b deriving Bounded
|
|
</div>
|
|
<p class="noindent"></div>
|
|
<p class="noindent"> would generate the following <span
|
|
class="pcrr7t-">Bounded</span> instance:
|
|
<div class="quote">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-355">
|
|
  instance (Bounded a,Bounded b) => Bounded (Pair a b) where
|
|
 <br />    minBound = Pair minBound minBound
|
|
 <br />    maxBound = Pair maxBound maxBound
|
|
</div>
|
|
<p class="noindent"></div>
|
|
<p class="noindent">
|
|
<h3 class="sectionHead"><span class="titlemark">11.4 </span> <a
|
|
id="x18-18600011.4"></a>Derived instances of <span
|
|
class="pcrr7t-">Read</span> and <span
|
|
class="pcrr7t-">Show</span></h3>
|
|
<a
|
|
id="dx18-186001"></a>
|
|
<a
|
|
id="dx18-186002"></a>
|
|
<p class="noindent"> The class methods automatically introduced by derived instances of <span
|
|
class="pcrr7t-">Read</span> and <span
|
|
class="pcrr7t-">Show</span> are <span
|
|
class="pcrr7t-">showsPrec</span><a
|
|
id="dx18-186003"></a>,
|
|
<span
|
|
class="pcrr7t-">readsPrec</span><a
|
|
id="dx18-186004"></a>, <span
|
|
class="pcrr7t-">showList</span><a
|
|
id="dx18-186005"></a>, and <span
|
|
class="pcrr7t-">readList</span><a
|
|
id="dx18-186006"></a>. They are used to coerce values into strings and parse strings into
|
|
values.
|
|
<p class="noindent"> The function <span
|
|
class="pcrr7t-">showsPrec</span><span
|
|
class="pcrr7t-"> d</span><span
|
|
class="pcrr7t-"> x</span><span
|
|
class="pcrr7t-"> r</span> accepts a precedence level <span
|
|
class="pcrr7t-">d</span> (a number from <span
|
|
class="pcrr7t-">0</span> to <span
|
|
class="pcrr7t-">11</span>), a value <span
|
|
class="pcrr7t-">x</span>, and a string <span
|
|
class="pcrr7t-">r</span>.
|
|
It returns a string representing <span
|
|
class="pcrr7t-">x</span> concatenated to <span
|
|
class="pcrr7t-">r</span>. <span
|
|
class="pcrr7t-">showsPrec</span> satisfies the law:
|
|
<span
|
|
class="pcrr7t-">showsPrec</span><span
|
|
class="pcrr7t-"> d</span><span
|
|
class="pcrr7t-"> x</span><span
|
|
class="pcrr7t-"> r</span><span
|
|
class="pcrr7t-"> ++</span><span
|
|
class="pcrr7t-"> s</span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="pcrr7t-"> ==</span><span
|
|
class="pcrr7t-"> </span><span
|
|
class="pcrr7t-"> showsPrec</span><span
|
|
class="pcrr7t-"> d</span><span
|
|
class="pcrr7t-"> x</span><span
|
|
class="pcrr7t-"> (r</span><span
|
|
class="pcrr7t-"> ++</span><span
|
|
class="pcrr7t-"> s)</span>
|
|
The representation will be enclosed in parentheses if the precedence of the top-level constructor in <span
|
|
class="pcrr7t-">x</span> is less than <span
|
|
class="pcrr7t-">d</span>.
|
|
Thus, if <span
|
|
class="pcrr7t-">d</span> is <span
|
|
class="pcrr7t-">0</span> then the result is never surrounded in parentheses; if <span
|
|
class="pcrr7t-">d</span> is <span
|
|
class="pcrr7t-">11</span> it is always surrounded in parentheses,
|
|
unless it is an atomic expression (recall that function application has precedence <span
|
|
class="pcrr7t-">10</span>). The extra parameter <span
|
|
class="pcrr7t-">r</span> is
|
|
essential if tree-like structures are to be printed in linear time rather than time quadratic in the size of the
|
|
tree.
|
|
<p class="noindent"> The function <span
|
|
class="pcrr7t-">readsPrec</span><span
|
|
class="pcrr7t-"> d</span><span
|
|
class="pcrr7t-"> s</span> accepts a precedence level <span
|
|
class="pcrr7t-">d</span> (a number from <span
|
|
class="pcrr7t-">0</span> to <span
|
|
class="pcrr7t-">10</span>) and a string <span
|
|
class="pcrr7t-">s</span>,
|
|
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
|
|
<span
|
|
class="pcrr7t-">d</span>.
|
|
<p class="noindent"> It should be the case that
|
|
|
|
|
|
|
|
<div class="center"
|
|
>
|
|
<p class="noindent">
|
|
<p class="noindent"> <span
|
|
class="pcrr7t-">(x,"")</span> is an element of <span
|
|
class="pcrr7t-">(readsPrec</span><span
|
|
class="pcrr7t-"> d</span><span
|
|
class="pcrr7t-"> (showsPrec</span><span
|
|
class="pcrr7t-"> d</span><span
|
|
class="pcrr7t-"> x</span><span
|
|
class="pcrr7t-"> ""))</span></div>
|
|
<p class="noindent"> That is, <span
|
|
class="pcrr7t-">readsPrec</span> should be able to parse the string produced by <span
|
|
class="pcrr7t-">showsPrec</span>, and should deliver the value that
|
|
<span
|
|
class="pcrr7t-">showsPrec</span> started with.
|
|
<p class="noindent"> <span
|
|
class="pcrr7t-">showList</span> and <span
|
|
class="pcrr7t-">readList</span> allow lists of objects to be represented using non-standard denotations. This is
|
|
especially useful for strings (lists of <span
|
|
class="pcrr7t-">Char</span>).
|
|
<p class="noindent"> <span
|
|
class="pcrr7t-">readsPrec</span> 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 <span
|
|
class="pcrr7t-">[</span>…<span
|
|
class="pcrr7t-">]</span> is accepted. See Chapter <a
|
|
href="haskellch9.html#x16-1710009">9<!--tex4ht:ref: stdprelude --></a> for full
|
|
details.
|
|
<p class="noindent"> The result of <span
|
|
class="pcrr7t-">show</span> 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, <span
|
|
class="ptmri7t-">ignoring</span>
|
|
<span
|
|
class="ptmri7t-">associativity</span>. No line breaks are added. The result of <span
|
|
class="pcrr7t-">show</span> is readable by <span
|
|
class="pcrr7t-">read</span> 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 class="noindent"> Derived instances of <span
|
|
class="pcrr7t-">Read</span> make the following assumptions, which derived instances of <span
|
|
class="pcrr7t-">Show</span> obey:
|
|
<ul class="itemize1">
|
|
<li class="itemize">If the constructor is defined to be an infix operator, then the derived <span
|
|
class="pcrr7t-">Read</span> instance will parse only infix
|
|
applications of the constructor (not the prefix form).
|
|
</li>
|
|
<li class="itemize">Associativity is not used to reduce the occurrence of parentheses, although precedence may be. For example,
|
|
given
|
|
<div class="quote">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-356">
|
|
  infixr 4 :$
|
|
 <br />  data T = Int :$ T  |  NT
|
|
</div>
|
|
<p class="noindent"></div>
|
|
<p class="noindent"> then:
|
|
<ul class="itemize2">
|
|
<li class="itemize"><span
|
|
class="pcrr7t-">show</span><span
|
|
class="pcrr7t-"> (1</span><span
|
|
class="pcrr7t-"> :$</span><span
|
|
class="pcrr7t-"> 2</span><span
|
|
class="pcrr7t-"> :$</span><span
|
|
class="pcrr7t-"> NT)</span> produces the string <span
|
|
class="pcrr7t-">"1</span><span
|
|
class="pcrr7t-"> :$</span><span
|
|
class="pcrr7t-"> (2</span><span
|
|
class="pcrr7t-"> :$</span><span
|
|
class="pcrr7t-"> NT)"</span>.
|
|
</li>
|
|
<li class="itemize"><span
|
|
class="pcrr7t-">read</span><span
|
|
class="pcrr7t-"> "1</span><span
|
|
class="pcrr7t-"> :$</span><span
|
|
class="pcrr7t-"> (2</span><span
|
|
class="pcrr7t-"> :$</span><span
|
|
class="pcrr7t-"> NT)"</span> succeeds, with the obvious result.
|
|
</li>
|
|
<li class="itemize"><span
|
|
class="pcrr7t-">read</span><span
|
|
class="pcrr7t-"> "1</span><span
|
|
class="pcrr7t-"> :$</span><span
|
|
class="pcrr7t-"> 2</span><span
|
|
class="pcrr7t-"> :$</span><span
|
|
class="pcrr7t-"> NT"</span> fails.</li></ul>
|
|
</li>
|
|
<li class="itemize">If the constructor is defined using record syntax, the derived <span
|
|
class="pcrr7t-">Read</span> will parse only the record-syntax form, and
|
|
furthermore, the fields must be given in the same order as the original declaration.
|
|
</li>
|
|
<li class="itemize">The derived <span
|
|
class="pcrr7t-">Read</span> instance allows arbitrary Haskell whitespace between tokens of the input string. Extra
|
|
parentheses are also allowed.</li></ul>
|
|
<p class="noindent"> The derived <span
|
|
class="pcrr7t-">Read</span> and <span
|
|
class="pcrr7t-">Show</span> instances may be unsuitable for some uses. Some problems include:
|
|
<ul class="itemize1">
|
|
<li class="itemize">Circular structures cannot be printed or read by these instances.
|
|
</li>
|
|
<li class="itemize">The printer loses shared substructure; the printed representation of an object may be much larger than
|
|
necessary.
|
|
</li>
|
|
<li class="itemize">The parsing techniques used by the reader are very inefficient; reading a large structure may be quite
|
|
slow.
|
|
</li>
|
|
<li class="itemize">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.</li></ul>
|
|
<p class="noindent">
|
|
<h3 class="sectionHead"><span class="titlemark">11.5 </span> <a
|
|
id="x18-18700011.5"></a>An Example</h3>
|
|
<p class="noindent"> As a complete example, consider a tree datatype:
|
|
<div class="quote">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-357">
|
|
  data Tree a = Leaf a | Tree a :^: Tree a
|
|
 <br />       deriving (Eq, Ord, Read, Show)
|
|
</div>
|
|
<p class="noindent"></div>
|
|
<p class="noindent"> Automatic derivation of instance declarations for <span
|
|
class="pcrr7t-">Bounded</span> and <span
|
|
class="pcrr7t-">Enum</span> are not possible, as <span
|
|
class="pcrr7t-">Tree</span> is not an
|
|
enumeration or single-constructor datatype. The complete instance declarations for <span
|
|
class="pcrr7t-">Tree</span> are shown in Figure <a
|
|
href="#x18-1870021">11.1<!--tex4ht:ref: tree-inst --></a>,
|
|
Note the implicit use of default class method <a
|
|
id="dx18-187001"></a>definitions—for example, only <span
|
|
class="pcrr7t-"><=</span> is defined for <span
|
|
class="pcrr7t-">Ord</span>, with the other
|
|
class methods (<span
|
|
class="pcrr7t-"><</span>, <span
|
|
class="pcrr7t-">></span>, <span
|
|
class="pcrr7t-">>=</span>, <span
|
|
class="pcrr7t-">max</span>, and <span
|
|
class="pcrr7t-">min</span>) being defined by the defaults given in the class declaration shown in
|
|
Figure <a
|
|
href="haskellch6.html#x13-1270011">6.1<!--tex4ht:ref: standard-classes --></a>.
|
|
<hr class="figure" /><div class="figure"
|
|
>
|
|
|
|
|
|
|
|
<a
|
|
id="x18-1870021"></a>
|
|
|
|
|
|
|
|
<div class="center"
|
|
>
|
|
<p class="noindent">
|
|
<div class="fbox"><div class="minipage"><div class="verbatim" id="verbatim-358">
|
|
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
|
|
</div>
|
|
<p class="noindent"> </div></div>
|
|
</div>
|
|
<br /><div class="caption"
|
|
><span class="id">Figure 11.1: </span><span
|
|
class="content">Example of Derived Instances</span></div><!--tex4ht:label?: x18-1870021 -->
|
|
|
|
|
|
|
|
</div><hr class="endfigure" />
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<!--l. 6--><div class="crosslinks"><p class="noindent">[<a
|
|
href="haskellch12.html" >next</a>] [<a
|
|
href="haskellch10.html" >prev</a>] [<a
|
|
href="haskellch10.html#tailhaskellch10.html" >prev-tail</a>] [<a
|
|
href="haskellch11.html" >front</a>] [<a
|
|
href="haskellpa1.html#haskellch11.html" >up</a>] </p></div>
|
|
<p class="noindent"> <a
|
|
id="tailhaskellch11.html"></a>
|
|
</body></html>
|