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