maeder at tzi.de
Mon Mar 6 13:33:26 EST 2006
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
> 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.
Also for Tupels there are several possibilities for total orderings, but
the type class Ord forces you to pick one.
More information about the Libraries