GNU bug report logs -
#28753
25.3; Functions to get alist from hash table and vice versa
Previous Next
Reported by: Drew Adams <drew.adams <at> oracle.com>
Date: Mon, 9 Oct 2017 00:27:02 UTC
Severity: wishlist
Found in version 25.3
Done: Lars Ingebrigtsen <larsi <at> gnus.org>
Bug is archived. No further changes may be made.
Full log
Message #62 received at 28753 <at> debbugs.gnu.org (full text, mbox):
[Message part 1 (text/plain, inline)]
Drew Adams <drew.adams <at> 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.
[Message part 2 (text/html, inline)]
This bug report was last modified 3 years and 32 days ago.
Previous Next
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.