Subject: Re: Another "gotta be a better way" from <gasp> The Real World of Lisp
From: (Rob Warnock)
Date: Sun, 22 Apr 2007 20:14:30 -0500
Newsgroups: comp.lang.lisp
Message-ID: <>
Ken Tilton  <> wrote:
| Your mission, should you blah blah blah, is to take a list of field 
| outputs (again, a list whose last element is data, the rest a path)
| and collapse them into the implied tree(s):
| #+test
| (time (tree-ify '((x one a 1)(x two a 2)(x three 42)
|                   (y two b 3)(x one b 4))))
| ;; 39 cons cells
| ;; -> ((Y (TWO (B 3))) (X (THREE 42) (TWO (A 2)) (ONE (B 4) (A 1))))

Not sure I can contribute any code more useful than the other branch
of this thread [some cute stuff in there], but one thought comes to
mind from the problem statement: If you consider each element of an
input "list of field outputs" to be a "character" [yes, I know it isn't],
then this task smells an awful lot like inserting into a "trie", and
some study of trie algorithms might prove useful.

Oh, and there was some discussion that might be related to this
back in August '02, in the thread "Q: modularity problem with CLOS".
Tim Bradshaw's "generic trees" & INTERN-SEQUENCE-IN-GT come to mind in
particular, see <>, et seq in which Rahul
Jain says that GTs are really tries, or maybe "discrimination nets".
["Ternary search trees" were also mentioned.]

That's all I've got. Sorry it's not more...


Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607