robdockins at fastmail.fm
Mon Mar 6 14:25:43 EST 2006
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.
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).
> 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://
Or are you getting at something else?
>> These properties _can't_ be guaranteed (at least not by Haskell
> 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
Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
More information about the Libraries