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

[Michael Richter]

On 18 November 2013 18:19, Paul Bone <paul at bone.id.au> wrote:

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

I haven't yet made the pull request.  This is a pre-PR glimpse.  When I
make the formal pull request it will be exhaustively documented, trust me.
 ;)


>
>
> >  +:- pred pqueue.is_empty(pqueue(K,V)::in) is semidet.
>
> yeah, the bikeshed should have a space after the comma and before the "V".
> Just to make it conform to the existing style.
>

Fair cop.  That was a typo I didn't catch in my final review of the code.
 Fixed.


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

Ah.  I have my right column marked at 80.  I'll adjust to 76 for Mercury
code.  Fixed for my additions, but I've noted more than a few lines in
old code that exceed this.  Shall I fix them as well?


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

Hmmm...  You want different behaviour in the predicate and the function?
 It's doable, but to me a bit weird.  Done.


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

Another typo, result of a last-second editing change.  Fixed.


>
> >  +        error("pqueue.det_peek/2: empty priority queue")
>
> So you can write:
>
>     unexpected($module, $pred, "empty priority queue")
>

Fixed.


>
> >
>  +%---------------------------------------------------------------------------%
> > +
> >   pqueue.insert(!.PQ, K, V) = !:PQ :-
> >       pqueue.insert(K, V, !PQ).
> >
>
> The style specifies one whitespace line at most between anything.
>

I'm not sure I understand.  That's old code.  And I only see one line of
whitespace anyway.


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

It removes a trailing whitespace that was in the old code.  My editor does
that for me automatically unless I explicitly turn off the behaviour.


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

OK, will do.


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

I think this eliminates the need for the caller to worry about it?:

pqueue.merge(A, B, C) :-
  ( pqueue.length(A) =< pqueue.length(B) ->
      pqueue.merge2(A, B, C)
  ;
      pqueue.merge2(B, A, C) ).

:- pred pqueue.merge2(pqueue(K, V)::in, pqueue(K, V)::in, pqueue(K, V)::out)
    is det.

pqueue.merge2(empty,                   B,     B).
pqueue.merge2(A at pqueue(_, K, V, L, R), empty, A).
pqueue.merge2(pqueue(_, K, V, L, R),   !.PQ at pqueue(_, _, _, _, _), !:PQ) :-
    pqueue.merge2(L, !PQ),
    pqueue.merge2(R, !PQ),
    pqueue.insert(K, V, !PQ).


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

Going faster to the wrong place is not what I'm aiming for.  Correctness
before speed.

-- 
"Perhaps people don't believe this, but throughout all of the discussions
of entering China our focus has really been what's best for the Chinese
people. It's not been about our revenue or profit or whatnot."
--Sergey Brin, demonstrating the emptiness of the "don't be evil" mantra.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20131118/203db258/attachment.html>