[m-dev.] multi_map and one_or_more

[Julien Fischer]

Hi Zoltan,

On Sun, 29 Dec 2019, Zoltan Somogyi wrote:

> I am currently working on a big change, which amongst other things
> contains a whole bunch of operations on multi_maps.

Does your change add additional operations on multi_maps, or just use
them?

> 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 guess in the absence of an abstraction barrier in the multi_map module
we cannot just make the mode of arguments returning a list of values be
out(non_empty_list).

> 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.

The major downside being that it will further inflate the already large
interface of the list module.

>  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.

A third option would be to make the one_or_more module a submodule of
the list module.

My preference is for the operations on one_or_mores to go into a
separate module (be it a submodule or not).

> - 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.

I prefer one_or_more_map.  (Actually, what I prefer is that the name
of the one_or_more module and the associated map type align.)

> - 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?

Another alternative would be to "fix" the existing multi_map module.  Of
course, that's likely to break a good deal of existing code.  Still,
perhaps we ought to move things in that direction.

Julien.