Assoc dalam daftar bertingkat

Question

Saya memiliki daftar bersarang berikut:

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

Bagaimana bisa masuk (chocolate . "edible")?

Saya membaca pertanyaan ini & dan ini

Tapi tidak seperti q1, saya tidak tahu "jalur" ke nilai, dan tidak seperti, q2, saya ingin implementasi Elisp. Selain itu, saya memiliki daftar yang lebih besar yang dapat memiliki "kedalaman" 2 - 5 (maksud saya adalah daftar dalam daftar)

Sejauh ini, inilah yang bisa saya masak:

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

Jelas bahwa kode ini hanya berfungsi selama nilainya bukan daftar daftar sejenis (bar . ((..))

Bagaimana saya dapat mengakses nilai dalam daftar bersarang dengan vanilla Elisp (tanpa emulasi CL)? Atau haruskah saya menyerah dan menginstal api CL dan mencoba q2?

Sintaks yang saya cari adalah seperti (func key list)

ps: Saya cukup baru mengenal Emacs jadi saya mungkin kehilangan fungsi yang nyaman.

Answer 1

Saya memiliki daftar bersarang berikut:

Contoh tidak menunjukkan daftar nyata, karena elemen pertamanya foo,, bukan sel kontra. Saya pribadi menyebutnya pohon. Fungsi seperti assoc-stringdapat menangani ini, yang lain mungkin mengabaikan elemen tersebut, tetapi secara umum fungsi alist mengharapkan setiap elemen menjadi kontra dengan mobil dan cdr. Lihat (info "(elisp) Lists")dan subnodenya.

Sejauh ini, inilah yang bisa saya masak:

Elisp tidak menangani rekursi dengan sangat efisien, jadi saya sarankan untuk menghindarinya secara umum, jika memungkinkan. Anda bisa saja mencapai max-specpdl-sizebatas.

tidak seperti q1, saya tidak tahu "jalur" ke nilai

Selain itu, saya memiliki daftar yang lebih besar yang dapat memiliki "kedalaman" 2 - 5 (maksud saya adalah daftar dalam daftar)

Mengingat ketidakteraturan struktur data ini, saya sarankan untuk meratakan daftar terlebih dahulu sebelum mencari di dalamnya. Ini akan sangat menyederhanakan kompleksitas kode dengan mengorbankan beberapa waktu dan ruang. Dalam Emacs 27:

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

Berikut implementasi saat ini flatten-tree, jika Anda menggunakan Emacs versi lama:

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

Atau, Anda dapat melakukan penelusuran pohon kedalaman-pertama yang berulang. Ini memperdagangkan masalah rekursi Elisp untuk kode yang lebih kompleks. Berikut contoh DFS pada HTML DOM yang diambil darihttps://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))

Dalam kasus Anda, whileloop tambahan akan berhenti di lokasi kunci yang diinginkan.

Atau, saya akan merekomendasikan untuk menyusun data Anda sedemikian rupa sehingga lebih teratur. ;)

Answer 2

Anda dapat menggunakan makro bawaan let-alistuntuk mengakses nilai dari daftar bersarang, misalnya,

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

Dan Anda xbukan alist, alist adalah daftar key-value pair, yaitu ((key1 . val1) (key2 . val2) ...).