Re: plists, alists, and hashtables

[Stefan Monnier]

> Sure, absolutely.  I'm trying to say that a better read syntax for maps
> could avoid that altogether by making it impossible to specify something
> like the alist above.

You can't "make it impossible".
So, IIUC you want to signal errors for invalid maps.

> (mapcar #'car '((a) (b 1) (c . 2) d))
> -> Debugger entered--Lisp error: (wrong-type-argument listp d)
> ...and that's just a simple edge case.

So, now you don't want to signal errors for invalid maps?
Make up your mind.

> So you have to do
> (delq nil (mapcar #'car-safe '((a) (b 1) (c . 2) d)))

No: ((a) (b 1) (c . 2) d) is an invalid map, and it's perfectly OK (tho
not mandatory either) to signal an error when faced with such a thing.

> When the backend implementation is also the frontend, as with alists,
> you have to go through the whole alist to collect the keys. That's the
> access-time looping and parsing I mean. By contrast, the hashtable
> implementation (whether it does it now or not) can keep the list of keys
> and update it only when the data is modified.  At access time, the keys
> are instantly available.

Reality check: Have you looked at the definition of hash-table-keys?
Better yet: have you looked at how often hash-table-keys is used?
The efficiency of map-keys is largely irrelevant.

SM> More importantly, mathematical maps are persistent, whereas your
SM> apparently favorite implementation (the hash-table) is not persistent,
SM> contrary to (e.g.) alists.
> I am not sure what you mean.  Perhaps it's a problem with the
> terminology.  Could you explain?

alists can be functional, whereas hash-tables are by nature imperative.
For example,

   (cons (cons k v) m)

returns a new alist with a new mapping from "k" to "v" without changing
the map "m".  Whereas after

   (puthash k v m)

"m" has necessarily been modified.


        Stefan