clojure - 相当于 Common Lisp 中 Clojure 的 “assoc-in” 和 “get-in”

Question

在 Clojure 中，您可以使用 assoc-in 更新映射(字典)，并在不存在时自动创建关键路径。

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

与 get-in 相同:您可以指定键(或列表索引)的路径，它将返回该路径指定的值，如果不存在则返回 nil。

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

我喜欢在 Common lisp 中添加糖分，所以我搞了一个“assoc-in”，并在我用列表结构制作的 trie 上测试了它，我保留了“:leaf”，所以“get”的结果-in' 始终是列表:

• 测试用例:(setf trie '(:A (:B (:leaf t) :C (:leaf t)) :D (:leaf t)))

进入实现和测试:

(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 实现和测试:

(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

我在“assoc-in”方面遇到问题，我可以更新特里树，但无法插入

欢迎任何建议，不必是宏观的。我抬头看Clojure implementation并尝试在 Common lisp 中做到这一点，也失败了。

Answer 1

这就是我的做法。代码中的文档字符串和注释解释了发生的情况。首先是一个实用函数:

(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))))))

现在，函数将从嵌套关联列表中检索值。

(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)

现在，一个“更新”嵌套关联列表的函数。请注意，这将更新大多数关联列表，但由于您无法就地修改空列表，因此您需要使用此函数的返回值。

(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)))