Edison 1.2rc2

Christian Maeder maeder at tzi.de
Tue Mar 7 06:51:06 EST 2006

Robert Dockins wrote:
>> 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

Well, "A map is a way of associating unique objects to every element in 
a given _set_"! The (strong or given) equality of [(a,b)] does not 
correspond to the (possibly uncomputable) equality of maps (where order 
does not matter). So association lists are no maps unless you hide (or 
ignore) all functions that allow you to observe differences (i.e, your 
fold and elements function).

Also for hash maps you have no chance to order elements with equal hash 
keys. Maybe all computable and observable maps (and sets) require a 
total order?

Of course all mentioned data structures are useful for certain purposes 
(and it's maybe only a matter of documentation).

Cheers Christian

More information about the Libraries mailing list