Re: [Cbor] "ordered hash"

[Kio Smallwood <[e-mail]>]

Yes you can use my text, I'll have to think about what address to use...


Cheers, 

Kio 

On 2020-07-30 10:05, Carsten Bormann wrote:

> Thank you, Kio!
> 
> I think I will write a subsection in 
> https://www.ietf.org/id/draft-bormann-cbor-notable-tags-02.html
> (even if we don't have the actual tags yet), probably 6.4.
> 
> Can I use your text as a contribution (like I did [and still plan to do] with Peter Occil's contribution)?  (I would need some address information that you want to see in a draft/RFC.)
> 
> Grüße, Carsten
> 
> On 2020-07-30, at 10:59, Kio Smallwood <[e-mail]> wrote:
> 
> 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)]

_______________________________________________
CBOR mailing list
[e-mail]
https://www.ietf.org/mailman/listinfo/cbor