Equivalent of Clojure's “assoc-in” and “get-in” in Common lisp

Question

In Clojure you can update a map (dict) with assoc-in and create key path automatically if it don't exist.

(assoc-in {:a 1 :b 3} [:c :d] 33)
; {:a 1, :c {:d 33}, :b 3}

Same for get-in: you can specify a path of keys (or list indices) and it will return the value specified by the path, nil if it does not exist.

(get-in {:a 1, :c {:d 33}, :b 3} [:c :d])
; 33
(get-in {:a 1, :c {:d 33}, :b 3} [:c :e])
; nil

I like to have the sugar in Common lisp,so I monkeyed a 'assoc-in' and I tested it on a trie I made out of list structure, I leave ':leaf' preserved, so the result of 'get-in' is always list:

• test case: (setf trie '(:A (:B (:leaf t) :C (:leaf t)) :D (:leaf t)))

get-in implementation and test:

(defmacro get-in (trie ks)  `(reduce #'getf  ,ks :initial-value ,trie))
(get-in trie '(:a :b)) ; (:leaf t)
(get-in trie '(:a :b :leaf)) ; t

assoc-in implementation and test:

(defmacro assoc-in (trie ks v)
 `(setf (getf (get-in ,trie ,ks) :leaf) ,v))

(assoc-in trie '(:a :b) 99)
(get-in trie '(:a :b)) ; (:leaf 99)
(assoc-in trie '(:a :b :new-key) "new-key") ; (SETF REDUCE) is not fbound

I have trouble with 'assoc-in', I can update the trie but can't insert

Any advice is welcomed, doesn't have to be macro. I looked up Clojure implementation and tried to do it in Common lisp, also failed.

Answer 1

Since there are 95 times view, here I post my solution.

(defvar *list-trie* '(:A (:B (:leaf t) :C (:leaf t)) :D (:leaf t)))
(defun get-in-list (trie ks)
  "input a key chain list, return children of common ancestors, return nil of not exist"
  (reduce #'(lambda (node k) (and (listp node) (getf node k))) ks :initial-value trie))

(defmacro clojure-assoc-list (trie k v)
  "return updated list"
  `(progn (setf (getf ,trie ,k) ,v)
          ,trie))

(defun assoc-in-list (trie ks v)
  (if (= 1 (length ks))
      (clojure-assoc-list trie (car ks)  v)
      (clojure-assoc-list trie (car ks) (assoc-in-list (getf trie (car ks)) (cdr ks) v))))

Answer 2

Here's how I'd do this. The docstrings and comments in the code explain what's happening. First a utility function:

(defun make-nested-alist (value items)
  "Returns a nested association list that takes the first item
to an association list that takes the second item to an 
association list, and so on, finally to the value.  If items
is the empty list, then the value is returned by itself."
  (reduce (lambda (item value)
            (acons item value '()))
          items :initial-value value
          :from-end t))

(make-nested-alist 3 '())
;=> 3
(make-nested-alist 3 '(a b c))
;;=> ((a . ((b . ((c . e))))))

Now, a function that will retrieve values from a nested association list.

(defun assoc* (items alist)
  "Finds the item in the nested association list keyed by the items.
It is an error if a prefix of the path leads to a value that cannot be
interpreted as an associate list."
  (if (endp items) alist
      (assoc* (rest items)
              (cdr (assoc (first items) alist)))))

(defparameter *alist*
  (copy-tree '((a . 1)
               (b . 3)
               (c . ((d . 33))))))

(assoc* '(a) *alist*) ;=> 1
(assoc* '(c d) *alist*) ;=> 33
(assoc* '(c e) *alist*) ;=> NIL
(assoc* '(a b) *alist*) ; ERROR (since the prefix (a) leads to 1)

Now, a function to "update" a nested association list. Note that this will update most association lists in place, but since you can't modify an empty list in place, you need to use the return value from this function.

(defun assoc*-update (value items alist)
  "Returns a nested association list like the provided one, except
that the value at the path specified by items contains value.  This
will modify the association list if the any prefix of the path is a
value in the association list.  Because the result may be a new
list (e.g., when the original association list does not have a top
level entry for the initial item in the path), the result should be
used."
  (if (endp items)
      value
      (let ((entry (assoc (first items) alist)))
        (if (null entry)
            ;; if there is no entry at all, then we need to make a
            ;; nested association list out of the rest keys that
            ;; eventually comes back to the value, and tack it onto
            ;; the current alist. We can't modify alist, because alist
            ;; might be empty, and we can't modify the empty list.
            (acons (first items) (make-nested-alist value (rest items)) alist)
            ;; Otherwise, there is an entry, and that takes care of the
            ;; first key, but we'll need to recurse into the value and
            ;; update it.  If there are no keys left, then we should just
            ;; replace this entry, otherwise we need to recurse into it.
            ;; In both cases, we return alist.
            (prog1 alist
              (rplacd entry (assoc*-update value (rest items) (cdr entry))))))))

(let ((alist (copy-tree *alist*)))
  (setf alist (assoc*-update 42 '(c e) alist))
  (print alist)
  (setf alist (assoc*-update 89 '(d) alist))
  (print alist))
;=>          ((A . 1) (B . 3) (C (E . 42) (D . 33))) 
;=> ((D . 89) (A . 1) (B . 3) (C (E . 42) (D . 33)))