[m-rev.] for review: discrete interval encoding tree

[Julien Fischer]

Hi Peter,

On Fri, 28 Feb 2014, Peter Wang wrote:

> I have tested by bootchecking the compiler with diet and the test_bitset
> module.  Any other ideas?

None spring to mind.

> Add discrete interval encoding tree module to the standard library.
>
> Discrete Interval Encoding Trees are a highly efficient set
> implementation for fat sets.
>
> This implementation is largely a translation of Caml Diet.
> I have permission from the authors to license this version either
> under the LGPL, or LGPL/BSD dual license.  I choose the latter.

I would prefer it if the licensing of library modules were consistent
across the entire library, so for now I suggest you pick again!
(Also, (1) the Mercury system does not currently include the text of
the BSD license and (2) which BSD license? -- there are several
variants.)

> library/diet.m:
>    Add the new module.
>
> library/library.m:
>    Include the new module in the library.
>
> NEWS:
>    Announce the above addition.
>
>
> diff --git a/NEWS b/NEWS
> index f35b152..4f1b43d 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -7,6 +7,8 @@ Changes to the Mercury standard library:
>   io module.  These behave like the print and write predicates, but also
>   write a terminating newline character.
>
> +* We have added a discrete interval encoding tree (diet) module.

A little more detail here would be welcome.

> diff --git a/library/diet.m b/library/diet.m
> new file mode 100644
> index 0000000..cf70975
> --- /dev/null
> +++ b/library/diet.m
> @@ -0,0 +1,1746 @@
> +%-----------------------------------------------------------------------------%
> +% vim: ts=4 sw=4 et ft=mercury
> +%-----------------------------------------------------------------------------%
> +% Copyright (C) 2014 The Mercury team.
> +% Copyright (C) 2012-2014 YesLogic Pty. Ltd.
> +% This file may only be copied under the terms of the GNU Library General
> +% Public License - see the file COPYING.LIB in the Mercury distribution,
> +% or under the terms of the BSD license.
> +%-----------------------------------------------------------------------------%
> +%
> +% File: diet.m.
> +% Author: wangp.
> +% Stability: medium.
> +%
> +% Discrete Interval Encoding Trees are a highly efficient set implementation
> +% for fat sets, i.e. densely populated sets over a discrete linear order.
> +%
> +% M. Erwig: Diets for Fat Sets
> +% Journal of Functional Programming, Vol. 8, No. 6, pp. 627-632
> +%
> +% O. Friedmann, M. Lange: More on Balanced Diets
> +% Journal of Functional Programming, volume 21, issue 02, pp. 135-157

...

> +:- pred foldl4(pred(T, Acc1, Acc1, Acc2, Acc2, Acc3, Acc3, Acc4, Acc4),
> +    diet(T), Acc1, Acc1, Acc2, Acc2, Acc3, Acc3, Acc4, Acc4) <= enum(T).
> +:- mode foldl4(pred(in, in, out, in, out, in, out, in, out) is det,
> +    in, in, out, in, out, in, out, in, out) is det.
> +:- mode foldl4(pred(in, in, out, in, out, in, out, mdi, muo) is det,
> +    in, in, out, in, out, in, out, mdi, muo) is det.
> +:- mode foldl4(pred(in, in, out, in, out, in, out, di, uo) is det,
> +    in, in, out, in, out, in, out, di, uo) is det.
> +:- mode foldl4(pred(in, in, out, in, out, in, out, in, out) is semidet,
> +    in, in, out, in, out, in, out, in, out) is semidet.
> +:- mode foldl4(pred(in, in, out, in, out, in, out, mdi, muo) is semidet,
> +    in, in, out, in, out, in, out, mdi, muo) is semidet.
> +:- mode foldl4(pred(in, in, out, in, out, in, out, di, uo) is semidet,
> +    in, in, out, in, out, in, out, di, uo) is semidet.
> +
> +:- pred foldl5(pred(T, A, A, B, B, C, C, D, D, E, E), diet(T),
> +    A, A, B, B, C, C, D, D, E, E) <= enum(T).

