GNU bug report logs - #28876
26.0; (elisp) `Hash Tables': hash table vs alist

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 28876 in the body.
You can then email your comments to 28876 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Drew Adams <drew.adams <at> oracle.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 26.0; (elisp) `Hash Tables': hash table vs alist
Date: Tue, 17 Oct 2017 08:45:49 -0700 (PDT)

1. Please consider saying explicitly that an Elisp hash table is not a
multimap.

This is another way in which it differs from an alist.  An alist can
have multiple entries that have exactly the same key (even `eq').  An
Elisp hash table cannot - it realizes a mathematical function: one key
gives you only one value.

(The fact that `assoc' and `assq' ignore entries past the first is
irrelevant here.  An alist is a list; it can be used in many ways.)


2. Wrt the difference between an alist and a hash table, the emphasis in
this node seems to be on the performance characteristics.  I think that
functional/structural differences should be distinguished here from
performance differences, instead of just lumping them together in the
same bulleted list.

From the perspective of using a hash table, certainly the performance
(as well as the non-multimap characteristic) is important, and often
decisive.  But from the perspective of using an alist, the structure (as
well as the multimap characteristic) is also important: Lisp programs
manipulate alists as lists - they do not necessarily just use `assoc' or
`assq' on them.

This node seems to have been written by a hash table-only user, not a
general Lisp user, who might use both hash tables and alists.  Please
consider expanding the description of the difference between the two,
which means expanding on what is said about alists.

I recognize that the main purpose of this node is to describe/introduce
hash tables.  But this is Lisp, so I think it is important to _really_
describe how a hash table differs, in its use, from an alist.  An alist
is a more general thingy - you can use it in ways that you cannot use a
hash table.  That BIG difference does not come across in this node, so
far.

In GNU Emacs 26.0.90 (build 3, x86_64-w64-mingw32)
 of 2017-10-13
Repository revision: 906224eba147bdfc0514090064e8e8f53160f1d4
Windowing system distributor `Microsoft Corp.', version 6.1.7601
Configured using:
 `configure --without-dbus --host=x86_64-w64-mingw32
 --without-compress-install 'CFLAGS=-O2 -static -g3''

Message #10 received at 28876 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Drew Adams <drew.adams <at> oracle.com>
Cc: 28876 <at> debbugs.gnu.org
Subject: Re: bug#28876: 26.0; (elisp) `Hash Tables': hash table vs alist
Date: Wed, 09 Oct 2019 10:33:35 +0200

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

> 1. Please consider saying explicitly that an Elisp hash table is not a
> multimap.
>
> This is another way in which it differs from an alist.  An alist can
> have multiple entries that have exactly the same key (even `eq').  An
> Elisp hash table cannot - it realizes a mathematical function: one key
> gives you only one value.
>
> (The fact that `assoc' and `assq' ignore entries past the first is
> irrelevant here.  An alist is a list; it can be used in many ways.)

An alist is a list that associates keys with value.  There may be
several identical keys in the list, but that is not how an alist is
meant to be used, which is reflected in how the common operators on
alists work -- they only return the first match.

So I don't think this is a difference that needs to be pointed out here.

> 2. Wrt the difference between an alist and a hash table, the emphasis in
> this node seems to be on the performance characteristics.  I think that
> functional/structural differences should be distinguished here from
> performance differences, instead of just lumping them together in the
> same bulleted list.

The primary difference is in the performance characteristics, so I don't
see anything that needs changing in that node.  Closing.

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

Message #15 received at 28876 <at> debbugs.gnu.org (full text, mbox):

From: Drew Adams <drew.adams <at> oracle.com>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: 28876 <at> debbugs.gnu.org
Subject: RE: bug#28876: 26.0; (elisp) `Hash Tables': hash table vs alist
Date: Wed, 9 Oct 2019 07:47:50 -0700 (PDT)

> > 1. Please consider saying explicitly that an Elisp hash table is not a
> > multimap.
> >
> > This is another way in which it differs from an alist.  An alist can
> > have multiple entries that have exactly the same key (even `eq').  An
> > Elisp hash table cannot - it realizes a mathematical function: one key
> > gives you only one value.
> >
> > (The fact that `assoc' and `assq' ignore entries past the first is
> > irrelevant here.  An alist is a list; it can be used in many ways.)
> 
> An alist is a list that associates keys with value.  There may be
> several identical keys in the list, but that is not how an alist is
> meant to be used, which is reflected in how the common operators on
> alists work -- they only return the first match.

That is _exactly_ how an alist is meant to be used.

And not understanding that is precisely the problem here.

The point of using an alist is that you can, and you
typically will, have multiple entries with the same
key, AND that only the first one is returned by the
specifically-alist access functions.

An alist is not a hash table, and this is one of the
most important differences.

> So I don't think this is a difference that needs to be pointed out here.

That's unfortunate.

> > 2. Wrt the difference between an alist and a hash table, the emphasis in
> > this node seems to be on the performance characteristics.  I think that
> > functional/structural differences should be distinguished here from
> > performance differences, instead of just lumping them together in the
> > same bulleted list.
> 
> The primary difference is in the performance characteristics, so I don't
> see anything that needs changing in that node.

No, the primary difference is not in the performance
characteristics.  And even those can be more complex
that what is presented here.

Users used to other languages too often assume that
an Emacs-Lisp hash table will be more performant than
an alist, at least for a large set.  Things are not
so simple.

The primary difference is structural.  It is especially
that an alist is a Lisp _list_.

> Closing.

That's too bad.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.