bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

[Drew Adams]

Subject line says it all.

I had never heard of `add-to-ordered-list' before coming across this
user question:

https://emacs.stackexchange.com/q/62520/105

Why hard-code the hash-table :test predicate?  The fact of using a hash
table should be only an internal, implementation thing.  But the
comparison behavior for the ordering is a user thing.

Please consider adding an optional arg TEST-PREDICATE, which will be
passed to the hash table (and which will default to `eq').

In GNU Emacs 26.3 (build 1, x86_64-w64-mingw32)
 of 2019-08-29
Repository revision: 96dd0196c28bc36779584e47fffcca433c9309cd
Windowing system distributor `Microsoft Corp.', version 10.0.18362
Configured using:
 `configure --without-dbus --host=x86_64-w64-mingw32
 --without-compress-install 'CFLAGS=-O2 -static -g3''

bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

[Lars Ingebrigtsen]

Drew Adams <drew.adams@oracle.com> writes:

> Please consider adding an optional arg TEST-PREDICATE, which will be
> passed to the hash table (and which will default to `eq').

Since the ordering is hard-coded to `<', allowing the things being
compared are presumably all numbers, so allowing specifying the
comparison function doesn't make much sense.

However, using `eq' for numbers doesn't make much sense, either -- `eql'
would be better.  Looking at the in-tree usages, switching to `eql'
shouldn't make much difference, so I've done the daring thing and
switched to `eql'.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

[Drew Adams]

> > Please consider adding an optional arg TEST-PREDICATE, which will be
> > passed to the hash table (and which will default to `eq').
> 
> Since the ordering is hard-coded to `<', allowing the things being
> compared are presumably all numbers, so allowing specifying the
> comparison function doesn't make much sense.
> 
> However, using `eq' for numbers doesn't make much sense, either -- `eql'
> would be better.  Looking at the in-tree usages, switching to `eql'
> shouldn't make much difference, so I've done the daring thing and
> switched to `eql'.

I don't understand.  One of us is confused, I think.

What does the :test predicate for the hash table have to do with the order of elements in the list?

This is about letting you specify how the hash table is configured, by passing a TEST predicate arg to `add-to-ordered-list', which is just passed to the code implementing the hash table.  The purpose of the hash table's :test predicate is only to determine whether a hash-table item is already present, and if so, get its value using the item as key.

The code is currently hard-coded to use `eq' for :test, which works fine for symbol hash-table data, hence for symbol elements of the list.  But it doesn't work fine for, say, string list elements.  (And it wouldn't work well for numeric list elements, for which a :test of `eql' would be better.)

But in all cases, :test is about comparing the list elements, not their associated "order" in the list.

The things being compared are not numbers, they are the list elements.  The hash table is not used in any way for ordering the list.  The hash table hashes list elements (which can be anything) as the hash-table keys, and the order of those elements in the list (which are numeric) as the "order" values of the list elements.  When an entry is added to a hash table, it's the key, not the value, that's compared against other keys, using :test.

(elisp) `Creating Hash' says, for example:

':test TEST'
  This specifies the method of key lookup for this hash table.
  The default is 'eql'; 'eq' and 'equal' are other alternatives:

  'eql'
       Keys which are numbers are the same if they are 'equal',
       that is, if they are equal in value and either both are
       integers or both are floating point; otherwise, two
       distinct objects are never the same.

  'eq'
       Any two distinct Lisp objects are different as keys.

  'equal'
       Two Lisp objects are the same, as keys, if they are equal
       according to 'equal'.

In my understanding, :test is all about comparing hash-table keys, not values.  The hash table implements an association of ordered-list elements (the keys) with their orders in the list (the values).

This is about letting any kind of list elements to be in an "ordered list".  In the case of the example question, the list elements would be strings.  (Their orders in the list would be numbers.)  For string elements a :test of `equal' (or even `string=') makes sense and `eq' makes no sense.

bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

[Lars Ingebrigtsen]

Drew Adams <drew.adams@oracle.com> writes:

> I don't understand.  One of us is confused, I think.

Yeah, that was me.  I totally misread what the function is doing.  I'll
revert the patch and add the predicate function like you suggested.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

[Drew Adams]

> > I don't understand.  One of us is confused, I think.
> 
> Yeah, that was me.  I totally misread what the function is doing.  I'll
> revert the patch and add the predicate function like you suggested.

Thanks.

I know the feeling.  And when I looked at it
again, after your mail, I began to wonder...

And double thanks for adding the optional TEST-PRED arg.

bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

[Drew Adams]

Let me know if you want a separate bug for the following.

The doc for this function does not, I think, convey what it's really about.  And part of the reason for that, I guess, is that it hasn't (until now) allowed for list-element comparisons other than `eq'.

What this function is really about, I think, is this: a list with unique elements - no duplicates.

With your fix of this bug, "unique" will be defined by the new TEST arg (predicate).  Until then, "unique" is defined by `eq'.

This is important, as it means that this function is not only for adding an element at a given list position.  It's about having a list of unique elements, and being able to not only add (or remove) but also _change the position_ of an existing element.

That's not obvious from the current doc, but it seems to be the raison d'etre for this.

You have a list of 314,159 elements, and you want to change the value of the 2,067th element?  Use this function to do that.

Think of your Netflix DVD queue.  You can add or remove elements, of course.  But more importantly, you can move the DVD that's currently at position 147 to position 3.

It's vital to understanding this function that users know that the list has no duplicates.  Otherwise, the repositioning makes no sense.  And "no duplicates" depends on the meaning of "unique", i.e., the TEST-predicate optional arg or `eq' by default.

bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

[Lars Ingebrigtsen]

Drew Adams <drew.adams@oracle.com> writes:

> What this function is really about, I think, is this: a list with
> unique elements - no duplicates.
>
> With your fix of this bug, "unique" will be defined by the new TEST
> arg (predicate).  Until then, "unique" is defined by `eq'.

My confusion here was due to not reading the code closely enough,
and because it's implemented how you'd think, it's just ... confusing.

> (defun add-to-ordered-list (list-var element &optional order)
>   "Add ELEMENT to the value of LIST-VAR if it isn't there yet.
> The test for presence of ELEMENT is done with `eq'.

> The resulting list is reordered so that the elements are in the
> order given by each element's numeric list order.  Elements
> without a numeric list order are placed at the end of the list.

What on earth is a "numeric list order" of an object?  This seems to
imply that ELEMENT should be a number.

> If the third optional argument ORDER is a number (integer or
> float), set the element's list order to the given value.  If
> ORDER is nil or omitted, do not change the numeric order of
> ELEMENT.  If ORDER has any other value, remove the numeric order
> of ELEMENT if it has one.

The actual ORDER bit is optional, which makes no sense for a function
that's allegedly about an ordered list.

    > (when order
    >   (puthash element (and (numberp order) order) ordering))

The hash table is only used to store this ORDER, and ORDER is silently
discarded unless it's a number.

    > (unless (memq element (symbol-value list-var))
    >   (set list-var (cons element (symbol-value list-var))))

This is the actual member check -- the hash table isn't used to keep
track of what's already in the list or not.

    > (set list-var (sort (symbol-value list-var)

The list is re-sorted upon every call, which is maximally inefficient.

			> (lambda (a b)
			>   (let ((oa (gethash a ordering))
			> 	(ob (gethash b ordering)))
			>     (if (and oa ob)
			> 	(< oa ob)
			>       oa)))))))

