Association trees

I'm sure someone has done this before, but i haven't seen it. Originally developed in scheme, this implementation is for lisp. It ought be jazzed up with support for keywords.

The idea is, rather than a simple assoc list,

((a . 1) (b . 2) (c . 3))

use a full tree representation, where the children may be association lists themselves. Like this:

(tree-assoc '(a b c) ((a (b (c . 1) (d . 2))))) -> (c . 1)


The implementation is simple, just recur until the path runs out.

(defun tree-assoc (path tree)
  (cond
    ((null path) ())
    ((null (cdr path)) (assoc (car path) tree))
    (t (let ((subtree (assoc (car path) tree)))
  (and subtree (tree-assoc (cdr path) (cdr subtree)))))))

The original motivation came from a DnD character builder. I was running into trouble, because i wanted to use the key 'bonus far to often. The tree structure lets me segregate keys, so i can use duplicate keys. The real power became apparent when i wrote tree-insert. This gives a nice, simple, queryable representation of hierarchical data.

(defun tree-insert (path tree item)
  (cond
    ((null path) item)
    ((not tree) (build-path path item))
    (t (let ((node (assoc (car path) tree)))
  (acons (car path)
  (if node
      (tree-insert (cdr path) (cdr node) item)
      (build-path (cdr path) item))
  (remove (car path) tree :key #'car))))))

(defun build-path (path item)
  (if (null path) 
      item
      (acons (car path) (build-path (cdr path) item) ())))