Assoc w zagnieżdżonej liście

Question

Mam następującą zagnieżdżoną listę:

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

Jak uzyskać wpis (chocolate . "edible")?

Przeczytałem to pytanie i to

Ale w przeciwieństwie do q1, nie znam „ścieżki” do wartości, aw przeciwieństwie do q2, chciałbym implementację Elisp. Mam również większą listę, która może mieć „głębokość” 2–5 (przez głębokość mam na myśli listy na listach)

Do tej pory udało mi się ugotować:

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

Jest oczywiste, że ten kod działa tylko wtedy, gdy wartość nie jest listą list, takich jak (bar . ((..))

Jak mogę uzyskać dostęp do wartości w zagnieżdżonej liście za pomocą vanilla Elisp (bez emulacji CL)? Czy powinienem się poddać i zainstalować CL api i wypróbować Q2?

Składnia, której szukam, jest podobna (func key list)

ps: Jestem całkiem nowy w Emacsie, więc prawdopodobnie brakuje mi wygodnej funkcji.

Answer 1

Mam następującą zagnieżdżoną listę:

Przykład nie pokazuje prawdziwej listy, ponieważ jej pierwszy element foonie jest komórką wad. Osobiście nazwałbym to drzewem. Funkcje takie jak assoc-stringmogą sobie z tym poradzić, inne mogą ignorować takie elementy, ale generalnie funkcje alist oczekują, że każdy element będzie wadą samochodu i cdr. Zobacz (info "(elisp) Lists")i jego podwęzły.

Do tej pory udało mi się ugotować:

Elisp nie radzi sobie zbyt wydajnie z rekurencją, więc w miarę możliwości zalecałbym jej unikanie. W przeciwnym razie możesz osiągnąć max-specpdl-sizelimity.

w przeciwieństwie do q1, nie znam „ścieżki” do wartości

Mam również większą listę, która może mieć „głębokość” 2–5 (przez głębokość mam na myśli listy na listach)

Biorąc pod uwagę nieregularność tej struktury danych, zalecałbym najpierw spłaszczenie listy przed sprawdzeniem jej zawartości. Powinno to znacznie uprościć złożoność kodu kosztem czasu i miejsca. W Emacs 27:

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

Oto aktualna implementacja flatten-tree, na wypadek gdybyś korzystał ze starszej wersji Emacsa:

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

Alternatywnie, możesz przeprowadzić iteracyjne przeszukiwanie w głąb drzewa. Wymienia problemy związane z rekurencją Elisp na bardziej złożony kod. Oto przykład DFS w HTML DOM wzięty zhttps://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))

W twoim przypadku whilepętla dodatkowo zakończyłaby się w miejscu żądanego klucza.

Alternatywnie radziłbym uporządkować dane w taki sposób, aby były bardziej regularne. ;)

Answer 2

Możesz użyć wbudowanego makra, let-alistaby uzyskać dostęp do wartości z zagnieżdżonej listy, np.

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

A twoja xnie jest listą, alist to lista par klucz-wartość, tj ((key1 . val1) (key2 . val2) ...).