PGS trong một danh sách lồng nhau

Question

Tôi có danh sách lồng nhau sau:

(setq x '(foo . ((bar . ((chocolate . "edible") (gold . "inedible")))
                 (jar . "glass"))))

Làm thế nào để có được mục nhập (chocolate . "edible")?

Tôi đã đọc câu hỏi này & và điều này

Nhưng không giống như q1, tôi không biết "đường dẫn" đến giá trị và không giống như q2, tôi muốn triển khai Elisp. Ngoài ra, tôi có một danh sách lớn hơn có thể có "độ sâu" là 2 - 5 (theo độ sâu, ý tôi là các danh sách)

Cho đến nay đây là những gì tôi có thể nấu ra:

(defun assoc-recur (key list)
  (if (listp (cdr list))
      (assoc key (cdr list))
    (assoc-reccur key (cdr list))))

Rõ ràng là mã này chỉ hoạt động miễn là giá trị không phải là danh sách các danh sách như (bar . ((..))

Làm cách nào tôi có thể truy cập một giá trị trong một danh sách lồng nhau với vanilla Elisp (không có mô phỏng CL)? Hay tôi nên từ bỏ và cài đặt api CL và thử q2?

Cú pháp tôi đang tìm kiếm giống như (func key list)

ps: Tôi khá mới với Emacs nên có lẽ tôi đang bỏ lỡ một chức năng tiện lợi.

Answer 1

Tôi có danh sách lồng nhau sau:

Ví dụ này không hiển thị một danh sách thực, vì phần tử đầu tiên của nó foo, không phải là ô khuyết điểm. Cá nhân tôi gọi nó là một cái cây. Các hàm như assoc-stringcó thể xử lý điều này, các hàm khác có thể bỏ qua các yếu tố như vậy, nhưng nói chung các hàm alist mong đợi mọi yếu tố đều là khuyết điểm với một chiếc xe hơi và một cdr. Xem (info "(elisp) Lists")và các subnodes của nó.

Cho đến nay đây là những gì tôi có thể nấu ra:

Elisp không xử lý đệ quy rất hiệu quả, vì vậy tôi khuyên bạn nên tránh nó nói chung, nếu có thể. Nếu không, bạn có thể đạt đến max-specpdl-sizegiới hạn.

không giống như q1, tôi không biết "đường dẫn" đến giá trị

Ngoài ra, tôi có một danh sách lớn hơn có thể có "độ sâu" là 2 - 5 (theo độ sâu, ý tôi là các danh sách)

Với sự bất thường của cấu trúc dữ liệu này, tôi khuyên bạn nên làm phẳng danh sách trước khi tìm kiếm mọi thứ trong đó. Điều này sẽ đơn giản hóa đáng kể độ phức tạp của mã với chi phí là thời gian và không gian. Trong Emacs 27:

(setq x '(foo
          (bar (chocolate . "edible")
               (gold . "inedible"))
          (jar . "glass")))
(cadr (memq 'chocolate (flatten-tree x))) ; => "edible"

Đây là cách triển khai hiện tại của flatten-tree, trong trường hợp bạn đang sử dụng phiên bản Emacs cũ hơn:

(defun flatten-tree (tree)
  "Return a \"flattened\" copy of TREE.
In other words, return a list of the non-nil terminal nodes, or
leaves, of the tree of cons cells rooted at TREE.  Leaves in the
returned list are in the same order as in TREE.

\(flatten-tree \\='(1 (2 . 3) nil (4 5 (6)) 7))
=> (1 2 3 4 5 6 7)"
  (let (elems)
    (while (consp tree)
      (let ((elem (pop tree)))
        (while (consp elem)
          (push (cdr elem) tree)
          (setq elem (car elem)))
        (if elem (push elem elems))))
    (if tree (push tree elems))
    (nreverse elems)))

Ngoài ra, bạn có thể thực hiện tìm kiếm cây theo chiều sâu lặp đi lặp lại. Nó giao dịch các vấn đề đệ quy của Elisp cho các mã phức tạp hơn. Đây là một ví dụ về DFS trên HTML DOM được lấy từhttps://github.com/abo-abo/swiper/pull/1593#issuecomment-392587760 :

(defun counsel--firefox-bookmarks-libxml ()
  "Parse current buffer contents as Firefox HTML bookmarks.
Return list of propertized string candidates for
`counsel-firefox-bookmarks'.
Note: This function requires libxml2 support."
  ;; Perform iterative pre-order depth-first search instead of using
  ;; `dom.el' because the latter is new to Emacs 25 and uses recursion.
  (let ((stack (cddr (libxml-parse-html-region (point-min) (point-max))))
        cands)
    (while (let ((node (pop stack)))
             (if (eq (car-safe node) 'a)
                 (let* ((text (cl-caddr node))
                        (attrs (cadr node))
                        (href (cdr (assq 'href attrs)))
                        (tags (cdr (assq 'tags attrs))))
                   (unless (zerop (length href))
                     (push (counsel--firefox-bookmarks-cand href text tags)
                           cands)))
               (dolist (child (nreverse (cddr node)))
                 (when (consp child)
                   (push child stack))))
             stack))
    cands))

Trong trường hợp của bạn, whilevòng lặp cũng sẽ kết thúc tại vị trí của khóa mong muốn.

Ngoài ra, tôi khuyên bạn nên cấu trúc dữ liệu của mình sao cho thường xuyên hơn. ;)

Answer 2

Bạn có thể sử dụng macro nội trang let-alistđể truy cập giá trị từ danh sách lồng nhau, ví dụ:

(let-alist
    '((foo . ((bar . ((chocolate . "edible") (gold . "inedible")))
              (jar . "glass"))))
  .foo.bar.chocolate)
;; => "edible"

Và của bạn xkhông phải là alist, alist là một danh sách các cặp khóa-giá trị, tức là ((key1 . val1) (key2 . val2) ...),.