unofficial mirror of bug-gnu-emacs@gnu.org 
 help / color / mirror / code / Atom feed
From: Drew Adams <drew.adams@oracle.com>
To: Philipp Stephani <p.stephani2@gmail.com>
Cc: 28753@debbugs.gnu.org
Subject: bug#28753: 25.3; Functions to get alist from hash table and vice versa
Date: Sat, 30 Dec 2017 16:01:24 -0800 (PST)	[thread overview]
Message-ID: <94d02ad7-d069-4195-b84a-13229dfa3e9a@default> (raw)
In-Reply-To: <CAArVCkSjR-o9au-gkUzKm21zO9Nn0y-dH=w8YiP=35Hp=UXNhw@mail.gmail.com>

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

> 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?)
 
> I'd personally make use-last-p another keyword argument, though.

I don't have a strong objection, but why?

> > (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?

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.

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

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.





  reply	other threads:[~2017-12-31  0:01 UTC|newest]

Thread overview: 23+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-10-09  0:25 bug#28753: 25.3; Functions to get alist from hash table and vice versa Drew Adams
2017-10-09 13:20 ` Michael Heerdegen
2017-10-09 14:11   ` Drew Adams
2017-10-11 16:42     ` Drew Adams
     [not found]       ` <87wp4038m0.fsf@web.de>
2017-10-12 13:27         ` Nicolas Petton
2017-10-12 13:46           ` Michael Heerdegen
2017-10-12 14:36           ` Drew Adams
2017-11-06 16:19             ` Drew Adams
2017-11-07  0:46               ` Noam Postavsky
2017-11-07  2:24                 ` Drew Adams
2017-11-07  2:51                   ` Noam Postavsky
2017-11-07 13:28                 ` Michael Heerdegen
2017-12-30 20:40                   ` Philipp Stephani
2017-12-30 21:08                     ` Drew Adams
2017-12-30 21:15                       ` Philipp Stephani
2017-10-12 15:56           ` Noam Postavsky
2017-10-12 13:30       ` Nicolas Petton
2022-04-22 13:18   ` Lars Ingebrigtsen
2022-04-22 15:21     ` Drew Adams
2017-12-30 21:26 ` Philipp Stephani
2017-12-31  0:01   ` Drew Adams [this message]
2018-03-04 19:17     ` Philipp Stephani
2018-03-05  0:01       ` Drew Adams

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://www.gnu.org/software/emacs/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=94d02ad7-d069-4195-b84a-13229dfa3e9a@default \
    --to=drew.adams@oracle.com \
    --cc=28753@debbugs.gnu.org \
    --cc=p.stephani2@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).