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

Julien Fischer jfischer at opturion.com
Mon Mar 3 15:35:57 AEDT 2014


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.



More information about the reviews mailing list