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

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

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'



Reply | Threaded
Open this post in threaded view
|

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

Michael Heerdegen
Drew Adams <[hidden email]> 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.



Reply | Threaded
Open this post in threaded view
|

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.



Reply | Threaded
Open this post in threaded view
|

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.



Reply | Threaded
Open this post in threaded view
|

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

Nicolas Petton-2
Michael Heerdegen <[hidden email]> 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

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

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

Nicolas Petton-2
In reply to this post by Drew Adams
Drew Adams <[hidden email]> 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

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

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

Michael Heerdegen
In reply to this post by Nicolas Petton-2
Nicolas Petton <[hidden email]> 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.



Reply | Threaded
Open this post in threaded view
|

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

Drew Adams
In reply to this post by Nicolas Petton-2
(Odd: I (and the bug-list?) don't seem to have received the
reply from Michael that you quote below.)

> Michael Heerdegen <[hidden email]> 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.)



Reply | Threaded
Open this post in threaded view
|

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

Noam Postavsky-2
In reply to this post by Nicolas Petton-2
On Thu, Oct 12, 2017 at 9:27 AM, Nicolas Petton <[hidden email]> wrote:

> Michael Heerdegen <[hidden email]> 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)
  ...)