Edison 1.2rc2

[Robert Dockins]

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