[prev in list] [next in list] [prev in thread] [next in thread] 

List:       e-lang
Subject:    Re: [e-lang] [Caja] Equality of mappings in E
From:       David-Sarah Hopwood <david.hopwood () industrial-designers ! co ! uk>
Date:       2009-03-12 17:31:06
Message-ID: 49B946DA.70009 () industrial-designers ! co ! uk
[Download RAW message or body]

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 ⚥

_______________________________________________
e-lang mailing list
e-lang@mail.eros-os.org
http://www.eros-os.org/mailman/listinfo/e-lang

[prev in list] [next in list] [prev in thread] [next in thread]