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-Ed... http://hackage.haskell.org/packages/archive/EdisonAPI/1.2.1/doc/html/Data-Ed... 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