[Haskell-cafe] Re: (flawed?) benchmark : sort
robdockins at fastmail.fm
Thu Mar 13 23:01:47 EDT 2008
On Thursday 13 March 2008 07:33:12 pm Aaron Denney wrote:
> I've seen mention of difficulties with Data.Map, and edison, but not
> in enough detail to really grasp what the problems are. Until I do, my
> natural bias (which I'm trying to resist, really) is that it's a matter
> of lazy coding, not any inherent difficulty.
For the specific case of Edison, the Haddock documentation for the following
two modules tells the whole sordid story:
The Cliff Notes version is that Edison assumes the following things about Eq
and Ord instances:
* An Eq instance correctly defines an equivalence relation (but not
necessarily structural equality); that is, we assume (==) (considered as a
relation) is reflexive, symmetric and transitive, but allow that equivalent
items may be distinguishable by other means.
* An Ord instance correctly defines a total order which is consistent with the
Eq instance for that type.
It's not explicitly stated, but Edison also assumes that the operations within
a class are consistent, i.e., that (not (x == y)) calculates the same
function as (x /= y), etc. I suppose that should go in the docs too. Edison
makes no particular assumptions about min and max, except that they are
consistent with the defined order.
Anyway, the end result for Edison is that some operations aren't well-defined,
and can't be made well-defined without restrictions. For example, consider
the operation of folding in non-decreasing order over the elements of a
multi-set. If the function being folded distinguishes between two elements x
and y, but (compare x y) = EQ, and x and y are both contained in the
multi-set, then the result of the fold depends on internal state that is not
supposed to be user-visible (e.g., the exact shape of a balanced tree).
Blah, blah, blah, its all in the documentation. The point is that making
loose assumptions about the meaning of the operations provided by Eq and Ord
complicates things in ways that can't be made to go away.
More information about the Haskell-Cafe