On Mar 6, 2006, at 1:33 PM, Christian Maeder wrote:
Robert Dockins wrote:
Well, this obviously depends on what you mean by "equal". That can get slippery pretty fast. I assume from your comments that you mean extensional equality (ie, viewing the map as a partial function with a known finite domain).
Right, this corresponds to the Eq instance for the current Data.Map (with a safe fold) as an _abstract_ data type.
I can hardly imagine a (finite) map implementation without Ord instance for the keys.
http://www.haskell.org/ghc/docs/latest/html/libraries/base/System-Mem- StableName.html#t%3AStableName No Ord instance. Would be very useful to be able to put it in a map; it hashes, so its not a total waste to do it. I recall seeing conversations on some haskell list in the past about how people wanted to put stable names in Data.Map but couldn't because of the need for an Ord instance. Really any data type which isn't totally ordered but can be hashed could be used in a map this way. (Not implemented in Edison currently, but it should be).
With equality only you have no chance to yield the keys of equal maps in a fixed order (by a toList function).
Right.
Thus an association list is not a (mathematical) map (and your fold function is fine for such lists).
I don't think I agree here. What definition are you using for map? Maps don't require a total ordering on their domain. http:// mathworld.wolfram.com/Map.html Or are you getting at something else?
These properties _can't_ be guaranteed (at least not by Haskell compilers).
I know, also the total-order-property of Ord instances can not be guaranteed (but "deriving" helps, of course).
However, even with foldr, foldl, etc, there is a degree undefinedness if the data structure is a finite relation rather than a finite map (in what order should you present elements bound to equal keys?). The folds for bags have similar properties.
Relations are (conceptually) sets of pairs and bags are multisets (or maps from elements to their occurrence counts). In both cases I'd expect to see an ascending ordered list when shown.
You'd need a total ordering on the elements for that -- Edison doesn't assume anything about the elements of an associated collection (and neither does Data.Map). What if you wanted a relation/map between, say, integers and functions :: String -> Bool or between Strings and IO actions or something like that? Re: bags as maps to counts; this can be problematic, for reasons discussed here (http://www.eecs.tufts.edu/~rdocki01/docs/edison/Data- Edison-Coll.html) See the section titled "Notes on Observability". If you assume a world where everything has an Eq instance representing decidable leibniz equality and Ord instances representing total orderings, a lot of things become easier. Unfortunately, we don't live in that world, which is why we have to worry about all this other stuff. The only thing we assume is that an Eq instance defines some equivalence relation and that an Ord instance (if it exists) defines a total ordering (and if those assumptions are violated, all is lost and we give up).
Also for Tupels there are several possibilities for total orderings, but the type class Ord forces you to pick one.
This is true, but orthogonal. I actually considered adding an API where you could specify orderings with arbitrary functions :: a -> a -
Ordering, but I decided it would be too hard to use (and a pain to write besides).
Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG