[Haskell-cafe] Re: (flawed?) benchmark : sort

[Robert Dockins]

On Thursday 13 March 2008 07:33:12 pm Aaron Denney wrote:

[snip]
> 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:

http://hackage.haskell.org/packages/archive/EdisonAPI/1.2.1/doc/html/Data-Edison.html
http://hackage.haskell.org/packages/archive/EdisonAPI/1.2.1/doc/html/Data-Edison-Coll.html

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.


Rob Dockins