Recursive Assoc and Subst

[jccoyle5WQ9G]

 Hey all, I've learned a lot from this forum, hoping to learn just a bit more. I've been working on some general routines for drilling into nested association lists of indeterminate complexity, and it seemed like a good excuse to learn a bit about recursion. So far I've gotten a recursive (assoc) to work:

; given a list of keys ordered from the "outside" of a nested assoc list to the "inside", return the (assoc) of the last given key
(defun jc:assocr (keys lst / nxt nxtkeys)
	(if (setq nxt (assoc (car keys) lst))
		(if (setq nxtkeys (cdr keys))
			(jc:assocr nxtkeys (cdr nxt))
			nxt))
)

Now I'd like to get a recursive subst to work, and I'm close, but not quite there.

; subst-r performs a subst on a nested association list.
; given a list of keys, a new value, and a list, it will walk along the tree until runs out of keys, then it will assign the last key the new value, and return the whole list with the new substitution.
(defun subst-r (keys val lst)
	(defun subst-f (keys val lst / nxt nxtkeys newsub)
		(if (setq nxt (assoc (setq key (car keys)) lst))
			(if (setq keys (cdr keys))
				(cons key (subst-f keys val (cdr nxt)))
				(subst (cons key val) nxt lst))))
	(subst (subst-f keys val lst) (assoc (car keys) lst) lst)
)

As you can see, I was able to get a recursive function to return all but the top level of the list, with the new value substituted in the appropriate level, but I had to wrap the recursive function in order to get the rest of it. I think it could be done by using a global variable to determine whether it's the first level of recursion and rearranging the logic slightly to get that highest-level (subst) into a conditional in subst-f, but that seems inelegant.

The idea is to use nested lists to store and modify per-layout data, i.e., a list of sheet names, each associated with a list of properties I'm using elsewhere in my routines, so that I can e.g. find the manual override for the number assigned to new rev clouds on layout E-100 with a quick (cdr (jc:assocr '("E-100" "RevCloudOverride") *layout_data_list*)), or  change its value to "3" with (setq *layout_data_list* (subst-r '("E-100" "RevCloudOverride") "3" *layout_data_list*)).

Thanks!

[pbejse]

Can you show us the elements of list *layout_data_list* ? or anything similar

[martti.halminen]

Why are you using SUBST? If these are true association lists (accessed only by ASSOC, and only the first occurrence of a key is significant), it is far easier to modify the values by just consing a new key - value pair in front of the list.

-- 

[martti.halminen]

Here is an example of adding data to nested association lists by CONS.

- not much tested, may miss some cases.

- for a long-running application might need some kind of garbage-collecting arrangement, too.

(defun set-alist* (keys new data)
  ;; returns a nested assoc.list with the new item added at last key in the chain
  (cond
    ((null (cdr keys)) (cons (cons (car keys) new) data))
    ((null (assoc (car keys) data)) (cons (cons (car keys)
                                                (set-alist* (cdr keys) new nil))
                                          data))
    (T (cons (cons (car keys) (set-alist* (cdr keys) new (cdr (assoc (car keys) data))))
             data))))

-- 

[jccoyle5WQ9G]

Sorry for the radio silence, things got busy and now they're not. So:

---

@pbejse wrote:

Can you show us the elements of list *layout_data_list* ? or anything similar

---

Basically something like this:

'( (Key1 ((SubKey1 . Val1) (Subkey2 . Val2)))
   (Key2 ((SubKey1 . Val1) (Subkey2 . Val2))) )

with the possibility of Val1/Val2 holding assoc lists. So, you'd call it with a key list '(Key2 Subkey1) to get the second instance of Val1

---

@martti.halminenwrote:

Here is an example of adding data to nested association lists by CONS.

- not much tested, may miss some cases.

- for a long-running application might need some kind of garbage-collecting arrangement, too.

(defun set-alist* (keys new data)
  ;; returns a nested assoc.list with the new item added at last key in the chain
  (cond
    ((null (cdr keys)) (cons (cons (car keys) new) data))
    ((null (assoc (car keys) data)) (cons (cons (car keys)
                                                (set-alist* (cdr keys) new nil))
                                          data))
    (T (cons (cons (car keys) (set-alist* (cdr keys) new (cdr (assoc (car keys) data))))
             data))))

-- 

Thanks, I'll pick this apart and mark as solution when I've got it figured it out. As for the question of why subst instead of consing a new key, I don't have a good answer! I guess the idea was to ensure some garbage collection, and I was also not operating under the assumption that a key would only appear once, but my code as it's currently written would definitely only catch the first instance of a given key anyways.

[martti.halminen]

A little warning about this structure: nested association lists only work reliably if they are only accessed and modified as a nested structure.

Most AutoLISP list operations don't preserve list identity, so if you have several places pointing to a list, modifying it via one way will break the connection through any other way.

_$ (setq aa '(1 2 3))
(1 2 3)
_$ (setq al1 (cons 'a aa))
(A 1 2 3)
_$ (setq aa (subst 5 2 aa))
(1 5 3)
_$ al1
(A 1 2 3)

-- 

[_gile]

Hi,

Assuming the list format looks like this:

(setq lst '(
	    (1 . "a")
	    (2 ((21 . "b") (22 . "c")))
	    (3 ((31 . "d") (32 ((321 . "x") (322 . "y")))))
	   )
)

The routines could be:

(defun recassoc (keys lst / sub)
  (cond
    ((null lst) nil)
    ((null (cdr keys)) (assoc (car keys) lst))
    ((and (setq sub (assoc (car keys) lst))
	  (listp (cadr sub))
     )
     (recassoc (cdr keys) (cadr sub))
    )
  )
)

(defun recsubst	(keys val lst)
  (cond
    ((null lst) nil)
    ((null (cdr keys))
     (subst (cons (car keys) val) (assoc (car keys) lst) lst)
    )
    ((equal (car keys) (caar lst))
     (if (listp (cdar lst))
       (cons (cons (caar lst) (list (recsubst (cdr keys) val (cadar lst)))) (cdr lst))
       lst
     )
    )
    (T (cons (car lst) (recsubst keys val (cdr lst))))
  )
)

But, in my opinion, the list structure should be like this:

(setq lst '(
	    (1 . "a")
	    (2 (21 . "b") (22 . "c"))
	    (3 (31 . "d") (32 (321 . "x") (322 . "y")))
	   )
)

So that you can always use (cdr (assoc ...)) instead of (cdr (assoc ...)) for dotted pairs and (cadr (assoc ...)) for lists.

This will also allow to avoid superfluous acces and creation of sublists (see the red symbols in the upper function).

(defun recassoc (keys lst / sub)
  (cond
    ((null lst) nil)
    ((null (cdr keys)) (assoc (car keys) lst))
    ((and (setq sub (assoc (car keys) lst))
	  (listp (cdr sub))
     )
     (recassoc (cdr keys) (cdr sub))
    )
  )
)

(defun recsubst	(keys val lst)
  (cond
    ((null lst) nil)
    ((null (cdr keys))
     (subst (cons (car keys) val) (assoc (car keys) lst) lst)
    )
    ((equal (car keys) (caar lst))
     (if (listp (cdar lst))
       (cons (cons (caar lst) (recsubst (cdr keys) val (cdar lst))) (cdr lst))
       lst
     )
    )
    (T (cons (car lst) (recsubst keys val (cdr lst))))
  )
)