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

[Fergus Henderson]

On 11-Nov-2000, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> Fergus wrote:
> > On 10-Nov-2000, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> > > 
> > > Fergus wrote:
> > > > OK, I'll give up on `..` for now, and go back to just wanting to be
> > > > able to support a dense_bitset type.  For that type, I need `first'
> > > > and `last' methods.  I guess it doesn't strictly *need* contiguous
> > > > to_int values, though.
> > > 
> > > I think it's better to leave the `enum' class as it is for now,
> > > rather than add stuff which may or may not be useful later.
> > > We can add a `bounded_enum' class derived from `enum'
> > > for the `enum_first' and `enum_last' methods.
> 
> > I'm happy with the design, but I object to the use of the name `enum'.
> > That name should be reserved for something that is actually enumerable, IMHO.
> 
> Just to explain why I'm keen on this use of `enum':
> An enumerable set is a set for which there is a one-to-one mapping
> onto a subset of the integers. What Fergus is suggesting should
> be denoted by `enum' is the proper subset of the enumerable sets for
> which the range of the mapping is a contiguous set of integers.
> It seems to me to be a bit confusing to use (an abbreviation of) the
> name of a set to describe a proper subset of that set.

I did a web search, and pulled up the following definitions
(from <http://www.earlham.edu/~peters/courses/logsys/glossary.htm>):

 |      Enumerable set.
 |              Roughly, a set that can be translated into a sequence. More
 |              precisely, a set such that every one of its members has at
 |              least one counterpart in a certain sequence (though they
 |              may have more than one counterpart), and every term in
 |              the sequence has a counterpart in the set. The resulting
 |              sequence is called an enumeration of the set. The set {a,
 |              b, c} is enumerated by the sequence <a, b, c>, but also
 |              by the sequence <a, a, c, b>; it is not enumerated by the
 |              sequence <a, a, c, c>.
 | 
 |      Effectively enumerable set.
 |              An enumerable set for which there is an effective method
 |              for ascertaining the nth term of the sequence for every
 |              positive integer n.

For computer programming, I'm inclined to think `enum' should be used
for something which is *effectively* enumerable.

We should also consider consistency with Haskell and other languages.
Haskell's `Enum' class has `pred' and `succ' methods, so it is
effectively enumerable.  Although the Haskell does not explicitly
require that the type be mapped to a contiguous subset of integers,
the default method implementations (for `pred', `succ', `enumFrom',
`enumFromTo', `enumFromThenTo') all assume that this is the case.
(The Haskell report doesn't document *any* requirements on class
methods; for example, `==' is not required to be an equivalence
relation, instances of the `Monad' class are not required to satisfy
the monad laws, etc.  On the other hand, Haskell defines an instance
`Enum Float', which although it does map to a contiguous subset of
integers doesn't satisfy the reversible_hash requirements... this
instance declaration is rather controversial, though.)

Hmm, I'm swinging back to Ralph's suggestion that there are a
bunch of different classes we could consider.  E.g.
	
	mathematically enumerable sets	(to_int and from_int methods)
	effectively enumerable sets	(pred and succ methods)
	densely enumerable sets		(adds requirement that to_int maps
					 to contiguous values)
	ordered enumerable sets		(adds requirement that to_int
					 preserves ordering)

Another possible name that we could use for the version that doesn't
guarantee contiguity is `sparse_enum'.  That might be better than
`reversible_hash', and goes well with `sparse_bitset'.

However, a counter-argument is that if we're going to have some
complicated hierarchy, then we should use the simple name (`enum') for
the base class, and use adjectives (`foo_enum') for the derived classes.

So, after much consideration, I think I could live with the name `enum'.

I suggest you commit it with that name for now, and we can discuss the
naming issue at the Mercury meeting next week.

-- 
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
--------------------------------------------------------------------------