Finally, we sort based on the values stashed in the hash table, and the
ones with a (numerical) order gets sorted first.

It's a strange, maximally inefficient function.  I'll fix it up a bit
and add the test-function.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

[Lars Ingebrigtsen]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> It's a strange, maximally inefficient function.  I'll fix it up a bit
> and add the test-function.

The complication is that test-function has to be the same in all calls
(or not given at all in subsequent calls).

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

[Drew Adams]

> > It's a strange, maximally inefficient function.  I'll fix it up a bit
> > and add the test-function.
> 
> The complication is that test-function has to be the same in all calls
> (or not given at all in subsequent calls).

I don't think so.  It just needs to be applicable
for the particular kind(s) of list elements you
have.

I think you can use different TEST functions, but
I'm not sure why you'd do that.

But you raise a good point.  Because TEST needs to
be used to test list membership, as well as to be
the hash-table :test, unless the default value for
it suffices for testing list membership you need
to provide it whenever you call the function.

That's not good, and it's maybe one reason the
design hard-coded `eq'.

OK, I see now that there's `hash-table-test', which
returns the :test defined for the hash table.  We
should use that, not TEST, each time for checking
list membership, I think.

IOW, not this:

(unless (cl-member element (symbol-value list-var) :test TEST)
  (set list-var  (cons element (symbol-value list-var))))

