Re: [Cbor] "ordered hash"

[Kio Smallwood <[e-mail]>]

Thanks Carsten!

> I think this idiom is frequent enough that it should get a 1+1 tag.

Yes I agree.

> The difference from a map is that this is both order-preserving and allowing duplicate keys; whether you want one or two of these properties on the application data model level may differ between applications.

I've always felt that allowing duplicate keys is unnecessary, does it
need to be bundled with order-preserving? Your other example MList<K, V>
= [* (K, [* V])] covers this use case nicely.

> FAList<K, V> = [* (K, V)]

Yes a flattened AList is the main use case. Allocating tags for the
other structures at the same time makes good sense. 

Thanks, 

Kio 

On 2020-07-30 5:08, Carsten Bormann wrote:

> On 2020-07-30, at 01:44, Kio Smallwood <[e-mail]> wrote: 
> 
>> I wrote a proposal for tag 272 ordered map.
>> 
>> https://github.com/Sekenre/cbor-ordered-map-spec
> 
> (272 is already taken: Non-UTF-8 CESU-8 string.)
> 
>> Unfortunately no one has approved the tag allocation or given me any guidance on how to proceed.
> 
> Let's look into this.
> 
> I think this idiom is frequent enough that it should get a 1+1 tag.
> 
> The difference from a map is that this is both order-preserving and allowing duplicate keys; whether you want one or two of these properties on the application data model level may differ between applications.
> 
> The traditional alist (association list) is
> 
> AList<K, V> = [* [K, V]]
> 
> By using the exact structure of a map (except that the array head will have double the argument that the map head has), we can save 1 byte per k/v pair ("flattened alist"):
> 
> FAList<K, V> = [* (K, V)]
> 
> So [["a", 1], ["b", 2]] becomes ["a", 1, "b", 2]
> 
> I'm not sure which of these MCR was inquiring on.  The first is definitely an alist, and there is no need for a new term.  The second can be called an ordered multimap, but there are other structures that also deserve this name.  
> 
> If adjacent duplicate keys of non-trivial size are likely in an ordered multimap, a better version of the multimap is:
> 
> MList<K, V> = [* (K, [* V])]
> 
> So [["aaa", 1], ["aaa", 2], ["bbb", 3]] becomes ["aaa", [1, 2], "bbb", [3]]
> 
> If V can never be an array (*), this can be further optimized into:
> 
> OMList<K, V> = [* (K, [2* V] / V)]
> 
> So [["aaa", 1], ["aaa", 2], ["bbb", 3]] becomes ["aaa", [1, 2], "bbb", 3]
> 
> Further refine by using delta coding for the keys (works best with sorted keys), etc.  Also, a map can be used for the outer structure if order preservation is not actually needed:
> 
> MMap<K, V> = {* K => [* V]}
> OMMap<K, V> = {* K => [2* V] / V}
> 
> There are many idioms to choose from; it would probably be best to define tags for at least each of the ones listed here.  I think FAList (what Kio proposed) is the one that will see the most use.
> 
> Grüße, Carsten
> 
> (*) Or extra-wrap just arrays:
> OEMList<K, V> = [* (K, [2* V] / [V .and [* any]] / V)]