Assoc in einem verschachtelten Alist

Nov 19 2020

Ich habe die folgende verschachtelte Liste:

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

Wie kann man Zutritt bekommen (chocolate . "edible")?

Ich habe diese und diese Frage gelesen

Aber im Gegensatz zu q1 kenne ich den "Pfad" zum Wert nicht und im Gegensatz zu q2 möchte ich eine Elisp-Implementierung. Außerdem habe ich eine größere Liste, die eine "Tiefe" von 2 bis 5 haben kann (mit Tiefe meine ich Alisten in Alisten).

Bisher konnte ich mir Folgendes ausdenken:

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

Es ist offensichtlich, dass dieser Code nur funktioniert, solange der Wert keine Liste von Alisten wie ist (bar . ((..))

Wie kann ich mit Vanilla Elisp (ohne CL-Emulation) auf einen Wert in einem verschachtelten Alist zugreifen? Oder sollte ich aufgeben und die CL-API installieren und q2 ausprobieren?

Die Syntax, die ich suche, ist so etwas wie (func key list)

ps: Ich bin ziemlich neu bei Emacs, daher verpasse ich wahrscheinlich eine praktische Funktion.

Antworten

3 Basil Nov 19 2020 at 22:55

Ich habe die folgende verschachtelte Liste:

Das Beispiel zeigt keinen echten Alist, da sein erstes Element fookeine Nachteile-Zelle ist. Ich würde es persönlich einen Baum nennen. Funktionen wie assoc-stringkönnen damit umgehen, andere mögen solche Elemente ignorieren, aber im Allgemeinen erwarten alistische Funktionen, dass jedes Element ein Nachteil für ein Auto und eine CDR ist. Siehe (info "(elisp) Lists")und seine Unterknoten.

Bisher konnte ich mir Folgendes ausdenken:

Elisp handhabt die Rekursion nicht sehr effizient, daher würde ich empfehlen, sie nach Möglichkeit generell zu vermeiden. Sie können sonst max-specpdl-sizeGrenzen überschreiten.

Im Gegensatz zu q1 kenne ich den "Pfad" zum Wert nicht

Außerdem habe ich eine größere Liste, die eine "Tiefe" von 2 bis 5 haben kann (mit Tiefe meine ich Alisten in Alisten).

Angesichts der Unregelmäßigkeit dieser Datenstruktur würde ich empfehlen, die Liste zuerst zu reduzieren, bevor Sie nachschlagen. Dies sollte die Komplexität des Codes auf Kosten von Zeit und Raum erheblich vereinfachen. In Emacs 27:

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

Hier ist die aktuelle Implementierung von flatten-tree, falls Sie eine ältere Version von Emacs verwenden:

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

Alternativ können Sie eine iterative Tiefensuche durchführen. Es tauscht die Rekursionsprobleme von Elisp gegen komplexeren Code. Hier ist ein Beispiel für DFS in einem HTML-DOM aushttps://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))

In Ihrem Fall würde die whileSchleife zusätzlich an der Stelle des gewünschten Schlüssels enden.

Alternativ würde ich empfehlen, Ihre Daten so zu strukturieren, dass sie regelmäßiger sind. ;)

xuchunyang Nov 20 2020 at 00:30

Sie können das integrierte Makro verwenden, let-alistum auf den Wert einer verschachtelten Liste zuzugreifen, z.

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

Und Ihr xist kein Alist, Alist ist eine Liste von Schlüssel-Wert-Paaren, dh ((key1 . val1) (key2 . val2) ...).