I confess I've become a bit lost. I'm not longer sure I understand the points you're making; I'll make my best effort to answer, but if I reply to points other than the ones you've made, please forgive me. On Mar 7, 2006, at 6:51 AM, Christian Maeder wrote:
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_"!
Clarification: "finite set" (for our purposes). I believe you are highlighting that sets have no intrinsic notion of order?
The (strong or given) equality of [(a,b)] does not correspond to the (possibly uncomputable) equality of maps (where order does not matter).
What I think you are saying: Let al :: [(a,b)] be a finite association list, where type 'a' has a decidable equality relation, and if (x,y) and (w,z) both appear in al such that x == w (equality), then y === z (identity, not necessarily decidable). Then let toMap1 and toMap2 be two different implementations of coercion from association lists to maps and: m1 = toMap1 al m2 = toMap2 al We must have that m1 is extensional equal to m2. However, if we have fromMap1 and fromMap2 that extract an association list from the different maps we might have: fromMap1 m1 <> fromMap2 (where tuple equality is defined using == for a and === for b) The problem is that there is an entire equivalence class of association lists each of which represents the map in question; each "fromMap*" has to make a particular concrete choice from this equivalence class, but they might make different choices. I think I have decided to call such operations "ambiguous" because they (conceptually) generate a set of possible results and arbitrarily choose one. Clearly, such behavior might be confusing to a programmer, so it should be carefully marked. The "safe" operations you prefer collapse the ambiguity as part of the function's contract by, eg, specifying that keys appear in order. I also suspect this is the primary source of our disagreement; I'm interested in allowing programmers access to ambiguous operations, and you think that the exposed API should only consist of well- defined (non-ambiguous) operations. Is that a fair characterization?
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).
If I were being particularly pedantic, I would instead say that association lists are not maps (at all). Rather, they represent and can be transformed into (finite) maps, in much the same way that, eg, source code represents and can be transformed into a particular abstract syntax tree. Parsing and pretty printing a source code file will not (in general) result in identical concrete syntax. Would you therefore say that concrete source code is not a program? You might (if you were being particularly pedantic), but I think most people would simply equate source code "up to parsing", at least when talking about the "program". I think we have the same situation here, were association lists can be informally identified with the maps they represent, but have to be thought about up to reordering.
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
What do you mean by computable in this context?
Of course all mentioned data structures are useful for certain purposes (and it's maybe only a matter of documentation).
Cheers Christian
Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG