[m-dev.] multi_map and one_or_more

[Zoltan Somogyi]

I am currently working on a big change, which amongst other things
contains a whole bunch of operations on multi_maps. These map
a key to a list of values, but these lists are never empty, because if
e.g. a deletion makes a list of values empty, we delete it alongs with its key.
This makes writing code that operates on multi_maps somewhat annoying:
you have to write code to handle empty lists (usually by throwing an exception)
that you know won't appear in practice.

One possible solution is to use a version of the multi_map type which maps
each key not to a list(V), but to one_or_more(V). A value of the one_or_more type
is a list that cannot be empty. It is defined in list.m, and has been for about
two and a half years, but it has only a couple of operations on it; even basic
operations such as length and append are missing.

I would like to do several things in relation to this.

- First, I would like to provide a full set of operations on one_or_mores.
  If an operation exists for lists,  then add it for one one_or_mores, unless
  it does not make sense for them. (An example is a test for emptyness.)

- Second, I would like to add a new module to the standard library that
   is a version of multi_map but with the range type being one-or-more.

I have some questions for you guys about this.

- Should the operations on one_or_mores go into list.m, or into a new module?
  I can see arguments on both sides, but favour the former slightly, for two
  reasons: because it would make it much harder to forget to add an
  one_or_more version of a newly added operation on lists, and because
  it would continually remind people using the module's documentation
  about the availability of the one_or_more version.

  However, I would be ok with putting the new operations into a new module.
  The new module should also contain the one_or_more type itself, and its
  existing operations, so this wouldn't be backward compatible with older ROTDs,
  though it would be compatible with the last release. The obvious module name
  is one_or_more.m.

- With the same-module approach, what naming scheme should we follow
  to differentiate operations on one_or_mores from operations on lists?
  The possibilities include "one_or_more_" and the shorter but obviously
  less expressive version "oom_" as prefixes. (If the one_or_more operations
  are in their own module, then the module name is the obvious disambigation.)

- What should the one_or_more equivalent of multi_map be named?
  I think we need to choose either a short name or an expressive name;
  I don't there is a name that is both. I lean slightly towards oom_map,
  but one_or_more_map and multi_map_oom are also possibilities.

- Should the new version of multi_map have its own module? Here the
  tradeoffs are different, since multi_map is already a mutatis-mutandis
  copy of map.m. This allows multi_map.m to use the same predicate
  and function names as map.m, and this should also be true for the new
  (e.g.) oom_map.m.

Opinions?

Zoltan.