Is the documentation of library(heaps) confusing?

Help! PlDoc
1

Maybe it is just me. I think the underlying reason is the generous use of the forward slash in the text. For example, we find the following pairs (with a bit of context, because I am not even sure how should this parse, if we would strictly follow the author’s intention)

library(heaps): heaps/priority queues

a central element of algorithms such as best-first/A* search and Kruskal’s minimum-spanning-tree algorithm

meaning that items are retrieved in ascending order of key/priority

Although the data items can be arbitrary Prolog data, keys/priorities must be ordered by @=</2

This all sounds okey until the predicate definitions, which look like this:

add_to_heap(+Heap0, +Priority, ?Key, -Heap)

Adds Key with priority Priority to Heap0, constructing a new heap in Heap.

Here is an attempt to demonstrate that the Priority from the definition above is used; but the Key is not. I used X and Y in the queries so that I don’t have to name it something confusing. The docs claim:

min_of_heap(+Heap, ?Priority, ?Key)

Unifies Key with the minimum-priority element of Heap and Priority with its priority value. Complexity: constant.

?- empty_heap(_H0),
   add_to_heap(_H0, 1, foo, _H1),
   add_to_heap(_H1, 1, bar, _H2),
   min_of_heap(_H2, X, Y).
X = 1,
Y = bar.

?- empty_heap(_H0),
   add_to_heap(_H0, 1, bar, _H1), % same elements
   add_to_heap(_H1, 1, foo, _H2), % but inserted in different order
   min_of_heap(_H2, X, Y).
X = 1,
Y = foo.

This is also easily seen in the source code.

The use of “key/priority” in the docs, together with the naming of the arguments, is in my opinion inconsistent. I suspect the original author meant to use “key/priority” when documenting the second argument from the definition of add_to_heap/4 above, and use “data item” for the third argument.

Am I tripping? Is this a bit confused or is it me? I can make a PR if it turns out that other are also confused.

PS: the docs are confusing at first but the library itself is quite useful!

2

It seems there are some opportunities for improvement :slight_smile: Just file a PR.

3

Great, will do.

This is my general proposal:

  • Explain that the Key is the Priority and the Priority is the Key
  • consistently use “Priority” in the predicate documentation and get rid of “Key”
  • Call the other thing “Data item” or just “Value”.

Open to other suggestions.

1 Like
4

I too find the phrasing in the docs quite confusing and even incorrect at places. That said, I’d propose that what is now called Key should rather be called Item (in fact I’d propose to also change “entry”/“entries” to “item”/“items” in all places – anyway, this is the “data”): then it is also easier to explain that the “priority” is equivalently a key into the data.

Maybe it should also be made more explicit that the priority itself is an arbitrary Prolog term (if it is, I haven’t double-checked), where prioritisation is by the order of terms. In fact, there is not even prescription that the key/priority (in the sense I have now fixed, so distinct from the item/data), has to be ground.

5

At the moment the documentation already says:

Although the data items can be arbitrary Prolog data, keys/priorities must be ordered by @=</2. Be careful when using variables as keys, since binding them in between heap operations may change the ordering.

This is strong enough. You can use variables (there might be valid use cases) but you must remember that binding them will change their ordering in respect to other priorities/keys.

Yes, this is roughly my plan, as described in my previous post. It is just not clear which Key mentions you mean. I am aiming to remove completely the use of the argument name Key in predicate declarations and most probably rename it to Value. So, it will be Priority - Value but maybe Priority - Item also works. It might in fact make the re-write smaller.

6

Do not forget that Priority does not need to be a number, but the total ordering implied by the Prolog standard order of terms (don’t mention cyclic terms :slight_smile: ) In that sense Key-Value could do fine as well?

7

Yes, of course. In this case the intro will have to explain that the key is the priority (and the priority the key…). I will go with this then.

1 Like
8

Hmm, maybe after the warning on non-ground keys, I’d rather mention (even just quickly with a link) that cyclic terms are not supported, since “the standard order is not well defined on rational trees”, as stated in the section Standard Order of Terms.

FWIW, I am fine with that.