[m-dev.] for review: use bitsets in quantification

[Fergus Henderson]

On 07-Nov-2000, Ralph Becket <rbeck at microsoft.com> wrote:
> 
> I agree that the solution here would be to have a range of specialised
> typeclasses.

Yep.  But the drawback of this approach is complexity --
it makes the library more flexible, but more difficult to
learn and a little more difficult to use.  As a design principle,
I think we should create type classes in the standard library for the
things that will commonly be encountered, but for esoteric needs
people can always use user-defined classes.

> Several constraints have been discussed on this thread:
>
> * bounded enumerable types isomorphic to (a subset of) int
> :- typeclass enum(T) where [
> 	func to_int(T) = int,
> 	func from_int(int) = T is semidet
> ].
> 
> * (unbounded) enumerable types isomorphic to (a subset of) integer

See below.

> * enumerable types isomorphic to all ints/integers
> :- typeclass complete_enum(T) <= enum(T) where [
> 	% all [X:int] some [Y:T] Y = from_int(X)
> ].

I don't think that one will be very useful.  Certainly not for `int',
anyway.  It might perhaps be useful for `integer', but if so, users
can easily define it for themselves. 

Note that defining classes with too few methods or too few invariants
is not a problem, since the user can easily add their own derived
classes that add new methods or new invariants.  In contrast, defining
a standard library class with too many methods or too many invariants
_can_ cause problems, because user A will write code that uses this
type class, even though their code doesn't make use of all of those
methods/invariants, and then this will prevent user B from safely
reusing user A's code, because user B's type can't define the extra
methods (except as stubs that just throw exceptions), and can't
satisfy the extra invariants, and user B doesn't know that user A's
code doesn't depend on those methods/invariants.  Even if user B
does find this out, they should not write code that depends on it,
since they have no way of ensuring that it will remain the case in
future versions of A's code.

> * enumerable types isomorphic to a contiguous subset of int/integer
> :- typeclass contiguous_enum(T) <= enum(T) where [
> 	% all [X:T, Y:T, N:int]
> 	%	(to_int(X) =< N, N =< to_int(Y)) =>
> 	%		some [Z:T] Z = from_int(N)
> ].

I think that this one will be much more useful than the non-contiguous
versions.  After all, if any type can be mapped onto a non-contiguous
subset of int/integer, it can be mapped onto a contiguous subset of
int/integer, and in almost all cases this will be very easy.  What
would be the point in defining a `to_int' function that mapped things
to a non-contiguous subset?  The only effect of doing that would be to
make it impossible to efficiently enumerate on that type.  I don't see
that possibility being useful in practice.

There might be some types for which you want to defined a different
function, called something other than `enum__to_int', that maps the
type to non-contiguous ints.  But for that function you can use a
different name and a different type class.

> * enumerable types isomorphic to an arbitrary subset of int/integer

This is the same as the first two that you listed.
(The only difference is that you added the word "arbitrary".)
For reasons explained above, I think only the version that
maps to a contiguous subset will be useful.  I think this
one and the first two above should not go in the standard library.

> * enumerable types with a lower bound
> :- typeclass lb_enum(T) <= enum(T) where [
> 	func min = T
> ].
> 
> * enumerable types with an upper bound
> :- typeclass ub_enum(T) <= enum(T) where [
> 	func max = T
> ].
>
> * enumerable types with both an upper and lower bound
> :- typeclass bounded_enum(T) <= (lb_enum(T), ub_enum(T)) where [].
>
> I like Fergus' suggestion of using `enum' for int enumerations and
> `enumerable' for integer enumerations.

Since `enum' uses int, all enums will have lower and upper bounds, and
so I think we might as well just put `enum_first' and `enum_last'
functions in the `enum' type class.  That will simplify the type class
hierarchy without restricting flexibility.  (BTW I think `enum_first'
is a better name for the value which is lowest in the enumeration
ordering; `min' should be reserved for the value which is lowest in
the usual ordering, which in general might be unrelated to the
enumeration ordering.)

For `enumerable', it does make more sense to split out the lower
and upper bounds, since natural numbers (`unsigned' or perhaps
`natural', i.e. non-negative arbitrary-precision integers) might
be quite commonly used, and have a lower bound but no upper bound.
But off-hand I can't think of any good example algorithms which
would use the `lb_enumerable' type class.  Hmm...

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------