Make Map length run in O(1) instead of O(n)

Hi OCaml developers team 👋🏻

I want to propose a change to the OCaml standard library.

Please, let me know if it should be done differently!

What?

Currently, the implementation of Map.cardinal (a function to return the size of the Map) takes linear time:

https://github.com/ocaml/ocaml/blob/b72d99b3dbf3a593f9ff38acc4a375a2e2fd8749/stdlib/map.ml#L493-L495

I propose to

• Change the implementation to run in constant time, independent of the tree size
• Document that the implementation runs in constant time

Why?

It's a common expectation for a dictionary-like data structure to return its own size in a constant time.

How?

The current linear-time behaviour is a consequence of the fact that a tree node (internal Map representation) stores height instead of size.

https://github.com/ocaml/ocaml/blob/b72d99b3dbf3a593f9ff38acc4a375a2e2fd8749/stdlib/map.ml#L77-L79

I propose to change the internals and store size (and change all the relevant functions). I expect the existing test suite to be exhaustive enough to make sure that there're no regressions after this change. But, obviously, new tests are always welcome!

There's a prior art on how to rebalance a binary search tree when a node stores the size. One can refer to the Haskell implementation:

• https://github.com/haskell/containers/blob/f5d0b13251291c3bd1ae396f3e6c8b0b9eaf58b0/containers/src/Data/Map/Internal.hs#L4162-L4208

Impact

This should be a backward-compatible change, impacting only internals.

Let me know what you think!

Start with stdlib/map.ml, especially the internal tree-node representation and the Map.cardinal implementation linked in the issue. Trace the balancing and update functions that depend on the stored height, then review the existing Map tests. Done means Map.cardinal is constant-time, the relevant internals remain correct, and the complexity is documented.