Edison 1.2rc2

[Robert Dockins]

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