The Haskell 1.3 Report: Derived Instances
The Haskell 1.4 Report
top | back | next | contents | function index
D Specification of Derived Instances
A 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 syntacticly 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 appendix, we
describe the derivation of classes defined by the Prelude.
If T is an algebraic datatype declared by:
data c => T u1 ... uk | = | K1 t11 ... t1k1 | ...| Kn tn1 ... tnkn |
| | deriving (C1, ..., Cm)
|
(where m>=0 and the parentheses may be omitted if m=1) then
a derived instance declaration is possible for a class C
if these conditions hold:
-
C is one of Eq, Ord, Enum, Bounded, Show, or Read.
-
There is a context c' such that c' =>C tij
holds for each of the constituent types tij.
-
If C is Bounded, the type must be either an enumeration (all
constructors must by nullary) or have only one constructor.
-
If C is Enum, the type must be an enumeration.
-
There must be no explicit instance declaration elsewhere in the program that
makes T u1 ... uk an instance of C.
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 u1 ... uk
over each class Ci.
If the derived instance declaration is impossible for any of the Ci
then a static error results.
If no derived instances are required, the deriving form may be
omitted or the form deriving () may be used.
Each derived instance declaration will have the form:
instance (c, C'1 u'1, ..., C'j u'j ) => Ci (T u1 ... uk) where { d }
where d is derived automatically depending on Ci and the data
type declaration for T (as will be described in the remainder of
this section), and u'1 through u'j form a subset of u1
through uk.
When inferring the context for the derived instances, type synonyms
must be expanded out first.
Free names in the declarations d are all
defined in the Prelude; the qualifier `Prelude.' is
implicit here. The remaining details of the derived
instances for each of the derivable Prelude classes are now given.
Derived instances of Eq and Ord.
The class methods automatically introduced by derived instances
of Eq and Ord are (==),
(/=),
compare,
(<),
(<=),
(>),
(>=),
max, and
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:
(1,undefined) == (2,undefined) => False
(undefined,1) == (undefined,2) => _|_
Derived instances of Enum
Derived instance declarations for the class Enum are only
possible for enumerations.
The nullary constructors are assumed to be
numbered left-to-right with the indices 0 through n-1.
Enum introduces the class methods
toEnum,
fromEnum,
enumFrom,
enumFromThen, enumFromTo, and
enumFromThenTo,
which are used to define arithmetic sequences as described
in Section 3.10.
The toEnum and fromEnum operators map enumerated values to and
from the Int type.
enumFrom n returns a list corresponding to the complete enumeration
of n's type starting at the value n.
Similarly, enumFromThen n n' is the enumeration starting at n, but
with second element n', and with subsequent elements generated at a
spacing equal to the difference between n and n'.
enumFromTo and enumFromThenTo are as defined by the
default class methods
for Enum (see Figure 5,
page ).
For example,
given the datatype:
data Color = Red | Orange | Yellow | Green deriving (Enum)
we would have:
[Orange..] == [Orange, Yellow, Green]
fromEnum Yellow == 2
Derived instances of Bounded.
The Bounded class introduces the class
methods
minBound and
maxBound,
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:
data Pair a b = Pair a b deriving Bounded
would generate the following Bounded instance:
instance (Bounded a,Bounded b) => Bounded (Pair a b) where
minBound = Pair minBound minBound
maxBound = Pair maxBound maxBound
Derived instances of Read and Show.
The class methods automatically introduced by derived instances
of Read and Show are showsPrec,
readsPrec,
showList, and 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
(a number from 0 to 10), a value x, and a string r.
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
of the top-level constructor operator in x is less than d. Thus,
if d is 0 then the result is never surrounded in parentheses; if
d is 10 it is always surrounded in parentheses, unless it is an
atomic expression. The extra parameter r is essential if tree-like
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 returns a list of pairs
(x,r) such that showsPrec d x r == s. readsPrec is a parse
function, returning a list of (parsed value, remaining string) pairs.
If there is no successful parse, the returned list is empty.
showList and readList allow lists of objects to be represented
using non-standard denotations. This is especially useful for strings
(lists of Char).
readsPrec will parse any valid representation of the standard types
apart from lists, for
which only the bracketed form [...] is accepted. See
Appendix A for full details.
A precise definition of the derived Read and Show instances for
general types is beyond the scope of this report. However, the
derived Read and Show instances have the following properties:
- 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.
- 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.)
- The instance generated by Read allows arbitrary whitespace
between tokens on the input string. Extra parenthesis are also
allowed.
- The result of show contains only the constructor names defined
in the data type, parenthesis, and spaces. When labeled
constructor fields are used, braces, commas, field names, and
equal signs are also used.
No leading or
trailing spaces are generated. Parenthesis are only added where
needed. No line breaks are added.
- If a constructor is defined using labeled field syntax then the derived
show for that constructor will 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.
- 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.
The derived Read and Show instances may be unsuitable for some
uses. Some problems include:
- Circular structures cannot be printed or read by these
instances.
- The printer loses shared substructure; the printed
representation of an object may be much larger that necessary.
- The parsing techniques used by the reader are very inefficient;
reading a large structure may be quite slow.
- 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.
D.1 An example
As a complete example, consider a tree datatype:
data Tree a = Leaf a | Tree a :^: Tree a
deriving (Eq, Ord, Read, Show)
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 8,
Note the implicit use of 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
the class declaration shown in Figure 5
(page ).
infix 4 :^:
data Tree a = Leaf a | Tree a :^: Tree a
instance (Eq a) => Eq (Tree a) where
Leaf m == Leaf n = m==n
u:^:v == x:^:y = u==x && v==y
_ == _ = False
instance (Ord a) => Ord (Tree a) where
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
instance (Show a) => Show (Tree a) where
showsPrec d (Leaf m) = showParen (d >= 10) showStr
where
showStr = showString "Leaf " . showsPrec 10 m
showsPrec d (u :^: v) = showParen (d > 4) showStr
where
showStr = showsPrec 5 u .
showString " :^: " .
showsPrec 5 v
instance (Read a) => Read (Tree a) where
readsPrec d r = readParen (d > 4)
(\r -> [(u:^:v,w) |
(u,s) <- readsPrec 5 r,
(":^:",t) <- lex s,
(v,w) <- readsPrec 5 t]) r
++ readParen (d > 9)
(\r -> [(Leaf m,t) |
("Leaf",s) <- lex r,
(m,t) <- readsPrec 10 s]) r
|
Figure 8
Example of Derived Instances
|
The Haskell 1.4 Report
top | back | next | contents | function index
March 27, 1997