Hans Aberg:
>The total order is needed in order to make the balanced trees used for the
>sets/maps. So what I have in my mind is that somehow Haskell produces a
>default total order on elements. This could be the declaration order or an
>alphabetical order, or whatever (and it is nice to humans that the elements
>always come out in a specific, known order). For elements that have a
>natural order, one can use that of course. And as an option, one can think
>of that it can be overridden.
There is another good reason to have a total order: it makes reduction
operations (folds) over the structure well-defined.
>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.
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).
Bjorn Lisper
