Hi,
I'm reading On Lisp and trying to extend the rfind-if that Paul
defines so that the test function has access to the whole subtree.
Here is what I've got so far...
(defun children (node)
"Returns the direct children of the specified node"
(remove-if-not #'listp node))
(defun rfind-if* (fn tree)
"return the first subtree for which (fn tree) returns true"
(if (funcall fn tree)
tree
(let ((nodes (children tree)))
(rfind-if* (find-if (lambda (x) (rfind-if* fn x)) nodes)))))
Each node in the tree has atoms (the node data and attributes) and
lists (the node's children). I'd like rfind-if* to return the first
subtree for which (fn tree) returns true.
This seems to work but I don't think its as good as it could be since
it calls rfind-if* more than it needs to (once inside the find-if to
get the first child we're interested in, and then again on the result
of this to get the subtree we're interested in.
How can I save the successful recursive calls so that I can return
them to the top-level?
Thanks,
Andy
··············@googlemail.com wrote:
> I'm reading On Lisp and trying to extend the rfind-if that Paul
> defines so that the test function has access to the whole subtree.
> (defun children (node)
> "Returns the direct children of the specified node"
> (remove-if-not #'listp node))
I would put this in fn (my pred).
What if you're looking for the highest leaf node?
This does the search breadth first
by doing the root node separately:
(defun find-subtree-if (pred tree)
"breadth-first search for first subtree such that (pred subtree)"
(let ((subtree (find-if pred tree)))
(or subtree
(find-if (lambda (x) (find-subtree-if pred x)) tree))))
(defun rfind-if* (pred tree)
"entry point for find-subtree-if"
(if (funcall pred tree)
tree
(find-subtree-if pred tree)))
--
Dan
www.prairienet.org/~dsb
Dan Bensen wrote:
> (defun find-subtree-if (pred tree)
> "breadth-first search for first subtree such that (pred subtree)"
> (let ((subtree (find-if pred tree)))
> (or subtree
> (find-if (lambda (x) (find-subtree-if pred x)) tree))))
Oops, it's even simpler.
(defun find-subtree-if (pred tree)
"breadth-first search for first subtree such that (pred subtree)"
(or (find-if pred tree)
(find-if (lambda (x) (find-subtree-if pred x)) tree)))
--
Dan
www.prairienet.org/~dsb
Dan Bensen wrote:
> (find-if (lambda (x) (find-subtree-if pred x)) tree)))
Sorry, that's not right.
It's returning the whole list.
--
Dan
www.prairienet.org/~dsb
Dan Bensen wrote:
>> (find-if (lambda (x) (find-subtree-if pred x)) tree)))
> Sorry, that's not right.
Okay, with your children function and my rfind-if* entry point:
(defun flat-1-children (list)
"remove atoms and flatten list by one level"
(apply #'append (children list)))
(defun find-subtree-if (pred tree)
(or (find-if pred tree)
(find-subtree-if pred (flat-1-children tree))))
--
Dan
www.prairienet.org/~dsb
Dan Bensen wrote:
> (defun find-subtree-if (pred tree)
> (or (find-if pred tree)
> (find-subtree-if pred (flat-1-children tree))))
Sorry about posting ad nauseum. Just one bugfix:
(defun find-subtree-if (pred tree)
(and tree
(or (find-if pred tree)
(find-subtree-if pred (flat-1-children tree)))))
--
Dan
www.prairienet.org/~dsb
In article <························@8g2000cwh.googlegroups.com>,
···············@googlemail.com" <··············@googlemail.com> wrote:
> Hi,
>
> I'm reading On Lisp and trying to extend the rfind-if that Paul
> defines so that the test function has access to the whole subtree.
> Here is what I've got so far...
>
>
> (defun children (node)
> "Returns the direct children of the specified node"
> (remove-if-not #'listp node))
>
> (defun rfind-if* (fn tree)
> "return the first subtree for which (fn tree) returns true"
> (if (funcall fn tree)
> tree
> (let ((nodes (children tree)))
> (rfind-if* (find-if (lambda (x) (rfind-if* fn x)) nodes)))))
This code won't work at all as written. The recursive call to rfind-if*
has the wrong number of arguments.
> Each node in the tree has atoms (the node data and attributes) and
> lists (the node's children). I'd like rfind-if* to return the first
> subtree for which (fn tree) returns true.
>
> This seems to work but I don't think its as good as it could be since
> it calls rfind-if* more than it needs to (once inside the find-if to
> get the first child we're interested in, and then again on the result
> of this to get the subtree we're interested in.
>
> How can I save the successful recursive calls so that I can return
> them to the top-level?
Why bother saving them? Just write it as a straightforward recursion.
Note that there are two base cases.
(defun rfind-if* (fn tree)
(cond ( (funcall fn tree) tree )
( (atom tree) nil )
(t (some (lambda (node) (rfind-if* fn node)) tree)))))
rg
On Mar 10, 7:47 am, Ron Garret <·········@flownet.com> wrote:
> Why bother saving them? Just write it as a straightforward recursion.
> Note that there are two base cases.
>
> (defun rfind-if* (fn tree)
> (cond ( (funcall fn tree) tree )
> ( (atom tree) nil )
> (t (some (lambda (node) (rfind-if* fn node)) tree)))))
Ah yes. I hadn't thought of using some. I think that makes the
difference. So some returns the result of calling the predicate,
whereas find-if returns the sequence item for which predicate is true.
Thanks for you help,
Andy
In article <························@q40g2000cwq.googlegroups.com>,
···············@googlemail.com" <··············@googlemail.com> wrote:
> On Mar 10, 7:47 am, Ron Garret <·········@flownet.com> wrote:
>
> > Why bother saving them? Just write it as a straightforward recursion.
> > Note that there are two base cases.
> >
> > (defun rfind-if* (fn tree)
> > (cond ( (funcall fn tree) tree )
> > ( (atom tree) nil )
> > (t (some (lambda (node) (rfind-if* fn node)) tree)))))
>
> Ah yes. I hadn't thought of using some. I think that makes the
> difference. So some returns the result of calling the predicate,
> whereas find-if returns the sequence item for which predicate is true.
Yep. Note that even if SOME were not already built in, it is trivial to
write:
(defun my-some (fn l) (or (funcall fn (car l)) (my-some fn (cdr l))))
If a built-in doesn't return the right thing and you can't find an
alternative, just roll your own. (Or use LOOP ;-) ;-) ;-)
> Thanks for you help,
You bet.
rg
On 10 Mar 2007 04:46:26 -0800, ···············@googlemail.com" <··············@googlemail.com> said:
| On Mar 10, 7:47 am, Ron Garret <·········@flownet.com> wrote:
|| Why bother saving them? Just write it as a straightforward recursion.
|| Note that there are two base cases.
||
|| (defun rfind-if* (fn tree)
|| (cond ( (funcall fn tree) tree )
|| ( (atom tree) nil )
|| (t (some (lambda (node) (rfind-if* fn node)) tree)))))
| Ah yes. I hadn't thought of using some. I think that makes the
| difference. So some returns the result of calling the predicate,
| whereas find-if returns the sequence item for which predicate is true.
I don't see that returning a (sub)tree (and note that if (FUNCALL FN
NIL) is true, that may redundantly walk the whole tree before
returning NIL). I don't think RFIND-IF* is quite suitable as a
predicate.
By the way, what exactly does "first subtree" mean in the formulation
of the problem? If (FUNCALL FN NODE) is true for any node in the
tree, why wouldn't the result be simply the root of the tree then?
---Vassil.
--
Is your code free of side defects?
Vassil Nikolov wrote:
> I don't see that returning a (sub)tree
It does return a subtree, from the line
> (cond ( (funcall fn tree) tree )
> (and note that if (FUNCALL FN NIL) is true, that may
> redundantly walk the whole tree before returning NIL).
Actually, the function returns as soon as it finds its first
non-nil value. FN has to keep returning nil for the function
to continue. Also, the walk isn't redundant. Each node
defines a distinct subtree that can have unique properties.
> I don't think RFIND-IF* is quite suitable as a predicate.
How long have you been using Lisp? Any function can serve as a
predicate by returning either nil for false or any other value for true.
That's common among dynamically typed languages, for instance Perl is
similar.
> By the way, what exactly does "first subtree" mean in the formulation
> of the problem? If (FUNCALL FN NODE) is true for any node in the
> tree, why wouldn't the result be simply the root of the tree then?
What's the connection between those two questions? You're right
that the term is ambiguous, which is why there are two solutions,
one depth-first and the other breadth-first. In general, FN might
return nil for any number of nodes, including the root, so only the
first non-nil value from FN triggers a non-nil value for rfind-if*.
--
Dan
www.prairienet.org/~dsb
> > I don't think RFIND-IF* is quite suitable as a predicate.
> How long have you been using Lisp? Any function can serve as a
> predicate by returning either nil for false or any other value for true.
Maybe that's not what you were saying, although it's hard to tell.
It is suitable, because it returns a non-nil subtree iff it finds one
that satisfies FN.
--
Dan
www.prairienet.org/~dsb
On Mar 11, 3:59 am, Vassil Nikolov <···············@pobox.com> wrote:
> I don't see that returning a (sub)tree (and note that if (FUNCALL FN
> NIL) is true, that may redundantly walk the whole tree before
> returning NIL). I don't think RFIND-IF* is quite suitable as a
> predicate.
I see your point here. If tree is nil, it should probably just return
nil straight away.
> By the way, what exactly does "first subtree" mean in the formulation
> of the problem? If (FUNCALL FN NODE) is true for any node in the
> tree, why wouldn't the result be simply the root of the tree then?
The use-case I was thinking of was this...
(setq tree '((forms
(form :id "001"
(textbox "Some question")
(textbox "Another Question"))
(form :id "002"
(choicefield 1 2 3)
(textbox "A final question"))))
(defun test (tree)
(cond ((atom tree) nil)
((equal (getf (cdr (node tree)) :id) "001") t)
(t nil)))
(rfind-if* 'test tree)
...which would return the first form with an :id attribute of "001" in
the test tree. Maybe I should say first, smallest subtree for which
the predicate returns true.
On 12 Mar 2007 05:14:02 -0700, ···············@googlemail.com" <··············@googlemail.com> said:
| On Mar 11, 3:59 am, Vassil Nikolov <···············@pobox.com> wrote:
|| I don't see that returning a (sub)tree (and note that if (FUNCALL FN
|| NIL) is true, that may redundantly walk the whole tree before
|| returning NIL). I don't think RFIND-IF* is quite suitable as a
|| predicate.
| I see your point here. If tree is nil, it should probably just return
| nil straight away.
Well, my point is that functions such as FIND, FIND-IF, RFIND-IF,
etc. return NIL in two cases: (a) it matches and is found, _or_ (b)
nothing matches and thus nothing is found. In typical predicate
usage, this makes them deficient as predicates; compare MEMBER (which
returns NIL if, and only if, nothing matches).
(Or, as the King says to Alice, she must have very good eyes to be
able to see nobody at a great distance...)
|| By the way, what exactly does "first subtree" mean in the formulation
|| of the problem? If (FUNCALL FN NODE) is true for any node in the
|| tree, why wouldn't the result be simply the root of the tree then?
| The use-case I was thinking of was this...
| (setq tree '((forms
| (form :id "001"
| (textbox "Some question")
| (textbox "Another Question"))
| (form :id "002"
| (choicefield 1 2 3)
| (textbox "A final question"))))
| (defun test (tree)
| (cond ((atom tree) nil)
| ((equal (getf (cdr (node tree)) :id) "001") t)
| (t nil)))
| (rfind-if* 'test tree)
| ...which would return the first form with an :id attribute of "001" in
| the test tree. Maybe I should say first, smallest subtree for which
| the predicate returns true.
What about some simpler cases, such as, with SYMBOLP as the
predicate, searching (1 (2 3 (4 a)) ...)? Or, for that matter,
(1 (2 3 (4 nil)) (5 a) ...)?
---Vassil.
--
Definitely worth seeing: "Das Leben der Anderen" ("The Lives of Others").