Topic: Nested assoc list accessor

[Grrr1337]

Hi fellow list manipulators,
I wanted to leave this idea I had:

Code - Auto/Visual Lisp: [Select]

1. ; Nested assoc list accessor
2. ; assocL - list of given accessors
3. ; L - Nested assoc list
4. (defun aassoc ( assocL L / r )
5.   (vl-every (function (lambda (x) (if r (setq r (cdr (assoc x r))) (setq r (cdr (assoc x L)))))) assocL) r
6. ); defun aassoc

Example:

Code - Auto/Visual Lisp: [Select]

1. ; Given a List:
2. (setq L
3.   '(
4.     ("A"
5.       ("AA" ("AA1" "1aa1") ("AA2" "2aa2") ("AA3" "3aa3") )
6.       ("AB" ("AB1" "1ab1") ("AB2" "2ab2") ("AB3" "3ab3") )
7.     )
8.     ("B"
9.       ("BA" ("BA1" "1ba1") ("BA2" "2ba2") ("BA3" "3ba3") )
10.       ("BB" ("BB1" "1bb1") ("BB2" "2bb2") ("BB3" "3bb3") )
11.     )
12.     ("C"
13.       ("CA" ("CA1" "1ca1") ("CA2" "2ca2") ("CA3" "3ca3") )
14.       ("CB" ("CB1" "1cb1") ("CB2" "2cb2") ("CB3" "3cb3") )
15.     )
16.   ); list
17. ); setq L
18.  
19. ; Results:
20. _$ (aassoc '("B" "BA" "BA2") L) -> ("2ba2")
21. _$ (aassoc '("C" "BA" "BA2") L) -> nil
22. _$ (aassoc '("C" "CB" "CB3") L) -> ("3cb3")
23. _$ (aassoc '("C" "CB") L) -> (("CB1" "1cb1") ("CB2" "2cb2") ("CB3" "3cb3"))

I'm not sure yet where I'm gonna use it, but you might have.
Feel free to share alternatives/opinions.

[Lee Mac]

Nice one Grrr1337 - I like that you avoided recursion even though the problem looks to be recursive on the surface.

Here's another variation:

Code - Auto/Visual Lisp: [Select]

1. (defun nassoc ( k l )
2.     (cond
3.         (   (not l) l)
4.         (   (cdr k) (nassoc (cdr k) (cdr (assoc (car k) l))))
5.         (   (cdr (assoc (car k) l)))
6.     )
7. )

[roy_043]

Code - Auto/Visual Lisp: [Select]

1. (defun NestedAssoc (keyLst lst)
2.   (repeat (length keyLst)
3.     (setq lst (cdr (assoc (car keyLst) lst)))
4.     (setq keyLst (cdr keyLst))
5.   )
6.   lst
7. )

[Grrr1337]

Thanks for the thoughts, guys!
I was really wondering about the recursive approach - although in my head was the iterating with (vl-every).

[ziele_o2k]

BTW, Lee's and roy's routines are a little bit faster

Code - Auto/Visual Lisp: [Select]

1. (repeat 20
2.   (setq time (getvar "MilliSecs"))
3.   (repeat 10000
4.     (aassoc '("B" "BA" "BA2") L)
5.   )
6.   (print (* (- (getvar "MilliSecs") time)1E-3) )
7.   (princ)
8. )
9. 0.141 0.156 0.171 0.156 0.203 0.203 0.218 0.203 0.171 0.156 0.203 0.172 0.156 0.156 0.171 0.172 0.156 0.156 0.156 0.156
10. (repeat 20
11.   (setq time (getvar "MilliSecs"))
12.   (repeat 10000
13.     (nassoc '("B" "BA" "BA2") L)
14.   )
15.   (print (* (- (getvar "MilliSecs") time)1E-3) )
16.   (princ)
17. )
18. 0.094 0.094 0.14 0.078 0.125 0.093 0.125 0.125 0.109 0.11 0.093 0.094 0.078 0.093 0.078 0.094 0.078 0.094 0.078 0.093
19. (repeat 20
20.   (setq time (getvar "MilliSecs"))
21.   (repeat 10000
22.     (NestedAssoc '("B" "BA" "BA2") L)
23.   )
24.   (print (* (- (getvar "MilliSecs") time)1E-3) )
25.   (princ)
26. )
27. 0.093 0.078 0.156 0.109 0.11 0.14 0.109 0.109 0.094 0.094 0.093 0.094 0.078 0.078 0.094 0.094 0.093 0.094 0.093 0.11
28.  

[Lee Mac]

Another:

Code - Auto/Visual Lisp: [Select]

1. (defun nassoc-while ( k l )
2.     (while (and (setq l (cdr (assoc (car k) l))) (setq k (cdr k))))
3.     l
4. )

[ziele_o2k]

Another:

Code - Auto/Visual Lisp: [Select]

1. (defun nassoc-while ( k l )
2.     (while (and (setq l (cdr (assoc (car k) l))) (setq k (cdr k))))
3.     l
4. )

Fastest one

Code - Auto/Visual Lisp: [Select]

1. 0.062 0.062 0.062 0.078 0.063 0.062 0.094 0.078 0.078 0.078 0.078 0.062 0.063 0.078 0.062 0.062 0.063 0.062 0.078 0.063

[Grrr1337]

Logically (foreach) is the one left:

Code - Auto/Visual Lisp: [Select]

1. ; (nassoc-foreach '("B" "BA" "BA2") L)
2. (defun nassoc-foreach ( k L )
3.   (foreach x k (setq L (cdr (assoc x L))) )
4. )

I guess ziele_o2k should do the speed test on his machine (so the speed would be compared on the same computer).

[ziele_o2k]

(...)
I guess ziele_o2k should do the speed test on his machine (so the speed would be compared on the same computer).

Results similar to nassoc-while:

Code - Auto/Visual Lisp: [Select]

1. 0.062 0.078 0.063 0.078 0.078 0.062 0.078 0.062 0.063 0.062 0.063 0.046 0.062 0.063 0.062 0.078 0.047 0.047 0.062 0.047

[Lee Mac]

The efficiency will obviously be dependent on the length of the key list argument, as those solutions which iterate over the entirety of the key list will be performing assoc queries on a null list if one of the keys is not found.

[Grrr1337]

The efficiency will obviously be dependent on the length of the key list argument, as those solutions which iterate over the entirety of the key list will be performing assoc queries on a null list if one of the keys is not found.

Yup, thats why unstoppable iterators like foreach mapcar repeat, although perform faster (cause the lack of a test function expr to mid-stop the iteration)
iterators like while vl-some vl-every, are more efficient - so they won't process the whole list (but will require the test function expr).

Just to clarify for anyone.