but this:

(unless (cl-member element (symbol-value list-var)
                   :test (hash-table-test ordering))
  (set list-var  (cons element (symbol-value list-var))))

bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

[Drew Adams]

I just now noticed the doc for this function in (elisp)
`List Variables'.  Should have looked in that manual
sooner.  (I didn't expect it to be documented there;
never heard of this function before.)

That description confirms what I've said, I think.

Dunno why this function was added (and documented in
the manual, which is usually done only for important
functions).  Dunno if anyone uses it.
___

One thing that I've said isn't quite correct: the
list _can_ have duplicates for elements that are
added with no ORDER.  IOW, I should have said that
elements that are recorded in the hash table can't
be duplicated (because a hash table has unique keys).
But other elements can be duplicated.
___

If we're adding a TEST optional arg, to accommodate
hash-table and list membership checks, maybe we should
allow callers to specify a :key arg as well.  In that
case, instead of adding optional TEST and KEY args we
would presumably want to use `cl-defun' and allow
keyword args :test and :key.

What do you think?  I realize that this now is about
redesigning this function a bit, and we (I, at least)
have little knowledge of why this function was added.

Still, it seems like its basic purpose would benefit
from letting you use different :key as well as :test.
___

Until I discovered that the function was in the manual
I was wondering, since this function seems so messed up
and unclear, if we should just remove it.  Now I think
we should maybe just fix it by using `cl-defun'.

Another thing (maybe even the main thing) that's
confusing about this function is its name.

This function is about a special kind of ordering:
the "order" you specify for an element is more of a
kind of "score".  It doesn't directly reflect
(correspond to) the list position of an element.
And the function is not so much about adding an
an element to a list as it is recording the score of
an element (a score used to determine its order in the
list).  And besides the function being able to record
such a score for an element, it can also _remove_ its
score.  (So it's not even necessarily about "adding"
a score.
___

Googling for this function (which is how I accidentally
came across it in the Elisp manual), I see that others
have been confused by its behavior and (IIUC) its aim.
E.g.:

https://stackoverflow.com/q/22440069/729907

I've added an answer to that question here, to clarify
some of its confusion.

https://stackoverflow.com/a/65523104/729907

And I've added a clarification answer to the emacs.SE
question (which provoked this bug report), as well:

https://emacs.stackexchange.com/a/62542/105

bug#45539: 26.3; `add-to-ordered-list': Add optional arg for :test predicate for hash table

[Drew Adams]

> > What this function is really about, I think, is this: a list with
> > unique elements - no duplicates.
> >
> > With your fix of this bug, "unique" will be defined by the new TEST
> > arg (predicate).  Until then, "unique" is defined by `eq'.
> 
> What on earth is a "numeric list order" of an object?  This seems to
> imply that ELEMENT should be a number.

No.  ELEMENT need not be a number.  In face, as currently
defined it needs to be something identified by `eq' (so
NOT a number, till we add an optional TEST arg).  It is
the order of ELEMENT that can (optionally) be specified
as a number.

I'm learning this too.  I never heard of this function before.

