robdockins at fastmail.fm
Tue Mar 7 11:20:12 EST 2006
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
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
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.
More information about the Libraries