Add a map type to LF

[bame-da]

There have been several discussion to add a new type Map K V to DAML-LF in order to give us maps with arbitrary keys in DAML and a sensible representation in app languages. The issues that arise are:

• The engine needs to be deterministic. Which means the representation of the map needs to be as well. @remyhaemmerle-da recommends defining an internal ordering on Value and using a tree map.
• gRPC doesn't have arbitrary maps so we need to represent maps as a [(K, V)] on the wire. Again, to get determinism, this needs to be ordered so we have complexity n log(n) somewhere.
• JS doesn't have a good map type for us to use in the bindings. @stefanobaghino-da recommends implementing our own.

If I got this right, the work would be

1. Define/implement ordering on Value
2. Implement LF type TreeMap K V and serialisation to and from [(K, V)] (with the write path doing the ordering and checking for duplicate keys)
3. Implement JS Map type
4. Translate [(K, V)] to and from idiomatic maps in Java and JS
5. Write a DA.TreeMap DAML lib

And the main tradeoff is that our maps would be O(log(n)), but I find that perfectly acceptable. If anyone needs an O(1), they can always write a MapKey instance.

Anything I missed? Does this sound like a good way to go? If so, how much effort would this be?

[stefanobaghino-da]

Rationale behind implementing our own map type in the Node.js bindings

Apart from the JSON subset, which easily maps to DAML TextMaps, JavaScript has a Map type of its own which however uses the SameValueEquality algorithm for key equality. For objects this boils down to referential equality, which makes the following snippet possible:

const m = new Map([[{a: 1}, 42], [{a: 1}, 47]]) // m is now Map { { a: 1 } => 42, { a: 1 } => 47 }
m.get({ a: 1 }) // returns undefined
const k = { a: 1 }
const n = new Map([[k, 42], [k, 47]]) // n is now Map { { a: 1 } => 47 }
n.get(k) // returns 47

Using this map could hurt the usability of the bindings because the keys would come from the network, so in order for the user to look up keys they would have to iterate the map, finding the key they're looking for and then actually perform the lookup (which basically defeats the purpose of using a map in the first place).

Since implementing a simple hashmap should be a fairly easy task, I would recommend implementing our own rather than depending on external dependencies for this.

/cc @bame-da

[hurryabit]

@remyhaemmerle-da We need something like an Ord constraint or a polymorphic comparison function in DAML-LF for this to work pleasantly.

[remyhaemmerle-da]

@martin-drhu-da We need also something likeorderable values annotation (like serializable) to mark type that can be ordered. Because contractId cannot be ordered.

[bame-da]

What would we return/accept on the JSON API? '[[{"a": 1}, 42], [{"a": 1}, 47]]'?
That would allow users to directly invoke new Map(list_of_pairs), or in case of Text keys Object.fromEntries(list_of_pairs).

[stefanobaghino-da]

The only sensible output for us to emit is an array of pairs as you said, but I would strongly discourage anyone from using both Map (for the reasons stated above) and Object.fromEntries, which calls toString on the keys:

Object.fromEntries([[{"a": 1}, 42], [{"a": 1}, 47]])
// evaluates to { "[object Object]": 47 }, way less then desirable outcome

If the API is consumed from JavaScript users can simply implement an associative array themselves or pull their favorite dictionary/map/associative array implementation from NPM.

[remyhaemmerle-da]

Proposal

We implement Insertion preserving map (called 'Map') where keys are a arbitrary serializable values.

We provides the following builtins (with expected builtins):

• MAP_EMPTY : ∀ k v, 'Map' k v

  Returns the empty map. O(1)

• MAP_INSERT : ∀ k v. k → v → 'Map' k v → 'Map' k v

  Inserts a new key and value in the map. If the key is already
  present in the map, the associated value is replaced with the
  supplied value.If the key is present do not change the key insertion order.
  O(log(n))

• MAP_LOOKUP : ∀ k v. k → 'Map' k v → 'Optional' v

  Lookups the value at a key in the map. O(log(n))

• MAP_DELETE : ∀ k v. k → 'Map' k v → 'Map' k v

  Deletes a key and its value from the map. When the key is not a
  member of the map, the original map is returned. o(log(n))

• MAP_LIST : ∀ k v. 'Map' k v → 'List' ⟨ key: k, value: v ⟩

  Converts to a list of key/value pairs. The output list is sorted in the
  ordered the key have been inserted. O(n * log n)

• MAP_FROM_LIST: ∀ k v. 'List' ⟨ key: k, value: v ⟩ → 'Map' k v

  Converts a list of key/value pairs into a map. The insertion order is
  from left o right. Throws an exception if a key is duplicated. O(n * log n)

• MAP_SIZE : ∀ k v. 'Map' k v → 'Int64'

  Return the number of elements in the map. O(1)

In the ledger and in the ledger API, the map are represented as lists of pairs order as the insertion order.

[cocreature]

added in lf 1.11