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

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

[Drew Adams]

Dunno whether functions like these might be useful.  I use something
similar.  If you think they're useful, consider adding them.

(cl-defun alist-to-hash-table (alist &optional use-last-p
                                     &key (test 'eql) weakness (size 65)
                                     (rehash-size 1.5) (rehash-threshold 0.8))
  "Create and return a hash table created from ALIST.
By default, if the same alist key is used in more than one alist entry
then only the first entry is used for the hash table.  Non-nil
USE-LAST-P means override this to use only the last entry for a given
key.

See `make-hash-table' for the keyword arguments you can use and their
default values."
  (let ((ht  (make-hash-table :test test :weakness weakness :size size
                              :rehash-size rehash-size :rehash-threshold rehash-threshold))
        key val)
    (dolist (key.val  alist)
      (setq key  (car key.val)
            val  (cdr key.val))
      (when (or use-last-p  (not (gethash key ht)))
        (puthash key val ht)))
    ht))

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


In GNU Emacs 25.3.1 (x86_64-w64-mingw32)
 of 2017-09-26
Windowing system distributor `Microsoft Corp.', version 6.1.7601
Configured using:
 `configure --without-dbus --without-compress-install 'CFLAGS=-O2
 -static -g3' PKG_CONFIG_PATH=/mingw64/lib/pkgconfig'

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

[Michael Heerdegen]

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

> Dunno whether functions like these might be useful.  I use something
> similar.  If you think they're useful, consider adding them.

I think something very similar is provided by map.el: `map-into'.


Michael.

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

[Drew Adams]

> > Dunno whether functions like these might be useful.  I use something
> > similar.  If you think they're useful, consider adding them.
> 
> I think something very similar is provided by map.el: `map-into'.

Good to know.  Thx.

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

[Drew Adams]

> > > Dunno whether functions like these might be useful.  I use something
> > > similar.  If you think they're useful, consider adding them.
> >
> > I think something very similar is provided by map.el: `map-into'.
> 
> Good to know.  Thx.

Actually, going from alist to hash table doesn't look so
useful with `map-into'.  A caller should be able to specify
the hash-table parameters (features), such as :test.

`map-into' should probably accept additional, keyword args,
which would be passed to `map--into-hash-table'.

I imagine that `map-into' is intended to be extended to
more than alists and hash tables eventually.  Otherwise,
dedicated functions for those two types, such as what I
suggested, would make as much (or more) sense.

Whether or not it will be so extended, it would be good
for `map-into' to accept additional args that would be
passed to the appropriate type-conversion helper functions.

If we just allowed an &rest ARGS parameter, that would
handle any types that might want to deal with additional
args.  But that would be less convenient than using
keyword args for a hash table.

We could I guess just pass ARGS along but define the
helper function (e.g. `map--into-hash-table') using
`cl-defun' with appropriate keyword args.  IOW, at the
`map-into' level nothing would be specified about ARGS,
but each conversion helper could define what kinds of
args it accepts.

(There's also `&allow-other-keys', but probably it
doesn't make much sense for `map-into' to define any
keyword args.)

In that case, the helper function should not be
"internal", and the use of `make-hash-table' keyword
args should be mentioned in its doc string.

Although simple lookup in an Elisp alist typically
uses only `assoc' or `assq' (or `rassoc' or `rassq'),
a program that _uses_ an alist might well make use
of a different equality test for its elements.  It
need not be limited to testing membership using
`assoc' or `assq'.

So while the alist to be converted to a hash table
might not, itself, have any fancy notion of a :test
function, the appropriate "equivalent" hash table in
some context might well need to define a particular
:test.

This is why it makes sense to allow conversion to a
hash table to give programmers an ability to specify
:test (and other hash-table features).

Note too that in Common Lisp `assoc' takes a :test arg.
`map-into' is designed for alists that use `cl-assoc'
as much as for those that use `assoc'.  Unlike a hash
table, however, an alist doesn't itself record ir
require any particular :test function, so `map-into'
can't transfer a hash-table :test to an alist that it
produces from a hash table.  So the existing `map-into'
for conversion to an alist is good enough.

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

[Nicolas Petton]

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

Michael Heerdegen <michael_heerdegen@web.de> writes:

>> Actually, going from alist to hash table doesn't look so
>> useful with `map-into'.  A caller should be able to specify
>> the hash-table parameters (features), such as :test.
>
> Yeah, that's what I thought, too.

That's something I can easily add.  `map-into' would then look like
the following `(defun map-into (map type &rest keywords))'.

However, `keywords' would be ignored when converting to an alist.  I'm
not sure I like it.

> Maybe Nicolas, maintainer of the library, wants to kick in (CC'ing
> him).

No you didn't :-P.

Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

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

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> However, `keywords' would be ignored when converting to an alist.  I'm
> not sure I like it.

If you don't like it, then maybe `map-into' is a misconception, and we
should use different functions as Drew suggested instead.


BTW, when I looked at map.el, i noticed that we have `map-some' and
`map-every-p'.  Is there a reason for the different naming style (one
has -p, the other one has not)?


Michael.

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

[Drew Adams]

(Odd: I (and the bug-list?) don't seem to have received the
reply from Michael that you quote below.)

> Michael Heerdegen <michael_heerdegen@web.de> writes:
>
> > >> Actually, going from alist to hash table doesn't look so
> >> useful with `map-into'.  A caller should be able to specify
> >> the hash-table parameters (features), such as :test.
> >
> > Yeah, that's what I thought, too.
> 
> That's something I can easily add.  `map-into' would then look
> like the following `(defun map-into (map type &rest keywords))'.

&rest keywords does not treat the keywords as keywords.
That's why we have (CL has) &keys.  (And &rest can be
used together with &keys.)

> However, `keywords' would be ignored when converting to
> an alist.  I'm not sure I like it.

Converting to an alist is different from converting to
a hash table.  As I mentioned, in particular a hash table
has, as part of its definition, a :test function etc.
An alist does not.  Even an alist in CL does not, even
though CL at least allows :test with `assoc'.

So a general function that wants to handle the two the
same way is out of luck.  The best it can do is just
allow whatever keyword args or other args a given
target representation construction function might need.
But in that case it cannot actually control such args
in the call.

See the code I sent originally.

Note too the optional arg USE-LAST-P that I provided
for conversion of an alist to a hash-table.

Unlike a hash table, an alist is often used in a way
that allows multiple entries for the same key, and
in particular in a way where the first entry shadows
the other entries for the same key.

That means that, for that common alist use case, it
is likely that the conversion to a hash table would
use only the first alist entry with a given key,
ignoring any others.

But because an alist can be used in multiple ways,
including ways where the other entries (shadowed in
the typical case) are relevant, and because the
most common case among those cases is for the last
entry, not the first one, to be most relevant, we
provide arg USE-LAST-P.  When that arg is non-nil
the last alist entry for a given key is used for
the hash table.

(If you get a hash table from an alist then you
necessarily get only one entry for a given key.
So you do not really capture the alist in all its
functionality.  Presumably someone asking for such
a conversion knows this.  We could, instead of
providing an optional arg such as USE-LAST-P, just
expect the user who wants the hash table to have
already removed all alist entries with the same
key except for the entry s?he wants.  But that
can be a bit of a bother, and it's easy to
provide USE-LAST-P as a convenience.)

It's great to have abstract, general-purpose
functions that handle maps, sequences, streams,
etc.  But not all such things are handled the
same way in Lisp code.  An alist is itself quite
general, so it can be and is used in different
ways in different programs.  There is no single,
simple mapping from an arbitrary alist to a hash
table, I think.

We can provide a general-purpose function that
chooses just one kind of mapping from an alist
to, e.g., a hash table.  But I'm guessing that we
should also provide a function that gives you more
control over the conversion mapping.  IOW, maybe
both a `map-into' kind of general-purpose behavior
and a more specific `alist-to-hash-table' kind of
behavior.

(But for the time being, `map-into' is only for
list <-> hash table, so for the time being it
seems less useful than the more specific
function.)

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

[Drew Adams]

> It's great to have abstract, general-purpose
> functions that handle maps, sequences, streams,
> etc.  But not all such things are handled the
> same way in Lisp code.  An alist is itself quite
> general, so it can be and is used in different
> ways in different programs.  There is no single,
> simple mapping from an arbitrary alist to a hash
> table, I think.
> 
> We can provide a general-purpose function that
> chooses just one kind of mapping from an alist
> to, e.g., a hash table.  But I'm guessing that we
> should also provide a function that gives you more
> control over the conversion mapping.  IOW, maybe
> both a `map-into' kind of general-purpose behavior
> and a more specific `alist-to-hash-table' kind of
> behavior.
> 
> (But for the time being, `map-into' is only for
> list <-> hash table, so for the time being it
> seems less useful than the more specific
> function.)

Any news on this?  There is no general, abstract
solution proposed, so far, to meet the needs met
by the specific alist <-> hash-table code I sent.

Should we not add that code or similar to Emacs?

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

[Noam Postavsky]

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

> Any news on this?  There is no general, abstract
> solution proposed, so far, to meet the needs met
> by the specific alist <-> hash-table code I sent.

Did you have any comments for my proposal in #29?

https://debbugs.gnu.org/cgi/bugreport.cgi?bug=28753#29

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

[Drew Adams]

> > Any news on this?  There is no general, abstract
> > solution proposed, so far, to meet the needs met
> > by the specific alist <-> hash-table code I sent.
> 
> Did you have any comments for my proposal in #29?
> 
> https://urldefense.proofpoint.com/v2/url?u=https-
> 3A__debbugs.gnu.org_cgi_bugreport.cgi-3Fbug-3D28753-
> 2329&d=DwIBAg&c=RoP1YumCXCgaWHvlZYR8PZh8Bv7qIrMUB65eapI_JnE&r=kI3P6ljGv6CTH
> IKju0jqInF6AOwMCYRDQUmqX22rJ98&m=2PshIV1HLbvhys07NQMj0gaYobwyLDaPs6zHJYzxwD
> Y&s=30GvxP6lcqjxDwNDmk0njIsHZRQE1V1VGEA4JNZLf60&e=

I don't see a complete proposal there.

Your solution is apparently to punt, telling users to
first create the hash table they need and then call a
function that injects the alist key+value entries into
that existing table.

I think that's less clear than the function I provided.

And in particular it does not provide a USE-LAST
possibility.  Does it?  Would you be adding an optional
such arg to `map--into-existing-hash-table', to handle
this?  Would the default behavior of that function use
only the first entry with a given key, as is typical for
an alist?

If you show how to achieve all of what this definition
achieves, then I guess it would be OK - provided its doc
makes it just as clear as is clear for this function how
to get specific alist-to-hash-table mappings:

(cl-defun alist-to-hash-table (alist &optional use-last-p
                                     &key (test 'eql) weakness (size 65)
                                     (rehash-size 1.5) (rehash-threshold 0.8))
  "Create and return a hash table created from ALIST.
By default, if the same alist key is used in more than one alist entry
then only the first entry is used for the hash table.  Non-nil
USE-LAST-P means override this to use only the last entry for a given
key.

See `make-hash-table' for the keyword arguments you can use and their
default values."
  (let ((ht  (make-hash-table
               :test test :weakness weakness :size size
               :rehash-size rehash-size
               :rehash-threshold rehash-threshold))
        key val)
    (dolist (key.val  alist)
      (setq key  (car key.val)
            val  (cdr key.val))
      (when (or use-last-p  (not (gethash key ht)))
        (puthash key val ht)))
    ht))

Users shouldn't have to reinvent that by figuring out how
they might achieve its possibilities using `map-into'.

You would presumably start by defining
`map--into-existing-hash-table'.  (Why would that function
be "internal", BTW?)

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

[Noam Postavsky]

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

>> Did you have any comments for my proposal in #29?
>
> I don't see a complete proposal there.

Correct, I wanted to get comments on the whether the approach was
acceptable before finishing it.

> Your solution is apparently to punt, telling users to
> first create the hash table they need and then call a
> function that injects the alist key+value entries into
> that existing table.

Yes, if they want a hash table with specific parameters.

> I think that's less clear than the function I provided.

I think it has the advantage that the conversion function doesn't have
to know about all the possible parameters involved in hash table
creation.  Therefore the interface is simpler.

> And in particular it does not provide a USE-LAST
> possibility.

No, but I think it could be easily added.

> You would presumably start by defining
> `map--into-existing-hash-table'.  (Why would that function
> be "internal", BTW?)

I meant it as a variant on `map--into-hash-table', so it uses the same
naming convention.

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

[Michael Heerdegen]

Noam Postavsky <npostavs@users.sourceforge.net> writes:

> Drew Adams <drew.adams@oracle.com> writes:
>
> > Any news on this?  There is no general, abstract
> > solution proposed, so far, to meet the needs met
> > by the specific alist <-> hash-table code I sent.
>
> Did you have any comments for my proposal in #29?

That's clever.

OTOH I'm not convinced that `map-into' is a good abstraction.  Every
goal type might have an individual set of useful parameters, especially
when we want to add support for other map types in the future.  Our
choice now to unite those in one conversion interface function might
result in quite a mess later.


Michael.

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

[Philipp Stephani]

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

Michael Heerdegen <michael_heerdegen@web.de> schrieb am Di., 7. Nov. 2017
um 14:29 Uhr:

> Noam Postavsky <npostavs@users.sourceforge.net> writes:
>
> > Drew Adams <drew.adams@oracle.com> writes:
> >
> > > Any news on this?  There is no general, abstract
> > > solution proposed, so far, to meet the needs met
> > > by the specific alist <-> hash-table code I sent.
> >
> > Did you have any comments for my proposal in #29?
>
> That's clever.
>
> OTOH I'm not convinced that `map-into' is a good abstraction.  Every
> goal type might have an individual set of useful parameters, especially
> when we want to add support for other map types in the future.  Our
> choice now to unite those in one conversion interface function might
> result in quite a mess later.
>

I don't think a unified conversion interface is that important. The various
structures used for mappings are just too different. For example, alists
and plists aren't real types, they are only defined by their usage. Hash
tables, on the other hand, are real types, with a per-object comparison
function, a non-nil empty value, etc. These two kinds of objects are just
too different to treat uniformly. Also, in most cases it is statically
known which kinds of objects are involved, so a generic function that
dynamically selects on the type of object isn't that useful. How about
adding some simple conversion functions to subr.el such as
(defun alist-to-hashtable (alist &rest keys) ...)
(defun hashtable-to-alist (hashtable) ...)

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

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

[Drew Adams]

> I don't think a unified conversion interface is that important.
> The various structures used for mappings are just too different.
> For example, alists and plists aren't real types, they are only
> defined by their usage. Hash tables, on the other hand, are real
> types, with a per-object comparison function, a non-nil empty
> value, etc. These two kinds of objects are just too different
> to treat uniformly. Also, in most cases it is statically known
> which kinds of objects are involved, so a generic function that
> dynamically selects on the type of object isn't that useful.
>
> How about adding some simple conversion functions to subr.el such as
> 
> (defun alist-to-hashtable (alist &rest keys) ...) 
> (defun hashtable-to-alist (hashtable) ...)

Which brings us back to the very first msg of this thread -
the bug report.  Please see the code I proposed there.

And note the differences from the signature you show for
`alist-to-hashtable'.  I think those differences are
important and your signature is not satisfactory.

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

[Philipp Stephani]

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

Drew Adams <drew.adams@oracle.com> schrieb am Sa., 30. Dez. 2017 um
22:08 Uhr:

> > I don't think a unified conversion interface is that important.
> > The various structures used for mappings are just too different.
> > For example, alists and plists aren't real types, they are only
> > defined by their usage. Hash tables, on the other hand, are real
> > types, with a per-object comparison function, a non-nil empty
> > value, etc. These two kinds of objects are just too different
> > to treat uniformly. Also, in most cases it is statically known
> > which kinds of objects are involved, so a generic function that
> > dynamically selects on the type of object isn't that useful.
> >
> > How about adding some simple conversion functions to subr.el such as
> >
> > (defun alist-to-hashtable (alist &rest keys) ...)
> > (defun hashtable-to-alist (hashtable) ...)
>
> Which brings us back to the very first msg of this thread -
> the bug report.  Please see the code I proposed there.
>

OK thanks. I think your definitions would be a useful addition to subr.el.


>
> And note the differences from the signature you show for
> `alist-to-hashtable'.  I think those differences are
> important and your signature is not satisfactory.
>

NB, I have the `&rest keys` in my arglist, with similar intentions as your
definition.

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

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

[Noam Postavsky]

On Thu, Oct 12, 2017 at 9:27 AM, Nicolas Petton <nicolas@petton.fr> wrote:
> Michael Heerdegen <michael_heerdegen@web.de> writes:
>
>>> Actually, going from alist to hash table doesn't look so
>>> useful with `map-into'.  A caller should be able to specify
>>> the hash-table parameters (features), such as :test.
>>
>> Yeah, that's what I thought, too.
>
> That's something I can easily add.  `map-into' would then look like
> the following `(defun map-into (map type &rest keywords))'.
>
> However, `keywords' would be ignored when converting to an alist.  I'm
> not sure I like it.

What about just receiving the hash-table as a parameter:

(defun map-into (map type)
  "Convert the map MAP into a map of type TYPE.

TYPE can be one of the following symbols: `list', `hash-table'; or it
can be a hash-table to use.
MAP can be a list, hash-table or array."
  (pcase type
    (`list (map-pairs map))
    (`hash-table (map--into-hash-table map))
    ((pred hash-tablep) (map--into-existing-hash-table map type)
    (_ (error "Not a map type name: %S" type)))))

(defun map--into-existing-hash-table (map hash-table)
  ...)

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

[Nicolas Petton]

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

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

> I imagine that `map-into' is intended to be extended to
> more than alists and hash tables eventually.

Yes, the same way `seq.el' can be extended (using generic functions).  I
haven't yet found the time to do it though, it's a pretty big
refactoring of the library.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

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

[Lars Ingebrigtsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> I think something very similar is provided by map.el: `map-into'.

The discussion then went onto how to specify parameters to
make-hash-table, and I see that this is fixed now like this:

  (map-into '((1 . 3)) '(hash-table :test eql))

So there doesn't seem to be anything further to do here, and I'm
therefore closing this bug report.

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

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

[Drew Adams]

> Michael Heerdegen <michael_heerdegen@web.de> writes:
> 
> > I think something very similar is provided by map.el: `map-into'.
> 
> The discussion then went onto how to specify parameters to
> make-hash-table, and I see that this is fixed now like this:
> 
>   (map-into '((1 . 3)) '(hash-table :test eql))
> 
> So there doesn't seem to be anything further to do here, and I'm
> therefore closing this bug report.

IOW, you ignored the entire thread.  The bug is NOT
about "how to specify parameters to make-hash-table".

Yet another won't-fix.

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

[Philipp Stephani]

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

Drew Adams <drew.adams@oracle.com> schrieb am Mo., 9. Okt. 2017 um
02:27 Uhr:

> Dunno whether functions like these might be useful.  I use something
> similar.  If you think they're useful, consider adding them.
>

I think both are useful.


>
> (cl-defun alist-to-hash-table (alist &optional use-last-p
>                                      &key (test 'eql) weakness (size 65)
>                                      (rehash-size 1.5) (rehash-threshold
> 0.8))
>   "Create and return a hash table created from ALIST.
> By default, if the same alist key is used in more than one alist entry
> then only the first entry is used for the hash table.  Non-nil
> USE-LAST-P means override this to use only the last entry for a given
> key.
>
> See `make-hash-table' for the keyword arguments you can use and their
> default values."
>   (let ((ht  (make-hash-table :test test :weakness weakness :size size
>                               :rehash-size rehash-size :rehash-threshold
> rehash-threshold))
>         key val)
>     (dolist (key.val  alist)
>       (setq key  (car key.val)
>             val  (cdr key.val))
>       (when (or use-last-p  (not (gethash key ht)))
>

This doesn't work if the value is nil. You need to use an uninterned symbol
or some other unique object, e.g.
(eq (gethash key ht #1='#:void) #1#)


>         (puthash key val ht)))
>     ht))
>

I'd personally make use-last-p another keyword argument, though.


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

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

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

[Drew Adams]

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

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

[Philipp Stephani]

[-- 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 --]

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

[Drew Adams]

>> 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.
 
Emacs hash tables don't fall from the sky.  They are not
shadows of some Platonic ideal.  This is a design choice.
Emacs Lisp can implement hash tables any way it wants.

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

Neither of those assertions has been demonstrated.  Feel
free to do so (how much overhead, how infrequent).

And infrequency of use is not, alone, a good reason not
to support something.  Infrequent does not mean unimportant.

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

Why?  How much 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.)

Emacs Lisp has lots of features that are not in "most
programming languages".  Propertized strings, for one
trivial example.

> Even for alists, most of the time maintaining insertion
> order is an irrelevant detail,

What time maintaining insertion order?  I can't imagine
what you mean by that.

> most users care only about get/put/remove.

Not demonstrated.  But even if it were true, it wouldn't
follow that Lisp alist order is unimportant.

Next you'll be suggesting that because lists are mutated
relatively infrequently it is unimportant to be able to
modify list structure or test cons equality with `eq'.
Or that because true lists are used most of the time we
might as well drop support of dotted lists.

----

Naive google search -

https://www.javaspecialists.eu/archive/Issue073.html

https://stackoverflow.com/questions/12998568/hashmap-vs-linkedhashmap-performance-in-iteration-over-values/12998878

https://stackoverflow.com/questions/26623129/when-to-use-linkedhashmap-over-hashmap-in-java