Re: [Cbor] "ordered hash"

[Carsten Bormann <[e-mail]>]

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)]