Monday, October 8, 2007

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