bug#28753: 25.3; Functions to get alist from hash table and vice versa

[Philipp Stephani <p.stephani2@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 4982 bytes --]

Drew Adams <drew.adams@oracle.com> schrieb am So., 31. Dez. 2017 um
01:01 Uhr:

> > > (when (or use-last-p  (not (gethash key ht)))
> >
> > This doesn't work if the value is nil.
>
> I guess you mean that it doesn't DTRT if the cdr of an alist
> entry is `nil' - e.g. (foo) aka (foo . nil).
>

Yes.


>
> > You need to use an uninterned symbol or some other unique object, e.g.
> > (eq (gethash key ht #1='#:void) #1#)
>
> OK.  Dunno which is clearer or whether there is some
> performance difference, but I would probably just bind
> a var to a unique cons, e.g. (cons 1 1), outside the
> `dolist'.  E.g.:
>
> (let ((ht (make-hash-table :test test :weakness weakness
>                            :size size :rehash-size rehash-size
>                            :rehash-threshold rehash-threshold))
>       (uniq-cons (cons 1 1))
>       key val)
>   (dolist (key.val  alist)
>     (setq key  (car key.val)
>           val  (cdr key.val))
>     (when (or use-last-p  (not (eq (gethash key ht uniq-cons))))
>       (puthash key val ht)))
>   ht))
>
> (With your approach of using an uninterned symbol, wouldn't
> you want to do the same thing: bind a var to it outside the
> `dolist', or would that make no real difference?)
>

It's no real difference. I just proposed the shortest way that works.


>
> > I'd personally make use-last-p another keyword argument, though.
>
> I don't have a strong objection, but why?
>

Especially for booleans it's much clearer if the parameter name is repeated
on the call site.


>
> > > (defun hash-table-to-alist (hash-table)
> > >  "Create and return an alist created from HASH-TABLE.
> > > The order of alist entries is the same as the order of hash-table
> > > entries (which normally is the order in which the entries were added
> > > to the table)."
> > >  (let ((al  ()))
> > >    (maphash (lambda (key val) (push (cons key val) al)) hash-table)
> > >    (nreverse al)))
> >
> > Hmm, is the order guaranteed? I haven't found anything in the
> > Emacs Lisp manual about this, so maybe just leave out the
> > parenthetical remark or say that the order is unspecified?
>
> Good question!  But it's not just the parenthetical part.
> If we couldn't say anything about the traversal order of
> `maphash' then the whole sentence would need to go.
>
> FWIW, I think it's pretty important.  Order is quite
> important for alists, generally.
>
> Is there some reason we should not be able to count on
> this `maphash' behavior?
>

Order in hashtables is not guaranteed. If anything relies on the order,
it's buggy.


>
> That's the behavior I saw, AFAICT, but I didn't test much.
>
> I don't know whether it is guaranteed, but this use case
> involving conversion to alist looks like a good argument for
> some guarantee wrt order.
>

No. Ordering guarantees require additional complexity and overhead, and are
almost never needed.


>
> I see that in Common Lisp nothing is said about the traversal
> by `maphash' over the hash table.  This is all that is said:
>
>  "For each entry in hash-table, maphash calls function on two
>   arguments: the key of the entry and the value of the entry;
>   maphash then returns nil. If entries are added to or deleted
>   from the hash table while a maphash is in progress, the results
>   are unpredictable, with one exception: if the function calls
>   remhash to remove the entry currently being processed by the
>   function, or performs a setf of gethash on that entry to change
>   the associated value, then those operations will have the
>   intended effect."
>
>   - https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node155.html
>
> (Emacs doc should also probably say at least something about
> what happens when entries are added/removed during a `maphash'
> application.)
>

Yes.


>
> If Emacs decides not to guarantee the order seen now, which I
> think is the order I described in the doc string above, then we
> would need to remove that sentence.  That would be too bad for
> users of function `hash-table-to-alist', but at least they
> would, at least so far (and AFAICT), get that behavior, which
> is likely to be expected by them even if it is not documented.
>
> Another possibility (?): Allow _optional_ creation of a hash
> table that does preserve such ordering (even if just by
> recording order of entry and making that available to `maphash').
> E.g., add a keyword arg for `make-hash-table' that does just that.
>
> Even if it turned out that this consistently or occasionally
> detracted from performance, it could be a useful option.
> Conversion to an alist would be a case in point.
>

I don't think it would be worth the additional complexity. Hash tables have
been available for ages in most programming languages, and almost never
does anybody ask for ordering guarantees. (For example, I have never seen
somebody using LinkedHashMap in Java.)
Even for alists, most of the time maintaining insertion order is an
irrelevant detail, most users care only about get/put/remove.

[-- Attachment #2: Type: text/html, Size: 6864 bytes --]