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 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. Thanks, - Conal
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
Thanks for the pointers. I'd found 10.1 but hadn't noticed 10.5. So I suggest that you use an explicit Ord instance and define min/max the
way you want.
Yep. That's my solution:
instance Ord a => Ord (AddBounds a) where
MinBound <= _ = True
NoBound _ <= MinBound = False
NoBound a <= NoBound b = a <= b
NoBound _ <= MaxBound = True
MaxBound <= MaxBound = True
MaxBound <= _ = False
MinBound `min` _ = MinBound
_ `min` MinBound = MinBound
NoBound a `min` NoBound b = NoBound (a `min` b)
u `min` MaxBound = u
MaxBound `min` v = v
MinBound `max` v = v
u `max` MinBound = u
NoBound a `max` NoBound b = NoBound (a `max` b)
_ `max` MaxBound = MaxBound
MaxBound `max` _ = MaxBound
Cheers, - Conal
On Wed, Mar 19, 2008 at 2:35 PM, Duncan Coutts
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
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)
The class Ord is not suited for partial orders. If you write your own Ord instances anyway, I'd suggest to introduce a proper new class (say Lattice), too! I hope that the computation of "uncomparable" does terminate in your case. Maybe the lattice operation "join and "meet" are even more appropriate than "min" and "max". However, if your type parameter "a" has a total order, the above derived instance looks correct. HTH Christian
AddBounds makes total orders from total orders. It just adds new least and
greatest elements.
The problem with the derived instance is that it doesn't exploit the
potential laziness of min on 'a'. Because of their types, min it can
produce partial info from partial info and (<=) and compares cannot.
- Conal
On Thu, Mar 20, 2008 at 2:00 AM, Christian Maeder
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)
The class Ord is not suited for partial orders. If you write your own Ord instances anyway, I'd suggest to introduce a proper new class (say Lattice), too!
I hope that the computation of "uncomparable" does terminate in your case. Maybe the lattice operation "join and "meet" are even more appropriate than "min" and "max".
However, if your type parameter "a" has a total order, the above derived instance looks correct.
HTH Christian
Conal Elliott wrote:
AddBounds makes total orders from total orders. It just adds new least and greatest elements.
The problem with the derived instance is that it doesn't exploit the potential laziness of min on 'a'. Because of their types, min it can produce partial info from partial info and (<=) and compares cannot.
Right, I've mixed up partial orders, partial (infinite?) values as input to total order functions. I could not construct an example, though. min (NoBound MinBound) (NoBound (NoBound undefined)) worked using ghci. Cheers Christian
Oh -- partial & partial. Thanks. I was pretty puzzled there.
The type argument I ran into trouble with represents a value as a list of
increasing lower bounds, ending in the exact value. min produces lower
bounds from lower bounds and so is immediately productive before even
knowing which argument is the lesser one. (<=) returns Bool, and so cannot
produce any partial information. Unfortunately, the derived Ord instance
omits min which therefore defaults to a definition in terms of (<=), which
therefore cannot produce partial 'a' info.
- Conal
Some references on "improving values":
@Article{Burton91:Encapsulating,
author = {F. Warren Burton},
title = {Encapsulating nondeterminacy in an abstract data type
with deterministic semantics},
journal = {Journal of Functional Programming},
year = 1991,
volume = 1,
number = 1,
pages = {3--20},
month = {January}
}
@inproceedings{Burton89:Indeterminate,
author = {F. Warren Burton},
title = {Indeterminate behavior with determinate semantics in
parallel programs},
booktitle = {FPCA '89: Proceedings of the fourth international
conference on Functional programming languages and computer architecture},
year = {1989},
isbn = {0-89791-328-0},
pages = {340--346},
location = {Imperial College, London, United Kingdom},
doi = {http://doi.acm.org/10.1145/99370.99402},
publisher = {ACM},
address = {New York, NY, USA},
}
On Thu, Mar 20, 2008 at 11:00 AM, Christian Maeder
Conal Elliott wrote:
AddBounds makes total orders from total orders. It just adds new least and greatest elements.
The problem with the derived instance is that it doesn't exploit the potential laziness of min on 'a'. Because of their types, min it can produce partial info from partial info and (<=) and compares cannot.
Right, I've mixed up partial orders, partial (infinite?) values as input to total order functions. I could not construct an example, though.
min (NoBound MinBound) (NoBound (NoBound undefined))
worked using ghci.
Cheers Christian
Conal Elliott wrote:
The type argument I ran into trouble with represents a value as a list of increasing lower bounds, ending in the exact value. min produces lower bounds from lower bounds and so is immediately productive before even knowing which argument is the lesser one.
Is this only a matter of efficiency? Can it be compared with a faster equality check that does not need to evaluate terms always, because it compares the internal pointers first (and returns True for equal ones)? Cheers Christian P.S. Maybe it is still a good idea to have a separate user defined class Min for your purpose, because then you don't have to hand-write compare functions, but then I don't know the nesting of your data types, though a generic instance Ord a => Min a may help.
Christian Maeder wrote:
Conal Elliott wrote:
The type argument I ran into trouble with represents a value as a list of increasing lower bounds, ending in the exact value. min produces lower bounds from lower bounds and so is immediately productive before even knowing which argument is the lesser one.
Is this only a matter of efficiency? Can it be compared with a faster equality check that does not need to evaluate terms always, because it compares the internal pointers first (and returns True for equal ones)?
Because min returns one of its arguments, "<=" could be defined in terms of "min" and equality. a <= b = min a b == a "==" would cause further evaluations, but if an equality could look up pointers (to unevaluated thunks) no further evaluation might be necessary, so that min and <= do basically the same.
Cheers Christian
P.S. Maybe it is still a good idea to have a separate user defined class Min for your purpose, because then you don't have to hand-write compare functions, but then I don't know the nesting of your data types, though a generic instance Ord a => Min a may help.
The issue is more than just efficiency. It's vital that these improving
values get evaluated as little as possible. In my use for functional
reactivity, they represent the times of future event occurrences.
Your (<=)-via-min idea might work in some cases, though useful pointer
equality can be pretty tricky in the presence of laziness. It's one thing
to use pointer equality in lazy memo functions, where false negatives are
okay, but in this case, a false negative (pointer inequality between
semantically equal values) would give the wrong answer for min. Also, the
assumption that min returns one of its arguments is questionable. It's
certainly not the case in Warren Burton's implementation of improving values
(refs in previous mail). Instead, min merges the lower bounds from each
argument into the result. Of course min returns a value semantically equal
to one of its arguments, but a pointer-equality test would fail, and a
semantic equality test would block.
Cheers, - Conal
On Mon, Mar 31, 2008 at 1:34 AM, Christian Maeder
Christian Maeder wrote:
Conal Elliott wrote:
The type argument I ran into trouble with represents a value as a list of increasing lower bounds, ending in the exact value. min produces lower bounds from lower bounds and so is immediately productive before even knowing which argument is the lesser one.
Is this only a matter of efficiency? Can it be compared with a faster equality check that does not need to evaluate terms always, because it compares the internal pointers first (and returns True for equal ones)?
Because min returns one of its arguments, "<=" could be defined in terms of "min" and equality.
a <= b = min a b == a
"==" would cause further evaluations, but if an equality could look up pointers (to unevaluated thunks) no further evaluation might be necessary, so that min and <= do basically the same.
Cheers Christian
P.S. Maybe it is still a good idea to have a separate user defined class Min for your purpose, because then you don't have to hand-write compare functions, but then I don't know the nesting of your data types, though a generic instance Ord a => Min a may help.
participants (3)
-
Christian Maeder -
Conal Elliott -
Duncan Coutts