Me:
>> There is another good reason to have a total order: it makes reduction
>> operations (folds) over the structure well-defined.
Kevin Atkinson:
>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.
It depends. Sometimes you do fold over binary operations which are
associative and commutative, and then the order does not matter of
course. But sometimes this is not true - floating-point operations are
typically not exactly associative and commutative and then the ordering does
matter for the numerical precision. It must then be up to the programmer to
use knowledge of the numerical algorithm and indata to decide whether a
"loose specification" of fold which does not require a well-defined ordering
is OK or not.
One can come up with examples where the order of summation makes a big
difference in error propagation. Whether pathological or not, the programmer
must have control when necessary.
Other operations are non-commutative, like function composition. There is an
amusing example in Hillis, Steele "Data Parallel Algorithms", CACM vol 29,
1986, where they derive a data parallel algorithm for lexical analysis by
expressing this problem as a reduction over composition of transition
functions for finite automata. This reduction can be parallelized due to
associativity of function composition but the order of the functions being
composed cannot be changed.
>> We require that there is a function enumerate :: Bounds a -> [a] which
> provides a total order of the elements ....
>Do strings fall within the requirements?
Yes (use lexicographic order), but we don't have them for now.
Bjorn Lisper
