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

[Julien Fischer]

Hi Peter,

On Mon, 3 Mar 2014, Peter Wang wrote:

>>> 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.)
>
> If you insist, but the option is there for the future.

Sure, but if / when we take that option it should be as part of library wide
change, not individual modules.

...

>>> 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.
>>
>
> * We have added a module for discrete interval encoding trees,
>  which are a highly efficient set implementation for fat sets.

That's fine.

>> Why have you suddenly changed the naming scheme you were using for
>> accumulator arguments?
>
> I was bouncing around between U/V/W, A/B/C and Acc1/2/3.
> I will go with A/B/C for all for them.
>
>>> +%-----------------------------------------------------------------------------%
>>> +
>>> +:- 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.
>
> I considered it but the result for take_min, etc. becomes two arguments
> so it's not completely trivial.  It can be done later, with benchmarking.

Ok.  Add a note to this effect above the interval type.

>>> +%-----------------------------------------------------------------------------%
>>> +
>>> +:- 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.
>
> Are you sure?  I think enum should stay minimal.

It's an obvious utility predicate that the enum module ought to provide.
(I've certainly wanted it in the past when I used the enum type class
and the fact that you've required here suggests that it is something the
enum modue should provide.)

Cheers,
Julien.