[e-lang] [Caja] Equality of mappings in E

[David-Sarah Hopwood]

Kevin Reid wrote:
> On Mar 11, 2009, at 22:15, Bill Frantz wrote:
[...]
>>>>> Mark S. Miller wrote:
>>>>>>    ? ["a" => 1, "b" => 2] == ["b" => 2, "a" => 1]
>>>>>>    # value: false
[...]
>> It would seem that you could canonicalize the order for any ordered  
>> type, including string. The process might have an execution time cost.
> 
> Yes; the problem is that key-type is not an explicit property of  
> ConstMaps, and it would be rather surprising, if not actively  
> hazardous, to have the behavior "a ConstMap's keys are sorted if the  
> keys all have op__cmp methods", especially as "are these objects all  
> of the same type?" is -- nontrivial -- in E.

I agree. The approach of having separate sorted and unsorted map
"classes" (with the same interface) doesn't have this problem.

> If you want a "sorted map literal" or to reestablish sortedness you  
> can always write:
> 
>    ? ["b" => 2, "a" => 1].sortKeys()
>    # value: ["a" => 1, "b" => 2]

That's not really providing the same functionality as a sorted map,
since sorting is at best O(n log n) (for a comparison sort), whereas
inserting an item into a balanced tree structure, maintaining sortedness,
is typically O(log n).

-- 
David-Sarah Hopwood ⚥