Why does DA.Map use Ord instances?

I am currently moving a code-base away from using the deprecated DA.Next.Map, and replacing their uses with the new-and-improved DA.Map. What’s great about this change is that MapKey instances are no longer required for conversion from and to a textual representations of the map’s key.

However, I noticed that all functions that access elements in the Map require an Ord instance for the key now. This is not an issue, since Ord instance can easily be derived (unlike MapKey).

I am curious however, what is the technical reason that DA.Map functions require an Ord instance for the map keys?

As things go, I discovered a high-level explanation to my own question in the source code virtually as I was formulating it.

Map k v internally uses the built-in order for the type k.
This means that keys that contain functions are not comparable
and will result in runtime errors. To prevent this, the Ord k
instance is required for most map operations. It is recommended to
only use Map k v for key types that have an Ord k instance
that is derived automatically using deriving:

This still leaves me curious as to why this Map implementation needs an order of the keys, internally.

digital-asset/daml/blob/ff28059c635a71565b47ae80f121f8e3f923a23b/compiler/damlc/daml-stdlib-src/DA/Map.daml#L28-L45

      

          
-- `Map k v` internally uses the built-in order for the type `k`.
          
-- This means that keys that contain functions are not comparable
          
-- and will result in runtime errors. To prevent this, the `Ord k`
          
-- instance is required for most map operations. It is recommended to
          
-- only use `Map k v` for key types that have an `Ord k` instance
          
-- that is derived automatically using `deriving`:
          
--
          
-- ```
          
-- data K = ...
          
--   deriving (Eq, Ord)
          
-- ```
          
--
          
-- This includes all built-in types that aren't function types, such as
          
-- `Int`, `Text`, `Bool`, `(a, b)` assuming `a` and `b` have default
          
-- `Ord` instances, `Optional t` and `[t]` assuming `t` has a
          
-- default `Ord` instance, `Map k v` assuming `k` and `v` have
          
-- default `Ord` instances, and `Set k` assuming `k` has a
          
-- default `Ord` instance.
      
    

I believe it’s simply that GenMap in Daml is implemented as a Tree Map in the background, which needs an ordering on Daml values.

Was also discussed here:

Record as a Key Questions

So, are you saying that the ordering determines the keys used for hashing, in answer to OP? I expect I’ve misunderstood this, but if not, isn’t this a pretty hefty constraint? Is it not enough to have some sort of a Hashable typeclass? Would this mean that in OP’s example, you’d need to write an instance Ord that then picks which particular field to order on - i.e. using deriving Ord in this particular case wouldn’t work? Btw. is Ord a total order?

There’s two reasons, as far as I know.

The first reason is, as @bernhard said, that DA.Map internally uses a data structure that expects key-value pairs to be stored in order, by key. This enables faster lookup and (non-destructive) insert operations. So the keys need to have some notion of “order” in order to make this data structure work (pun intended).

The second reason is that by requiring an order on keys, we can also store and transmit the map in order (e.g. over the ledger API). Because the keys are always in order, there’s no hidden dependence on the way that keys were presented originally. For example,

fromList [("a", 10), ("b", 20)]

and

fromList [("b", 20), ("a", 10)]

have the same map value, because they have the same set of key-value pairs. This sort of normalization leads to code that is easier to test and to predict.

An older version of DA.Map only required a notion of “equality” on keys, but it introduced a dependence on the order that keys were presented. So the two expressions above actually gave different maps, even though these two maps would otherwise behave the same. So to eliminate this source of unexpected behavior, we strengthened the requirement that keys should be orderable.

So, that’s why we need keys that can be ordered in general.

The documentation you found explains why the Ord constraint is required for these functions. Like the documentation says, the actual key order that is used in the Daml interpreter is a built-in order. This order agrees with the default Ord instance that you’d get from “deriving Ord”. This use of a built-in order ends up being much more efficient than using the Ord instance directly. So in the end, the Ord constraint is really only required for type safety!