Edison 1.2rc2

[Christian Maeder]

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. 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).

> 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.

Also for Tupels there are several possibilities for total orderings, but 
the type class Ord forces you to pick one.

Christian