My understanding is as I said in my previous mail.  This
is about a particular kind of list: one that has no
duplicates.  (Well, you can force it to have dups by
add elements other than using `add-to-ordered-list'.)

And one where you can specify a given list order to any
of the elements.  This specified order is a number, and
elements with lower orders appear in the list before
those with higher orders.

Elements of the list can also have no specified order.
If the order of a given list element isn't specified
then its order isn't guaranteed (not controlled by you),
except that it's sorted after any elements that have a
specified order.

The order of elements is determined by sorting them by
the order values you assigned them, which are recorded
in the hash table (except for elts with no recorded order,
which are in no special order at the end of the list,
after those with specified orders - these elts are not
recorded in the hash table).

The hash table key is the element, and the key's value
is the element's recorded order.

You can assign multiple elements the same order, in which
case they appear consecutively in the list but the order
among them isn't specified.  (Well, it's deterministic,
but essentially by recording the same recorded order for
them you're saying you don't care what the order is among
them.)

Once you assign an order to an element it's retained until
you change it (by specifying a different number as ORDER)
or you remove it (by specifying a non-nil, non-number
ORDER value).  If you remove it, it's just as if it never
had a specified order - it goes after elts with specified
orders.

You specify a particular order for a given element if you
care about its position.  If you add or remove elements
without ever having specified an order for them then they
just remain after any elts that have specified orders; the
relative order among those elts with no specified order
doesn't change.

You're right, however, that the new TEST predicate arg
cannot be used only for the hash table, in place of the
hard-coded `eq'.  It needs to also be used in place of
the hard-coded `memq', to test membership in the list.

E.g., instead of this:

(unless (memq element (symbol-value list-var))
  (set list-var (cons element (symbol-value list-var))))

This:

(unless (cl-member element (symbol-value list-var) :test TEST)
  (set list-var  (cons element (symbol-value list-var))))

> > If the third optional argument ORDER is a number (integer or
> > float), set the element's list order to the given value.  If
> > ORDER is nil or omitted, do not change the numeric order of
> > ELEMENT.  If ORDER has any other value, remove the numeric order
> > of ELEMENT if it has one.
> 
> The actual ORDER bit is optional, which makes no sense for a function
> that's allegedly about an ordered list.

It makes sense if you don't care about keeping the order
of some elements.  If you care about the order of each
element then when you add it you give it a numeric ORDER.
(Once it has a recorded order you need not provide ORDER
when you call the function, in which case the function
call is a no-op for that element.)

>     > (when order
>     >   (puthash element (and (numberp order) order) ordering))
> 
> The hash table is only used to store this ORDER, and ORDER is silently
> discarded unless it's a number.

No, it's not silently discarded.  A non-nil, non-number
ORDER _removes_ the recorded order from that element.
IOW, it removes the element from the hash table, so
`gethash' returns nil for it.

>     > (unless (memq element (symbol-value list-var))
>     >   (set list-var (cons element (symbol-value list-var))))
> 
> This is the actual member check -- the hash table isn't used to keep
> track of what's already in the list or not.

Correct.  The hash table is used to keep track of the
recorded orders for list elements (and they need not
all have recorded orders, i.e., they need not all be
in the hash table).

>     > (set list-var (sort (symbol-value list-var)
> 
> The list is re-sorted upon every call, which is maximally inefficient.

Has to be done, in general.  The only case (I think)
where it could be avoided is when the ELEMENT is in
the hash table (i.e., it has a recorded order) and the
call to `add-to-order-list' for that ELEMENT uses nil
for ORDER.

> 			> (lambda (a b)
> 			>   (let ((oa (gethash a ordering))
> 			> 	(ob (gethash b ordering)))
> 			>     (if (and oa ob)
> 			> 	(< oa ob)
> 			>       oa)))))))
> 
> Finally, we sort based on the values stashed in the hash table, and the
> ones with a (numerical) order gets sorted first.

Yes.

> It's a strange, maximally inefficient function.  I'll fix it up a bit
> and add the test-function.

It is indeed strange.  I don't think it's inefficient,
but you may be right.

The code change should be easy.  The doc clarification
won't be so easy.