Ken Tilton <email@example.com> 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):
| (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 <news:firstname.lastname@example.org>, 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 <email@example.com>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607