Subject: [Cbor] "ordered hash"

From: Michael Richardson <[email-masked]>
Date: Wed, 29 Jul 2020 13:56:16 -0400

Do we have a canonical term for an array of tuples that behaves like a map, but
isn't, because it's an ordered array of 2*n elements?

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: Brendan Moran <[email-masked]>
Date: Wed, 29 Jul 2020 22:37:46 +0000

I’d probably call it a multi-map if it were sorted. Perhaps it’s an ordered multi-map?

Brendan

> On 29 Jul 2020, at 18:56, Michael Richardson <[email-masked]> wrote:
>
>
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

---

From: Kio Smallwood <[email-masked]>
Date: Thu, 30 Jul 2020 00:44:30 +0100

I wrote a proposal for tag 272 ordered map.

https://github.com/Sekenre/cbor-ordered-map-spec

Unfortunately no one has approved the tag allocation or given me any guidance on how to proceed.

I'm probably doing something wrong but i haven't had time to do any follow up.

Hope its useful for you anyway.

Cheers,
Kio

On 29 July 2020 23:37:46 BST, Brendan Moran <[email-masked]> wrote:
>IMPORTANT NOTICE: The contents of this email and any attachments are
>confidential and may also be privileged. If you are not the intended
>recipient, please notify the sender immediately and do not disclose the
>contents to any other person, use it for any purpose, or store or copy
>the information in any medium. Thank you.

-- 
Sent from my Android device with K-9 Mail. Please excuse my brevity.

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 30 Jul 2020 06:08:26 +0200

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

---

From: Alexander Pelov <[email-masked]>
Date: Thu, 30 Jul 2020 09:46:16 +0200

Hi all,

Several years ago we had this type of discussion for the use of
COMI/CORECONF. We called it in a couple of different ways:
- DeterministicMultimaps
- COMAP (CBOR Order-preserving Multimap)
- Order-Keeping Multimap (OKMM)

Unfortunately, I don't think we published any open specs outside the Task
Force (although we did have quite some discussion at CORE WG).

One of the latest specs we had is attached (sorry for the PDF).

Cheers,
Alexander

On Thu, Jul 30, 2020 at 6:08 AM Carsten Bormann <[email-masked]> wrote:

> 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.
>
> 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”):
>
> 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:
>
> 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:
>
> 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
>

---

From: Kio Smallwood <[email-masked]>
Date: Thu, 30 Jul 2020 09:59:52 +0100

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 a…

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:

> Let's look into this.
> 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"):
> 
> 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.  
> 
> So [["aaa", 1], ["aaa", 2], ["bbb", 3]] becomes ["aaa", [1, 2], "bbb", [3]]
> 
> So [["aaa", 1], ["aaa", 2], ["bbb", 3]] becomes ["aaa", [1, 2], "bbb", 3]
>

---

From: Kio Smallwood <[email-masked]>
Date: Thu, 30 Jul 2020 10:05:07 +0100

Hi Alexander, 

Thanks for this, it's good to see people thinking in similar directions!

Cheers, 

Kio 

On 2020-07-30 8:46, Alexander Pelov wrote:

> Hi all, 
> 
> Several years ago we had this type of discussion for the use of COMI/CORECONF. We called it in a couple of different ways:  
> - DeterministicMultimaps 
> Unfortunately, I don't think we published any open specs outside the Task Force (although we did have quite some discussion at CORE WG). 
>

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 30 Jul 2020 11:05:58 +0200

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 <[email-masked]> wrote:
> 
> Thanks Carsten!
> 
> 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.
> 
> Yes a flattened AList is the main use case. Allocating tags for the other structures at the same time makes good sense.
> 
> Thanks,
> 
> Kio
>

---

From: Kio Smallwood <[email-masked]>
Date: Thu, 30 Jul 2020 10:22:50 +0100

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:

> (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
>

---

From: Michael Richardson <[email-masked]>
Date: Fri, 31 Jul 2020 13:33:34 -0400

Carsten Bormann <[email-masked]> wrote:
    > have double the argument that the map head has), we can save 1 byte per
    > k/v pair (“flattened alist”):

    > 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.

I am definitely referring to this.
"flattened alist" is a new term to me, and I'm mostly happen with this term.
I am unclear what the "second one" is.

I think that:
 Alist: [[“a”, 1], [“b”, 2]]
 flatened alist: [“a”, 1, “b”, 2]

    > So [[“aaa”, 1], [“aaa”, 2], [“bbb”, 3]] becomes [“aaa”, [1, 2], “bbb”, 3]

It's an optimization which is not preserve the order.
That is:
   [[“aaa”, 1], [“aaa”, 2], [“bbb”, 3]]
vs:[[“aaa”, 1], [“bbb”, 3], [“aaa”, 2]]
vs:[[“aaa”, 2], [“bbb”, 3], [“aaa”, 1]]

I agree that a tag may be in order.