Bjorn Lisper wrote:
>
> There is another good reason to have a total order: it makes reduction
> operations (folds) over the structure well-defined.
But how important is having a fold well defined. For many common
numerical operations such as summing a list, taking the product of a
list, etc. The order in which the elements get folded does not matter.
All that matters is that each element gets represented exactly once.
>
> >The main point though is that the total order exists, and is a sorting
> >order separate from the Ord derivation.
>
> >Then Haskell uses this to implement sets and maps by using C++ STL style
> >balanced trees. As Haskell already has generic variables, just as in the
> >case of lists, it needs only be implemented once.
>
> We have been working for a while on a related topic: support for generic and
> convenient collection-oriented programming over indexed structures. In order
> to achieve this, we have designed something called "data fields" which can
> be seen as arrays generalized to more arbitrary index sets than the
> "rectangular" ones given by array bounds. So we have a data type "Bounds a"
> which provide representations of sets of elements of type a, and some
> abstract set operations. Bounds be either "dense" (array-like bounds),
> "sparse" (general finite sets), or cartesian products. Data fields are
> created from bounds in Bounds a and functions a -> b.
>
> We require that there is a function enumerate :: Bounds a -> [a] which
> provides a total order of the elements in any bound defining a finite
> set. This is exactly to make operations like folds well-defined for any
> finite data field regardless of the "shape" of its bound. We assume a
> predefined total order on elements of non-product data types (we require
> that these belong to the class Ix), and if a is a product data type then we
> use the lexicographical ordering on tuples. We use balanced trees to
> represent "sparse" bounds. So in some sense we seem to be quite close to
> what you ask for.
Do strings fall within the requirements?
>
> Our implementation is a somewhat rehacked version of nhc from
> Gothenburg/York. It has been "almost finished" for a while now (some minor
> things to polish) and we will make it available on the net as soon as this
> is done.
>
> Just a final comment on total orders on sets: this makes sense, as regards
> operations where the order is important for the semantics, only if the
> elements of the set are drawn from an enumerable set. It would not be very
> sensible to, for instance, try to impose a total order on a set of
> functions. A total order of the objects representing the functions would of
> course be possible and could be used to have the balanced trees, but it
> would not be possible to, say, have a well-defined fold over that kind of
> set (or any indexed structure using this set as index set).
Well that depends on how you define well defined. For most cases simply
having a a list of functions appear in the same order through out the
execution of the program should be enough.
--
Kevin Atkinson
[EMAIL PROTECTED]
http://metalab.unc.edu/kevina/
