Assoc in un elenco annidato

Question

Ho il seguente elenco annidato:

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

Come posso entrare (chocolate . "edible")?

Ho letto questa domanda e questa

Ma a differenza di q1, non conosco il "percorso" del valore e, a differenza di q2, vorrei un'implementazione di Elisp. Inoltre, ho una lista più grande che può avere una "profondità" di 2 - 5 (per profondità intendo le liste nelle liste)

Finora questo è quello che sono riuscito a inventare:

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

È ovvio che questo codice funziona solo fintanto che il valore non è un elenco di elenchi come (bar . ((..))

Come posso accedere a un valore in un elenco annidato con vanilla Elisp (senza emulazione CL)? O dovrei rinunciare e installare l'API CL e provare q2?

La sintassi che sto cercando è qualcosa di simile (func key list)

ps: Sono abbastanza nuovo in Emacs quindi probabilmente mi sto perdendo una comoda funzione.

Answer 1

Ho il seguente elenco annidato:

L'esempio non mostra una lista reale, perché il suo primo elemento, foonon è una cella contro. Personalmente lo chiamerei un albero. Funzioni come assoc-stringpossono gestirlo, altre possono ignorare tali elementi, ma in generale le funzioni di elenco si aspettano che ogni elemento sia un contro con un'auto e un cdr. See (info "(elisp) Lists")e i suoi sottonodi.

Finora questo è quello che sono riuscito a inventare:

Elisp non gestisce la ricorsione in modo molto efficiente, quindi consiglierei di evitarla in generale, se possibile. Altrimenti potresti raggiungere i max-specpdl-sizelimiti.

a differenza di q1, non conosco il "percorso" del valore

Inoltre, ho una lista più grande che può avere una "profondità" di 2 - 5 (per profondità intendo le liste nelle liste)

Data l'irregolarità di questa struttura dati, consiglierei di appiattire l'elenco prima di cercare le cose al suo interno. Ciò dovrebbe semplificare notevolmente la complessità del codice al costo di un po 'di tempo e di spazio. In Emacs 27:

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

Ecco l'implementazione corrente di flatten-tree, nel caso in cui tu sia su una versione precedente di Emacs:

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

In alternativa, è possibile eseguire una ricerca iterativa su albero in profondità. Scambia i problemi di ricorsione di Elisp con codice più complesso. Ecco un esempio di DFS su un DOM HTML tratto dahttps://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))

Nel tuo caso, il whileciclo terminerebbe inoltre sulla posizione della chiave desiderata.

In alternativa, consiglierei di strutturare i dati in modo che siano più regolari. ;)

Answer 2

È possibile utilizzare la macro incorporata let-alistper accedere al valore da un elenco annidato, ad es.

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

E il tuo xnon è un elenco, l'elenco è un elenco di coppie chiave-valore, ad esempio ((key1 . val1) (key2 . val2) ...).