Non destructive modify hash table

Question

Is it possible to non-destructively add new key-value pairs to a Common Lisp (SBCL) hash table? The standard way to add new elements to a hash table is to call:

(setf (gethash key *hash-table*) value)

but the call to setf modifies *hash-table* corrupting the original. I have an application where I'd like to take advantage of the efficiency of hash table lookups, but I also would like to non destructively modify them. The work-around I see is to copy the original hash table before operating on it, but that is not practical in my case since the hash tables I'm dealing with contain many thousands of elements and copying large hash tables, say, in a loop would negate the computational efficiency advantage of using them in the first place.

Answer 1

Depending on your needs you may be able to just use an association list, using assoc and other functions to establish new bindings on top of existing ones. The fact that assoc returns the first matching element means you can shadow bindings:

(let ((list '((:a . 1) (:b . 2))))
  (acons :b 3 list))

=> ((:b . 3) (:a . 1) (:b . 2))

If you call (assoc :b list) in the resulting list, the entry will be (:b . 3), but the original list is unmodified.

FSet

If association lists are not enough, the FSet library provides purely functional data-structures for Common Lisp, like maps, which are immutable hash-tables. They are implemented as balanced trees, which is better than a naive approach. There are also other data-structures that are more efficient, but you probably need to implement them yourselves (Hash array mapped trie (edit: see https://github.com/danshapero/cl-hamt, thanks @Flux)). That being said, FSet is good enough in general.

FSet is available through Quicklisp

USER> (ql:quickload :fset)

Create a map; notice the printed representation is made to be read again, if you install the appropriate reader macros. But you can perfectly use the library without the modified syntax table.

USER> (fset:map (:a 0) (:b 1))
#{| (:A 0) (:B 1) |}

Update the previous map with a new binding for :c:

USER> (fset:with * :c 3)
#{| (:A 0) (:B 1) (:C 3) |}

Update the previous map with a new binding for :b, which shadows the previous one:

USER> (fset:with * :b 4)
#{| (:A 0) (:B 4) (:C 3) |}

All the intermediate maps are unmodified:

USER> (list * ** *** )
(#{| (:A 0) (:B 4) (:C 3) |}
 #{| (:A 0) (:B 1) (:C 3) |} 
 #{| (:A 0) (:B 1) |})

Answer 2

I don't think that you can pass-by-reference a hash-table to another hash-table in common lisp. But what I had an idea was how to avoid to copy the entire hashtable, yet get to a result by one call is to use the default value argument position of gethash.

(gethash key ht default-value) returns what is given for default-value, when key is not present in ht.

;; prepare three example hash-tables, where *h3* and *h2* gets the additional keys
;; and if a key is not present in *h3*, one should look up in *h2*, and if not there too, in *h1*.
(defparameter *h1* (make-hash-table))
(setf (gethash 'a *h1*) 1)
(setf (gethash 'b *h1*) 2)
(setf (gethash 'c *h1*) 3)

(defparameter *h2* (make-hash-table))
(setf (gethash 'd *h2*) 4)
(setf (gethash 'e *h2*) 5)

(defparameter *h3* (make-hash-table))
(setf (gethash 'f *h3*) 6)

;; the call
(gethash 'a *h3* (gethash 'a *h2* (gethash 'a *h1*)))
;; would give the desired result `1`.

;; let us assume, there is a chain of hash-tables *hk* *h(k-1)* ... *h2* *h1*
;; in which one should look up into that order.
;; Then it is to us to build the code
;; (gethash 'a *hk* (gethash 'a *h(k-1)* ...(gethash 'a *h2* (gethash 'a *h1*))...))
;; automatically for every lookup.


;; this macro does it:
(defmacro mget (key hash-tables-list)
  (flet ((inject-last (e1 e2) `(,@e1 ,e2)))
    (reduce #'inject-last 
            (mapcar (lambda (ht) `(gethash ,key ,ht)) 
                    (nreverse hash-tables-list)))))

;; let's see its macroexpansion:
(macroexpand-1 '(mget 'a (*h3* *h2* *h1*)))
;; (GETHASH 'A *H3* (GETHASH 'A *H2* (GETHASH 'A *H1*))) ;
;; T

;; and run the code:
(mget 'a (*h2* *h1*))
;; 1 ;
;; NIL

One could attach information which are the next hash table to look in in the hash-table object. And even automate the generation of the list (*h3* *h2* *h1*) so that one writes only (gethash* key ht) which then calls mget ...

Well, of course through all this the hash-access gets slowed.

It is a trade-off between copying entire hash-tables or pay the cost in performance at each call ...

automatic finding of hash-tables which are extended by *h3*

(setf (get '*h3* 'extendeds) '(*h2* *h1*))
(setf (get '*h2* 'extendeds) '(*h1*))

(defun collect-extendeds (hts)
  (let ((res (loop for ht in hts
                   nconcing (get ht 'extendeds))))
    (remove-duplicates res)))

;; this function can recursively retrieve all hashtables
(defun get-extendeds* (hts &optional (acc '()))
  (let ((hts (if (listp hts) hts (list hts))))
      (let ((nexts (collect-extendeds hts)))
        (cond ((every #'null nexts) (nreverse (remove-duplicates (append hts acc))))
              (t (get-extendeds* nexts (remove-duplicates (append hts acc))))))))

;; write a macro to retrieve key's value from all downstream hashtables
(defmacro geth (key ht)
  `(mget ,key ,(get-extendeds* ht)))

(geth 'a *h3*)
;; 1 ;
;; NIL  ;; NIL because it was not in *h3* directly but in one of the hashtables
;; which it extends.

;; problem is if 'NIL is a value of an existing key,
;; one would still get 'NIL NIL.