Why have you suddenly changed the naming scheme you were using for
accumulator arguments?

> +:- mode foldl5(
> +    pred(in, in, out, in, out, in, out, in, out, in, out) is det,
> +    in, in, out, in, out, in, out, in, out, in, out) is det.
> +:- mode foldl5(
> +    pred(in, in, out, in, out, in, out, in, out, mdi, muo) is det,
> +    in, in, out, in, out, in, out, in, out, mdi, muo) is det.
> +:- mode foldl5(
> +    pred(in, in, out, in, out, in, out, in, out, di, uo) is det,
> +    in, in, out, in, out, in, out, in, out, di, uo) is det.
> +:- mode foldl5(
> +    pred(in, in, out, in, out, in, out, in, out, in, out) is semidet,
> +    in, in, out, in, out, in, out, in, out, in, out) is semidet.
> +:- mode foldl5(
> +    pred(in, in, out, in, out, in, out, in, out, mdi, muo) is semidet,
> +    in, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
> +:- mode foldl5(
> +    pred(in, in, out, in, out, in, out, in, out, di, uo) is semidet,
> +    in, in, out, in, out, in, out, in, out, di, uo) is semidet.

...

> +:- implementation.
> +
> +% This file is, in large parts, a translation of Caml Diet.
> +% https://github.com/tcsprojects/camldiets
> +
> +/***********************************************************
> + *                      CAML DIET                          *
> + *                                                         *
> + *                  Copyright (c) 2010                     *
> + *           Distributed under the BSD license.            *
> + *                                                         *
> + *                   Oliver Friedmann                      *
> + *              Oliver.Friedmann at gmail.com                 *
> + *                 University of Munich                    *
> + *                                                         *
> + *                    Martin Lange                         *
> + *                Martin.Lange at gmail.com                   *
> + *                 University of Kassel                    *
> + *                                                         *
> + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
> + *                                                         *
> + * The code for handling the AVL trees is borrowed from    *
> + * the Objective Caml Standard Library Set module.         *
> + *                                                         *
> + * (c) Xavier Leroy, projet Cristal, INRIA Rocquencourt    *
> + *                                                         *
> + ***********************************************************/
> +
> +:- import_module bool.
> +:- import_module int.
> +:- import_module maybe.
> +:- import_module pair.
> +:- import_module require.
> +:- import_module string.
> +
> +%-----------------------------------------------------------------------------%
> +
> +:- type diet(T)
> +    --->    empty
> +    ;       node(
> +                interval    :: interval,
> +                node_height :: int,
> +                left        :: diet(T),
> +                right       :: diet(T)
> +            ).
> +
> +:- type interval == {int, int}. % inclusive

Rather than having a separate type for an interval, I think it would be
better to have the two integer fields directly in node constructor.  The
extra level of indirection doesn't appear to serve much purpose.

> +:- inst node
> +    --->    node(ground, ground, ground, ground).
> +
> +%-----------------------------------------------------------------------------%

...

> +%-----------------------------------------------------------------------------%
> +
> +:- func det_from_int(int) = T <= enum(T).
> +
> +det_from_int(I) = X :-
> +    ( X0 = from_int(I) ->
> +        X = X0
> +    ;
> +        unexpected($module, $pred, "from_int failed")
> +    ).

Move this to the enum module.

...

> +%-----------------------------------------------------------------------------%
> +% vim: ft=mercury ts=4 sts=4 sw=4 et
> diff --git a/library/library.m b/library/library.m
> index 7e1f0ab..baabd7e 100644
> --- a/library/library.m
> +++ b/library/library.m
> @@ -63,6 +63,7 @@
> :- import_module cord.
> :- import_module counter.
> :- import_module deconstruct.
> +:- import_module diet.
> :- import_module digraph.
> :- import_module dir.
> :- import_module enum.

You also need to update the mercury_std_library_module/1 predicate
further down in this module.

The change looks okay otherwise.

Cheers,
Julien.