Expected behavior of "deriving Ord"?
Duncan Coutts
duncan.coutts at worc.ox.ac.uk
Wed Mar 19 17:35:36 EDT 2008
On Wed, 2008-03-19 at 14:11 -0700, Conal Elliott wrote:
> I have an algebraic data type (not newtype) that derives Ord:
>
> data AddBounds a = MinBound | NoBound a | MaxBound
> deriving (Eq, Ord, Read, Show)
>
> I was hoping to get a min method defined in terms of the min method of
> the type argument (a). Instead, I think GHC is producing something in
> terms of compare or (<=). Maybe it's defaulting min altogether. What
> is the expected behavior in (a) the language standard and (b) GHC?
The H98 report says:
10.1 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) => _|_
All derived operations of class Eq and Ord are strict in both
arguments. For example, False <= _|_ is _|_, even though False
is the first constructor of the Bool type.
Which doesn't seem to help but looking at the later example:
10.5 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 10.1, 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 6.1 (page ).
So that is relying on the default class methods:
max x y | x <= y = y
| otherwise = x
min x y | x <= y = x
| otherwise = y
As for GHC, Looking at the comments in compiler/typecheck/TcGenDeriv.lhs
it says that it generates code that uses compare like so:
max a b = case (compare a b) of { LT -> b; EQ -> a; GT -> a }
min a b = case (compare a b) of { LT -> a; EQ -> b; GT -> b }
> The reason I care is that my type parameter a turns out to have
> partial information, specifically lower bounds. The type of min
> allows this partial info to be used in producing partial info about
> the result, while the type of (<=) and compare do not.
So I suggest that you use an explicit Ord instance and define min/max
the way you want.
Duncan
More information about the Glasgow-haskell-users
mailing list