[m-rev.] Proposed changes to pqueue.m

[Paul Bone]

On Mon, Nov 18, 2013 at 03:32:25PM +0800, Michael Richter wrote:
> (A colourful version may be obtained here:
> https://mail.google.com/mail/?ui=2&shva=1#label/programming%2Fmercury/141c9c3b88aa059e?compose=1426a13a7f8f05fc
> )
> 
> Summary of proposed changes:
> 
>    1. Add pqueue.is_empty/1 predicate.
>    Rationale: Despite this effectively being the same as testing
>    pqueue.length/1 for 0, it is more immediately clear what is being tested
>    for.  Code using pqueue.is_empty/1 can have its intent more readily
>    discerned.
> 
>    2. Add pqueue.peek/2 predicate.
>    Rationale: There are many cases where it is desirable to know what is at
>    the top of the priority queue without necessarily extracting it from the
>    queue at that point.  This is a frequently-used operation and is supplied
>    in most (all?) of the priority queue implementations I've encountered
>    before.
> 
>    3. Add pqueue.det_peek/2 predicate and pqueue.det_peek/1 function.
>    Rationale: Deterministic version of pqueue.peek/2.  Mirrors provision of
>    pqueue.remove vs. pqueue.det_remove.  A deterministic version is required
>    to make a meaningful function.
> 
>    4. Add pqueue.merge/3 predicate and pqueue.merge/2 function.
>    Rationale: While not as common as peek/2 in other implementations,
>    merging of priority queues is a fairly common task.
> 
> I have done basic testing of all of the above operations, but am unsure
> where to place tests in the current source code hierarchy.  (There appears
> to be no test suite for the existing pqueue functionality.)  The code, as
> far as I can tell, works as expected.  The testing I did can be found at
> http://sprunge.us/cjKe?prolog for inspection and/or expansion.
> 
> Comments and suggestions appreciated.
> 

I took a look on github, your commit message doesn't describe your changes.
It is generally the same as the message used on the mailing lists but
doesn't require the detail of the above notes.


> @@ -40,6 +40,10 @@
>   :- func pqueue.init = pqueue(K, V).
>   :- pred pqueue.init(pqueue(K, V)::out) is det.
> 
>  +    % Test if a priority queue is empty.
>  +    %
>  +:- pred pqueue.is_empty(pqueue(K,V)::in) is semidet.
>  +
>       % Insert a value V with key K into a priority queue
>       % and return the new priority queue.
>       %

yeah, the bikeshed should have a space after the comma and before the "V".
Just to make it conform to the existing style.

>  @@ -47,6 +51,15 @@
>   :- pred pqueue.insert(K::in, V::in, pqueue(K, V)::in, pqueue(K, V)::out)
>       is det.
> 
>  +    % Extract the smallest item from the priority queue without removing
> it.
>  +    % Fails if the priority queue is empty.
>  +    %
>  +:- pred pqueue.peek(pqueue(K, V)::in, V::out) is semidet.
>  +
>  +    % As above, but calls error/1 if the priority queue is empty.
>  +:- func pqueue.det_peek(pqueue(K, V)) = V.
>  +:- pred pqueue.det_peek(pqueue(K, V)::in, V::out) is det.
>  +
>       % Remove the smallest item from the priority queue.
>       % Fails if the priority queue is empty.
>       %

How long are lines in your text editor?  We like to limit lines to 76
columns so taht a diff plus an e-mail reply doesn't cause wrapping.

Why isn't the K returned in the predicate version of peek.  I'd imagine in
some cases it'd be useful.  If a caller doesn't want it then they can pass
the '_' variable.

Comments on declarations should always include an extra line with a %
character.

>  +%---------------------------------------------------------------------------%
>  +
>  +pqueue.det_peek(PQ) = V :-
>  +    pqueue.det_peek(PQ, V).
>  +
>  +pqueue.det_peek(PQ, V) :-
>  +    ( pqueue.peek(PQ, T) ->
>  +        V = T
>  +    ;
>  +        error("pqueue.det_peek/2: empty priority queue")
>  +    ).
>  +

Since this module was written we've introduced 'implementation defined
literals'.  They include $module and $pred and can be used to print the
module and predicate name in errors.  Also see the unexpected predicate in
the require module.  So you can write:

    unexpected($module, $pred, "empty priority queue")

>  +%---------------------------------------------------------------------------%
> +
>   pqueue.insert(!.PQ, K, V) = !:PQ :-
>       pqueue.insert(K, V, !PQ).
>

The style specifies one whitespace line at most between anything.

>  @@ -150,7 +189,7 @@
>           V = V0
>         else
>           error("pqueue.det_remove/4: empty priority queue")
>  -    ).
>  +    ).
>

Does this add or remove whitespace.  It's not written in the style guide but
at least Zoltan and I take measures to avoid trailing whitespace.

>   pqueue.remove(K, V, pqueue(_, K, V, L0, R0), PQ) :-
>       pqueue.remove_2(L0, R0, PQ).
>  @@ -177,6 +216,18 @@
> 
> 
> %---------------------------------------------------------------------------%
> 
>  +pqueue.merge(PQ1, PQ2) = PQ3 :-
>  +    pqueue.merge(PQ1, PQ2, PQ3).
>  +
>  +pqueue.merge(empty,                 PQ2,               PQ2).
>  +pqueue.merge(PQ1 at pqueue(_,_,_,_,_), empty,             PQ1).
>  +pqueue.merge(PQ1 at pqueue(_,_,_,_,_), pqueue(_,K,V,L,R), PQ3) :-
>  +    pqueue.merge(PQ1, L, IPQ1),
>  +    pqueue.merge(IPQ1, R, IPQ2),
>  +    pqueue.insert(K, V, IPQ2, PQ3).
>  +

I suggest for the arguments using letters, A and B. and numbers for the
version of something.

Note that your merge is faster if the queue in the second argument is
smaller.  This is not bad, you have to pick one.  You should note this in
the comment on the declaration for merge.

However, if you adjust your code so that it's faster if the first argument
is shorter then it will also be easier to write the definition using state
variable notation.

merge(pqueue(_, K, V, L, R), !PQ) :-
    merge(L, !PQ),
    merge(R, !PQ),
    insert(K, V, !PQ).

It's possible to still do this using the @ notation in the head.

merge(pqueue(_, K, V, L, R), !.PQ at pqueue(_, _, _, _, _), !:PQ) :-
    ...


> P.S. The bike shed should be cerulean.  ;-)

Red goes faster.

-- 
Paul Bone
http://www.bone.id.au