[m-users.] Question about map internal representation for repeated values on different keys

[Zoltan Somogyi]

2021-11-30 09:36 GMT+11:00 "Sean Charles (emacstheviking)" <objitsu at gmail.com>:
> What does map(string, string) do if I insert many keys that have the same value, does it re-share that string value?

No, it does not. What you are talking about is hash-consing, https://en.wikipedia.org/wiki/Hash_consing,
and Mercury has no built-in mechanism for doing it.

However, that does not mean it cannot be done, and in fact it is easy to do: you just
need to implement the hash-consing yourself. This is trivially done using a canonicalization map,
which in this case would be a map from strings to strings, which would map any string to
a "canonical instance" of that string. The code for that would be as simple as

:- pred canonicalize(T::in, T::out, map(T, T)::in, map(T, T)::out) is det.

canonicalize(X, CanonX, !Map) :-
  ( if map.search(!.Map, X, CanonXPrime) then
    CanonX = CanonXPrime
  else
    CanonX = X,
     map.det_insert(X, CanonX, !Map)
  ).

While this code is simple, it does have a performance cost in both time and space, which is why
this is not done by default.

Zoltan.