Simon suggested I produce a proposal for the three valued comparison.
I'm not really happy that this has had enough discussion yet.
The suggestion was made that we start with:
data _Tag = _LT | _EQ | _GT
to avoid poluting the programmer's namespace. Are these names `visible'
to the programmer (my reading of the report suggests these are not
allowed). If they are not visible, it will be tricky for the programmer
to produce new instances since `_cmp' will be tricky to define.
If they are visible, I guess we should also have _True and _False for
consistency!
Second, if we are really to allow partial Ord-erings, then we need to decide
what to do about incomparable values. Perhaps we need
data _Tag = _LT | _EQ | _GT | _INC
Frankly, I think this is getting messy. I suggest that Ord be reserved for
Total Orderings and all references and code for partial ordering should be
changed to reflect this change. This is a minor change and shouldn't effect
the operation of the standard prelude.
Users should be discourage from using Ord instances for partial orderings.
Perhaps the text in section 4.3 could use a partial ordering as an example,
e.g.
class Eq a => PartOrd a where
(<=?), (<?), (>?), (>=?), (==?), (/=?) :: a -> a -> Bool
x ==? y = x == y
x /=? y = x /= y
x >? y = y <? x
x >=? y = y <=? x
x <? y = x <=? y && x/=y
Personally, I'd leave min and max out of this class.
This make the following instance example fairly obvious in 4.3.2
instance (Eq a, Ord a) => PartOrd a where (<=?) = (<=)
Why is this so important? Many of our basic algorithms rely on total,
not partial, orderings. List merge and sorting, tree building, etc.
are examples. The obvious example is using sets of sets: where sets
are represented by ordered lists. Starting with a total ordering for
the basic set members - lets assume integers for simplicity, a set
can be represented by an ordered list. Set equality is built/derived
from list equality but say we choose to define (<=) to mean subset
rather than lexicographic ordering (as normally defined for lists).
Here is some Gofer:
> data Set a = Set [a]
> set xs = Set (nub (sort xs)) -- using insertion sort
> instance Eq [a] => Eq (Set a) where Set x == Set y = x==y
> instance Eq a => Ord (Set a) where
> Set x <= Set y = null (x \\ y) -- ignoring efficiency
Try some expressions:
? set[3,1] == set[1,3]
? set[set[1],set[3]] == set[set[3],set[1]]
The first works the second doesn't. Using qsort in set produces
more peculiar results. Some sorting algorithms might fail.
This type of problem should be avoided. The distinction between partial
and total orderings may be much more important to programmers than it
is to mathematicians. Hmmm, remember Pascal? I wonder what C++ programmers
do?
regards
b++
_______________________________________________________________________
Bob Buckley Phone: +61 8 302 3465
School of Computer and Information Science Fax: +61 8 302 3381
University of South Australia, The Levels,
Pooraka, SA 5095, Australia email: [EMAIL PROTECTED]
