tag:blogger.com,1999:blog-10770855.post112110628562644507..comments2024-03-28T03:20:57.393-04:00Comments on The Little Calculist: Deriving an Efficient Tree Traversal, Part IDave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-10770855.post-1121182155032756512005-07-12T11:29:00.000-04:002005-07-12T11:29:00.000-04:00FWIW, I just noticed in the CSS spec that CSS sibl...FWIW, I just noticed in the <A HREF="http://www.w3.org/TR/REC-CSS2/selector.html#adjacent-selectors" REL="nofollow">CSS spec</A> that CSS sibling selectors don't necessitate graph traversal: they're only for adjacent siblings, and they're ordered. That makes it easier. Ugly, but easier.Dave Hermanhttps://www.blogger.com/profile/00405190527081772997noreply@blogger.comtag:blogger.com,1999:blog-10770855.post-1121174045464385602005-07-12T09:14:00.000-04:002005-07-12T09:14:00.000-04:00Oops, right you are. Thanks!Oops, right you are. Thanks!Dave Hermanhttps://www.blogger.com/profile/00405190527081772997noreply@blogger.comtag:blogger.com,1999:blog-10770855.post-1121172977643646172005-07-12T08:56:00.000-04:002005-07-12T08:56:00.000-04:00it's actually not hard to fix; just change the rec...<I>it's actually not hard to fix; just change the recursion to<BR/><BR/>(append (select* (children t) (cdr path)) (select* (children t) path))</I><BR/><BR/>I'm weirder than you think; I actually tried that before posting. Doing it that way changes the output list into the <I>children</I> of matching trees, not that tree that matches the last tag (as the function as-is returns); to fix that the easiest way I came up with was to treat the path as a nonempty list and return the tree if it matches the last tag in the path. A bit nasty, but doable.Jacob Matthewshttps://www.blogger.com/profile/01440842967865877789noreply@blogger.comtag:blogger.com,1999:blog-10770855.post-1121145782635047682005-07-12T01:23:00.000-04:002005-07-12T01:23:00.000-04:00You win the prize for finding the first problem! B...You win the prize for finding the first problem! Basically, the semantics I've implemented is that the "descendant" relation is reflexive, i.e., a node is its own descendant. It would probably make more sense not to be reflexive, but it's actually not hard to fix; just change the recursion to<BR/><BR/>(append (select* (children t) (cdr path)) (select* (children t) path))<BR/><BR/>But I think the bigger problem is of repeated nodes in the output. You probably don't want to generate a list with duplicates, but removing duplicates is inefficient. (In this simplified example, if you remove the reflexivity, I think it might not come up, but in general, i.e. with real CSS selectors, it will.)<BR/><BR/>You could use an efficient set representation like that crazy union-find stuff, but a better way might be to visit every node just once, collecting up the set of all tests for each node and try them in order, stopping as soon as you find one that accepts the node.<BR/><BR/>This is starting to sound more like graph traversal... which full CSS selectors are anyway, since you have to do things like test siblings. Blech.<BR/><BR/>(BTW, you <B>are</B> weird for finding this bug in the final program. I'd found it in the original program. I hardly thought anyone could even read the final one...)Dave Hermanhttps://www.blogger.com/profile/00405190527081772997noreply@blogger.comtag:blogger.com,1999:blog-10770855.post-1121144497176740862005-07-12T01:01:00.000-04:002005-07-12T01:01:00.000-04:00Great series, thanks for writing this. One thing: ...Great series, thanks for writing this. One thing: it seems as though your program in all its forms collapses any number of repetitions of any tag. For instance:<BR/><BR/>> (select (make-tree 'a (list (make-tree 'b '()))) '(a a a b))<BR/>(#(struct:tree b ()))<BR/>> (select (make-tree 'a (list (make-tree 'b '()))) '(a b))<BR/>(#(struct:tree b ()))<BR/><BR/>That seems totally weird to me, but maybe it's the intended behavior. Anyway, fixing it to do what I'd expect (i.e. make repetitions of a tag in a path require sequential occurences of the tag to appear in the path) is a bit of extra work, and given all the transformations you're doing maybe you just didn't want to make the program any more complicated than it already is?<BR/><BR/>(Oddly enough I noticed this behavior by studying the <I>final</I> program, not the first one; I guess I'm just weird that way.)Jacob Matthewshttps://www.blogger.com/profile/01440842967865877789noreply@blogger.com