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