Could you please do my homework for me? The teacher wants us to convert
this to LOOP /and/ make it clearer yet as efficient as the recursive
version. I can't see a way (no downfrom for lists), but maybe I am
missing something. Here is the recursive version:
(defun prior-sib-if (self list &optional (test-fn #'true-that))
"Find nearest preceding sibling passing TEST-FN"
(labels ((check-priors (sibs)
(if (eql self (first sibs))
nil
(or (check-priors (rest sibs))
(when (funcall test-fn (first sibs))
(first sibs))))))
(check-priors list)))
thanks,
<i better not leave my name, the teacher reads this group>
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
Kenny Tilton <·······@nyc.rr.com> writes:
> Could you please do my homework for me? The teacher wants us to
> convert this to LOOP /and/ make it clearer yet as efficient as the
> recursive version. I can't see a way (no downfrom for lists), but
> maybe I am missing something. Here is the recursive version:
>
> (defun prior-sib-if (self list &optional (test-fn #'true-that))
> "Find nearest preceding sibling passing TEST-FN"
> (labels ((check-priors (sibs)
> (if (eql self (first sibs))
> nil
> (or (check-priors (rest sibs))
> (when (funcall test-fn (first sibs))
> (first sibs))))))
> (check-priors list)))
>
> thanks,
>
> <i better not leave my name, the teacher reads this group>
Not tested but I think this does what you want. (You can test it
yourself--you should be doing your own homework anyway. ;-))
(defun prior-sib-if (self list &optional (test-fn #'true-that))
"Find nearest preceding sibling passing TEST-FN"
(loop with sib = nil
for node in list
when (eql node self) return sib
when (funcall test-fn node) do (setf sib node)))
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel wrote:
> Kenny Tilton <·······@nyc.rr.com> writes:
>
>
>>Could you please do my homework for me? The teacher wants us to
>>convert this to LOOP /and/ make it clearer yet as efficient as the
>>recursive version. I can't see a way (no downfrom for lists), but
>>maybe I am missing something. Here is the recursive version:
>>
>>(defun prior-sib-if (self list &optional (test-fn #'true-that))
>> "Find nearest preceding sibling passing TEST-FN"
>> (labels ((check-priors (sibs)
>> (if (eql self (first sibs))
>> nil
>> (or (check-priors (rest sibs))
>> (when (funcall test-fn (first sibs))
>> (first sibs))))))
>> (check-priors list)))
>>
>>thanks,
>>
>> <i better not leave my name, the teacher reads this group>
>
>
> Not tested but I think this does what you want. (You can test it
> yourself--you should be doing your own homework anyway. ;-))
>
> (defun prior-sib-if (self list &optional (test-fn #'true-that))
> "Find nearest preceding sibling passing TEST-FN"
> (loop with sib = nil
> for node in list
> when (eql node self) return sib
> when (funcall test-fn node) do (setf sib node)))
Well, the teacher also said it has to be "as efficient", but that calls
the test on extra nodes, so I want to work backwards from SELF.
btw, the old version I am converting also had the flaw of calling the
test function unnecessarily. The recursive version above is actually a
new fix.
kenny
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
<·······@nyc.rr.com> wrote:
>Well, the teacher also said it has to be "as efficient", but that calls
>the test on extra nodes, so I want to work backwards from SELF.
Something like this?
(defun prior-sib-if2 (self list &optional (test-fn #'true-that))
"Find nearest preceding sibling passing TEST-FN"
(loop for a in
(loop for b in list and l = (cons b l)
do (when (eql self b) (return l)))
do (when (funcall test-fn a) (return a))))
I suppose that the
do (when ... (return x))
bits could be replaced with
with (until ...) finally return x
, if that looks clearer.
--
Juho Snellman
echo 'two billion twenty thousand five hundred and thirteen' |
perl -lp071e'y/tne/ o/d;s%(.*?)\b$&\w*%+($+)*1E0$/\n%gi,--$/while
b__m__HoHuyzOoWohFofSisiOiolw=~/[A-Z]*./g;$_-=eval;s/.(?=(...)+$)/$&,/g'
Kenny Tilton <·······@nyc.rr.com> writes:
> Peter Seibel wrote:
> > Kenny Tilton <·······@nyc.rr.com> writes:
> >
> >>Could you please do my homework for me? The teacher wants us to
> >>convert this to LOOP /and/ make it clearer yet as efficient as the
> >>recursive version. I can't see a way (no downfrom for lists), but
> >>maybe I am missing something. Here is the recursive version:
> >>
> >>(defun prior-sib-if (self list &optional (test-fn #'true-that))
> >> "Find nearest preceding sibling passing TEST-FN"
> >> (labels ((check-priors (sibs)
> >> (if (eql self (first sibs))
> >> nil
> >> (or (check-priors (rest sibs))
> >> (when (funcall test-fn (first sibs))
> >> (first sibs))))))
> >> (check-priors list)))
> >>
> >>thanks,
> >>
> >> <i better not leave my name, the teacher reads this group>
> > Not tested but I think this does what you want. (You can test it
> > yourself--you should be doing your own homework anyway. ;-))
> > (defun prior-sib-if (self list &optional (test-fn #'true-that))
> > "Find nearest preceding sibling passing TEST-FN"
> > (loop with sib = nil
> > for node in list
> > when (eql node self) return sib
> > when (funcall test-fn node) do (setf sib node)))
>
> Well, the teacher also said it has to be "as efficient", but that
> calls the test on extra nodes, so I want to work backwards from SELF.
Ah, I missed that bit in the maze of twisty, recursive passages, all
alike. How about this bit of double loop delight:
(defun prior-sib-if (self list &optional (test-fn #'true-that))
"Find nearest preceding sibling passing TEST-FN"
(loop with candidates = nil
for node in list
until (eql node self) do (push node candidates)
finally (return (loop for c in candidates when (funcall test-fn c) return c))))
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel wrote:
> Kenny Tilton <·······@nyc.rr.com> writes:
>
>
>>Peter Seibel wrote:
>>
>>>Kenny Tilton <·······@nyc.rr.com> writes:
>>>
>>>
>>>>Could you please do my homework for me? The teacher wants us to
>>>>convert this to LOOP /and/ make it clearer yet as efficient as the
>>>>recursive version. I can't see a way (no downfrom for lists), but
>>>>maybe I am missing something. Here is the recursive version:
>>>>
>>>>(defun prior-sib-if (self list &optional (test-fn #'true-that))
>>>> "Find nearest preceding sibling passing TEST-FN"
>>>> (labels ((check-priors (sibs)
>>>> (if (eql self (first sibs))
>>>> nil
>>>> (or (check-priors (rest sibs))
>>>> (when (funcall test-fn (first sibs))
>>>> (first sibs))))))
>>>> (check-priors list)))
>>>>
>>>>thanks,
>>>>
>>>> <i better not leave my name, the teacher reads this group>
>>>
>>>Not tested but I think this does what you want. (You can test it
>>>yourself--you should be doing your own homework anyway. ;-))
>>> (defun prior-sib-if (self list &optional (test-fn #'true-that))
>>> "Find nearest preceding sibling passing TEST-FN"
>>> (loop with sib = nil
>>> for node in list
>>> when (eql node self) return sib
>>> when (funcall test-fn node) do (setf sib node)))
>>
>>Well, the teacher also said it has to be "as efficient", but that
>>calls the test on extra nodes, so I want to work backwards from SELF.
>
>
> Ah, I missed that bit in the maze of twisty, recursive passages, all
> alike. How about this bit of double loop delight:
>
> (defun prior-sib-if (self list &optional (test-fn #'true-that))
> "Find nearest preceding sibling passing TEST-FN"
> (loop with candidates = nil
> for node in list
> until (eql node self) do (push node candidates)
> finally (return (loop for c in candidates when (funcall test-fn c) return c))))
Bzzt! No consing allowed. :)
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
Kenny Tilton <·······@nyc.rr.com> writes:
> Peter Seibel wrote:
>
> > Kenny Tilton <·······@nyc.rr.com> writes:
> >
> >>Peter Seibel wrote:
> >>
> >>>Kenny Tilton <·······@nyc.rr.com> writes:
> >>>
> >>>
> >>>>Could you please do my homework for me? The teacher wants us to
> >>>>convert this to LOOP /and/ make it clearer yet as efficient as the
> >>>>recursive version. I can't see a way (no downfrom for lists), but
> >>>>maybe I am missing something. Here is the recursive version:
> >>>>
> >>>>(defun prior-sib-if (self list &optional (test-fn #'true-that))
> >>>> "Find nearest preceding sibling passing TEST-FN"
> >>>> (labels ((check-priors (sibs)
> >>>> (if (eql self (first sibs))
> >>>> nil
> >>>> (or (check-priors (rest sibs))
> >>>> (when (funcall test-fn (first sibs))
> >>>> (first sibs))))))
> >>>> (check-priors list)))
> >>>>
> >>>>thanks,
> >>>>
> >>>> <i better not leave my name, the teacher reads this group>
> >>>
> >>>Not tested but I think this does what you want. (You can test it
> >>>yourself--you should be doing your own homework anyway. ;-))
> >>> (defun prior-sib-if (self list &optional (test-fn #'true-that))
> >>> "Find nearest preceding sibling passing TEST-FN"
> >>> (loop with sib = nil
> >>> for node in list
> >>> when (eql node self) return sib
> >>> when (funcall test-fn node) do (setf sib node)))
> >>
> >>Well, the teacher also said it has to be "as efficient", but that
> >>calls the test on extra nodes, so I want to work backwards from SELF.
> > Ah, I missed that bit in the maze of twisty, recursive passages, all
> > alike. How about this bit of double loop delight:
> > (defun prior-sib-if (self list &optional (test-fn #'true-that))
> > "Find nearest preceding sibling passing TEST-FN"
> > (loop with candidates = nil
> > for node in list
> > until (eql node self) do (push node candidates)
> > finally (return (loop for c in candidates when (funcall test-fn c) return c))))
>
> Bzzt! No consing allowed. :)
Where do you think stack frames come from. The Stack Frame Fairy?
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel <·····@javamonkey.com> writes:
> Kenny Tilton <·······@nyc.rr.com> writes:
>
> > Bzzt! No consing allowed. :)
>
> Where do you think stack frames come from. The Stack Frame Fairy?
I'm sure Kenny already knows this, but since the original function is
not tail recursive, and can't be rewritten to be so without consing,
it's not equivalent to a simple iteration. Since Peter's version
performs the exact same computation, it's certainly cheaper to keep
only the candidates, rather than all the other junk you get in a stack
frame. I think with (at least) ACL you can arrange to have the cons
cells stack-allocated, so you can even get them from the Stack Frame
Fairy :)
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Peter Seibel <·····@javamonkey.com> writes:
>
> Where do you think stack frames come from. The Stack Frame Fairy?
>
Where do they go when you are done with them?
My personal theory is that they go the same place that used
escalator steps go.
·············@comcast.net writes:
> Peter Seibel <·····@javamonkey.com> writes:
>
> >
> > Where do you think stack frames come from. The Stack Frame Fairy?
> >
>
> Where do they go when you are done with them?
>
> My personal theory is that they go the same place that used
> escalator steps go.
Sure. Though I suspect that such short-lived objects as the cons cells
in my LOOP version that Kenny was complaining about come from and go
back to a similar place--with a generational GC anyway.
At any rate, I suspect that the efficiency difference between
allocating such extremely-short-lived cons cells and keeping the
equivalent state on the stack via recursion is going to be subject to
a lot of implementation details that will require incredibly careful
profiling to detect. (Not to mention subsidiary issues such as the
danger of stack overflow with a recursive solution.)
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel <·····@javamonkey.com> writes:
> Where do you think stack frames come from. The Stack Frame Fairy?
Also known as Miss. Control Stack, yes..
--
Frode Vatvedt Fjeld
Peter Seibel <·····@javamonkey.com> writes:
> Where do you think stack frames come from. The Stack Frame Fairy?
It's implementation-dependent, and may even vary by CPU. SBCL, for
example, uses the Stack Frame Fairy on non-x86 ports (PPC, Alpha,
SPARC), but for x86, because of the paucity of general purpose registers,
we get them delivered by Little Green Men from Percentesp.
YMMV, of course
-dan
--
http://web.metacircles.com/cirCLe_CD - Free Software Lisp/Linux distro
Kenny Tilton <·······@nyc.rr.com> writes:
> (defun prior-sib-if (self list &optional (test-fn #'true-that))
> "Find nearest preceding sibling passing TEST-FN"
> (labels ((check-priors (sibs)
> (if (eql self (first sibs))
> nil
> (or (check-priors (rest sibs))
> (when (funcall test-fn (first sibs))
> (first sibs))))))
> (check-priors list)))
How about this, which is untested:
(defun prior-sib-if (self list test-fn)
(loop with result = nil
for x in list until (eql x self)
do (when (funcall test-fn x)
(setf result x))
finally (return result)))
This is another approach your teacher might not like:
(find-if test-fn list :end (position self list) :from-end t)
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld wrote:
> Kenny Tilton <·······@nyc.rr.com> writes:
>
>
>>(defun prior-sib-if (self list &optional (test-fn #'true-that))
>> "Find nearest preceding sibling passing TEST-FN"
>> (labels ((check-priors (sibs)
>> (if (eql self (first sibs))
>> nil
>> (or (check-priors (rest sibs))
>> (when (funcall test-fn (first sibs))
>> (first sibs))))))
>> (check-priors list)))
>
>
> How about this, which is untested:
>
> (defun prior-sib-if (self list test-fn)
> (loop with result = nil
> for x in list until (eql x self)
> do (when (funcall test-fn x)
> (setf result x))
> finally (return result)))
>
> This is another approach your teacher might not like:
>
> (find-if test-fn list :end (position self list) :from-end t)
>
Doh!!
Thanks, man! Turns out it was a trick question to see if we would
slavishly limit ourselves to LOOP when another built-in was simpler. <g>
Seriously, wow, and to think I knew about the from-end option. can't say
I knew the end was an index, that was a shocker. I guess the only flaw
is that it traverses the list twice, but for my short lists I wager your
solution is best.
thx, kenny
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
Kenny Tilton <·······@nyc.rr.com> writes:
> Thanks, man!
You're welcome :)
> [..] I guess the only flaw is that it traverses the list twice, but
> for my short lists I wager your solution is best.
I think you have two choices here, regardless of any language,
technique or mechanism issue:
1. Call the test-function while you're scanning forward, and accept
the cost of needlessly calling the test-function.
2. Scan forward to find "self", then make another backward pass
where test-function is called.
Your recursive function (and my find-if suggestion) falls into
category 2 while the , while the typical looping solution is in
category 1.
To be slightly more precise, the recursive function scans the list (up
to "self") exactly twice, while the find-if approach scans the list
two times plus the distance from "self" to the match. This one will
only scan once plus the searching distance:
(find-if test-fn (do (r (p list (cdr p)))
((eql (car p) self) r)
(push (car p) r)))
but of course it has the efficiency problem of consing. I don't think
you can have the 1+delta scanning behavior without some form of
dynamically allocating a reversed list (like the recursion does by
allocating one stack-frame per list item), but it'd be interesting to
be proved wrong about this.
Btw. the recursive solution's scanning behavior can be reduced from
two to 1+delta by this small modification:
(defun prior-sib-if (self list &optional (test-fn #'true-that))
"Find nearest preceding sibling passing TEST-FN"
(labels ((check-priors (sibs)
(if (eql self (first sibs))
nil
(or (check-priors (rest sibs))
(when (funcall test-fn (first sibs))
(return-from prior-sib-if (first sibs)))))))
(check-priors list)))
..but I don't really think this is more effective in practice, unless
possibly if the list is very long.
Obviously, all of these solitions are O(n), and I suspect that the
find-if and position combination has the smallest constant factor
overall.
--
Frode Vatvedt Fjeld (slightly bored)
Frode Vatvedt Fjeld wrote:
> To be slightly more precise, the recursive function scans the list (up
> to "self") exactly twice,
Isn't that "once plus the distance to the first match", or a maximum of
twice?
btw, I should have mentioned that in the /real/ code (slightly
different) self is guaranteed to be in list.
kenny
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
Kenny Tilton <·······@nyc.rr.com> writes:
> Isn't that "once plus the distance to the first match", or a maximum
> of twice?
Well, it kind of depends on your definitions, but so long as it's not
tail-recursive, you have to "unwind" the stack (return from each
stack-frame), which is what I counted as one full backward scan. But
like I said, it's all O(n), and anything else depends on any number of
little details. This is btw also why you shouldn't really stop
thinking when you observe that a solution scans one more time that
what is intuitively necessary. It's still just a constant
factor. (Except it alters the memory access pattern, but I don't think
we want to go there.)
--
Frode Vatvedt Fjeld
Kenny Tilton wrote:
>
> Frode Vatvedt Fjeld wrote:
>
> > Kenny Tilton <·······@nyc.rr.com> writes:
> >
> >
> >>(defun prior-sib-if (self list &optional (test-fn #'true-that))
> >> "Find nearest preceding sibling passing TEST-FN"
> >> (labels ((check-priors (sibs)
> >> (if (eql self (first sibs))
> >> nil
> >> (or (check-priors (rest sibs))
> >> (when (funcall test-fn (first sibs))
> >> (first sibs))))))
> >> (check-priors list)))
> >
> >
you might want to ask you teacher to set better problems. in particular to say
whether the function need complete on questionable input
? (defun true-that (x) (evenp x))
TRUE-THAT
? (prior-sib-if 1 '(2 3 4 5 6 7))
> Error: Stack overflow on value stack.
> To globally increase stack space,
> increase *MINIMUM-STACK-OVERFLOW-SIZE*
> While executing: CHECK-PRIORS
> Type Command-/ to continue, Command-. to abort.
> If continued: Continue with a larger stack
See the Restarts� menu item for further choices.
1 >
Aborted
?
> > How about this, which is untested:
> >
> > (defun prior-sib-if (self list test-fn)
> > (loop with result = nil
> > for x in list until (eql x self)
> > do (when (funcall test-fn x)
> > (setf result x))
> > finally (return result)))
> >
> > This is another approach your teacher might not like:
> >
> > (find-if test-fn list :end (position self list) :from-end t)
> >
>
> Doh!!
>
> Thanks, man! Turns out it was a trick question to see if we would
> slavishly limit ourselves to LOOP when another built-in was simpler. <g>
>
> Seriously, wow, and to think I knew about the from-end option. can't say
> I knew the end was an index, that was a shocker. I guess the only flaw
> is that it traverses the list twice, but for my short lists I wager your
> solution is best.
>
not only:
? (defun find-prior-sib-if (self list &optional (test-fn #'true-that))
(find-if test-fn list :end (position self list) :from-end t))
FIND-PRIOR-SIB-IF
? (find-prior-sib-if 1 '(2 3 4 5 6 7))
6
?
if you inputs are small, you can always try
? (defun caching-prior-sib-if (self list &optional (test-fn #'true-that)
(cache nil))
(when list
(if (eql self (first list))
(find-if test-fn cache)
(caching-prior-sib-if self (rest list) test-fn (cons (first list) cache)))))
CACHING-PRIOR-SIB-IF
? (caching-prior-sib-if 1 '(2 3 4 5 6 7))
NIL
? (caching-prior-sib-if 6 '(2 3 4 5 6 7))
4
?
...
james anderson wrote:
>
> Kenny Tilton wrote:
>
>>Frode Vatvedt Fjeld wrote:
>>
>>
>>>Kenny Tilton <·······@nyc.rr.com> writes:
>>>
>>>
>>>
>>>>(defun prior-sib-if (self list &optional (test-fn #'true-that))
>>>> "Find nearest preceding sibling passing TEST-FN"
>>>> (labels ((check-priors (sibs)
>>>> (if (eql self (first sibs))
>>>> nil
>>>> (or (check-priors (rest sibs))
>>>> (when (funcall test-fn (first sibs))
>>>> (first sibs))))))
>>>> (check-priors list)))
>>>
>>>
>
> you might want to ask you teacher to set better problems. in particular to say
> whether the function need complete on questionable input
Thanks, that was my mistake. He actually gave us a prior version not
shown which tested excessively, and that tested for nil input. The first
exercise was actually just to lose the excessive testing and I
mistakenly pulled the test for nil out thinking it was redundant.
Somehow I thought I was doing something like a dolist which would
terminate of its own accord.
I realized only after posting that I had not tested the above and was
afraid it would have bugs.
:)
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
Kenny Tilton wrote:
>
>
> james anderson wrote:
>
>>
>> Kenny Tilton wrote:
>>
>>> Frode Vatvedt Fjeld wrote:
>>>
>>>
>>>> Kenny Tilton <·······@nyc.rr.com> writes:
>>>>
>>>>
>>>>
>>>>> (defun prior-sib-if (self list &optional (test-fn #'true-that))
>>>>> "Find nearest preceding sibling passing TEST-FN"
>>>>> (labels ((check-priors (sibs)
>>>>> (if (eql self (first sibs))
>>>>> nil
>>>>> (or (check-priors (rest sibs))
>>>>> (when (funcall test-fn (first sibs))
>>>>> (first sibs))))))
>>>>> (check-priors list)))
>>>>
>>>>
>>>>
>>
>> you might want to ask you teacher to set better problems. in
>> particular to say
>> whether the function need complete on questionable input
>
>
> Thanks, that was my mistake. He actually gave us a prior version not
> shown which tested excessively, and that tested for nil input. The first
> exercise was actually just to lose the excessive testing and I
> mistakenly pulled the test for nil out thinking it was redundant.
Responding elsewhere in this thread, I am reminded that another detail I
left out is that self is guaranteed to be in list in the "live" example,
which I /think/ is why the code posted is a tad safety zero-ish. Anyway,
it's a good cover story. :)
kenny
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
james anderson <··············@setf.de> writes:
> ? (defun find-prior-sib-if (self list &optional (test-fn #'true-that))
> (find-if test-fn list :end (position self list) :from-end t))
>
> FIND-PRIOR-SIB-IF
> ? (find-prior-sib-if 1 '(2 3 4 5 6 7))
> 6
Actually, I considered this, and precisely because the original
function would fail if the self element wasn't present, I didn't
bother with this situation. It's easy enough to specify what is to
happen if position returns nil, anyway.
> ? (defun caching-prior-sib-if (self list &optional (test-fn #'true-that)
> (cache nil))
> (when list
> (if (eql self (first list))
> (find-if test-fn cache)
> (caching-prior-sib-if self (rest list) test-fn
> (cons (first list) cache)))))
This is a pretty strange, recursivish way to achieve the same effect
that I did with the explicit loop that generated the reverse list in
my previous post:
(find-if test-fn (do (r (p list (cdr p)))
((eql (car p) self) r)
(push (car p) r)))
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld wrote:
>
> james anderson <··············@setf.de> writes:
>
> > ? (defun find-prior-sib-if (self list &optional (test-fn #'true-that))
> > (find-if test-fn list :end (position self list) :from-end t))
> >
> > FIND-PRIOR-SIB-IF
> > ? (find-prior-sib-if 1 '(2 3 4 5 6 7))
> > 6
>
> Actually, I considered this, and precisely because the original
> function would fail if the self element wasn't present, I didn't
> bother with this situation. It's easy enough to specify what is to
> happen if position returns nil, anyway.
yes it is, but i figured that, as the teacher was apparently unaware of the
issue, it might be good for some extra credit.
>
> > ? (defun caching-prior-sib-if (self list &optional (test-fn #'true-that)
> > (cache nil))
> > (when list
> > (if (eql self (first list))
> > (find-if test-fn cache)
> > (caching-prior-sib-if self (rest list) test-fn
> > (cons (first list) cache)))))
>
> This is a pretty strange, recursivish way to achieve the same effect
> that I did with the explicit loop that generated the reverse list in
> my previous post:
previous being interpreted relativisticly.
>
> (find-if test-fn (do (r (p list (cdr p)))
> ((eql (car p) self) r)
> (push (car p) r)))
i am, in any case, curious why one would term it "pretty strange"? is it not
an instance of an at least twenty year old idiom for
rewriting_for_tail_recursion and, or so i thought, the prototypical naive
implemention of reverse?
?
james anderson <··············@setf.de> writes:
> ? (defun caching-prior-sib-if (self list &optional (test-fn #'true-that)
> (cache nil))
> (when list
> (if (eql self (first list))
> (find-if test-fn cache)
> (caching-prior-sib-if self (rest list) test-fn
> (cons (first list) cache)))))
[...]
> i am, in any case, curious why one would term it "pretty strange"?
> is it not an instance of an at least twenty year old idiom for
> rewriting_for_tail_recursion and, or so i thought, the prototypical
> naive implemention of reverse?
I just found it somewhat strange the way you intertwined the search
and the reversing operations, calling find-if at the deep end of the
recursion. Also, one of the benefits of recursion is that you can use
the stack-frames as a kind of dynamic-extent allocation (in this case,
of the reverse list you need to search, like Kenny's original function
did), whereas you don't utilize this and so more or less get the
"worst of both worlds".
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> I just found it somewhat strange the way you intertwined the search
> and the reversing operations, calling find-if at the deep end of the
> recursion. Also, one of the benefits of recursion is that you can use
> the stack-frames as a kind of dynamic-extent allocation (in this case,
> of the reverse list you need to search, like Kenny's original function
> did), whereas you don't utilize this and so more or less get the
> "worst of both worlds".
But of course, the maximum depth of stack might not be large enough
to handle the length of the lists you want to traverse with this,
which actually implies that the consing solutions would be preferred
if generality was at stake.
-russ
Kenny Tilton wrote:
> Could you please do my homework for me? The teacher wants us to convert
> this to LOOP /and/ make it clearer yet as efficient as the recursive
> version. I can't see a way (no downfrom for lists), but maybe I am
> missing something. Here is the recursive version:
>
> (defun prior-sib-if (self list &optional (test-fn #'true-that))
> "Find nearest preceding sibling passing TEST-FN"
> (labels ((check-priors (sibs)
> (if (eql self (first sibs))
> nil
> (or (check-priors (rest sibs))
> (when (funcall test-fn (first sibs))
> (first sibs))))))
> (check-priors list)))
>
(defun prior-sib-if (self list &optional (test-fn #'true-that))
(loop for element in list
for previous in (cons nil list)
for passing = nil then (if (funcall test-fn previous) previous passing)
when (eql element self) return passing))
Wade
Wade Humeniuk <········@nospamtelus.net> writes:
> (defun prior-sib-if (self list &optional (test-fn #'true-that))
> (loop for element in list
> for previous in (cons nil list)
;; I prefer
for previous = nil then element
> for passing = nil then (if (funcall test-fn previous) previous passing)
> when (eql element self) return passing))
>
> Wade
>
--
Thomas A. Russ, USC/Information Sciences Institute
Kenny Tilton <·······@nyc.rr.com> writes:
> Could you please do my homework for me? The teacher wants us to
> convert this to LOOP /and/ make it clearer yet as efficient as the
> recursive version. I can't see a way (no downfrom for lists), but
> maybe I am missing something. Here is the recursive version:
>
> (defun prior-sib-if (self list &optional (test-fn #'true-that))
> "Find nearest preceding sibling passing TEST-FN"
> (labels ((check-priors (sibs)
> (if (eql self (first sibs))
> nil
> (or (check-priors (rest sibs))
> (when (funcall test-fn (first sibs))
> (first sibs))))))
> (check-priors list)))
(defun prior-sib-if (self list &optional (test-fn #'true-that))
"Find nearest preceding sibling passing TEST-FN"
(let ((latest nil))
(loop for x in list until (eq x self) do
(when (funcall test-fn x)
(setq latest x)))
latest))
(defun test (n)
(let* ((list (list 0))
(last (first list)))
(loop for i from 1 to n do
(push i list)
(prior-sib-if last list #'evenp))))
Timings (CMU CL 18e, default optimization settings,
all code compiled, Athlon/1GHz, FreeBSD, (test 10000)
immediately following (gc)):
Kenny's version:
; 3.29 seconds of real time
; 3.131104 seconds of user run time
; 4.26e-4 seconds of system run time
; 3,281,258,636 CPU cycles
; 0 page faults and
; 80,072 bytes consed.
My version:
; 2.44 seconds of real time
; 2.321563 seconds of user run time
; 0.015813 seconds of system run time
; 2,433,045,320 CPU cycles
; 0 page faults and
; 80,072 bytes consed.
For (test 15000), Kenny's:
; 13.9 seconds of real time
; 13.298893 seconds of user run time
; 0.007819 seconds of system run time
; 13,894,682,950 CPU cycles
; 0 page faults and
; 120,072 bytes consed.
and mine:
; 5.52 seconds of real time
; 5.321154 seconds of user run time
; 0.007577 seconds of system run time
; 5,523,384,150 CPU cycles
; 0 page faults and
; 120,072 bytes consed.
I think the LOOPing code is clearer than the recursive
code, but I've been a LOOPophile for years. :-)
--
Gareth McCaughan
.sig under construc
Gareth McCaughan wrote:
> Kenny Tilton <·······@nyc.rr.com> writes:
>
>
>>Could you please do my homework for me? The teacher wants us to
>>convert this to LOOP /and/ make it clearer yet as efficient as the
>>recursive version. I can't see a way (no downfrom for lists), but
>>maybe I am missing something. Here is the recursive version:
>>
>>(defun prior-sib-if (self list &optional (test-fn #'true-that))
>> "Find nearest preceding sibling passing TEST-FN"
>> (labels ((check-priors (sibs)
>> (if (eql self (first sibs))
>> nil
>> (or (check-priors (rest sibs))
>> (when (funcall test-fn (first sibs))
>> (first sibs))))))
>> (check-priors list)))
>
>
> (defun prior-sib-if (self list &optional (test-fn #'true-that))
> "Find nearest preceding sibling passing TEST-FN"
> (let ((latest nil))
> (loop for x in list until (eq x self) do
> (when (funcall test-fn x)
> (setq latest x)))
> latest))
>
> (defun test (n)
> (let* ((list (list 0))
> (last (first list)))
> (loop for i from 1 to n do
> (push i list)
> (prior-sib-if last list #'evenp))))
>
> Timings (CMU CL 18e, default optimization settings,
> all code compiled, Athlon/1GHz, FreeBSD, (test 10000)
> immediately following (gc)):
>
> Kenny's version:
>
> ; 3.29 seconds of real time
> ; 3.131104 seconds of user run time
> ; 4.26e-4 seconds of system run time
> ; 3,281,258,636 CPU cycles
> ; 0 page faults and
> ; 80,072 bytes consed.
>
> My version:
>
> ; 2.44 seconds of real time
> ; 2.321563 seconds of user run time
> ; 0.015813 seconds of system run time
> ; 2,433,045,320 CPU cycles
> ; 0 page faults and
> ; 80,072 bytes consed.
Zippy. Hey, I thought you could not use eq on numbers? Anyway, the
problem is that the test functions would be a /lot/ heftier than evenp,
perhaps:
(lambda (self) (eq sought-name (model-name self)))
where model name is a GF slot accessor. And the lists would be just a
few things long, so not so much stack call-frame construction (my fake
attempt at sounding all compiler-y).
kenny
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
Kenny Tilton wrote:
[SNIP: my solution to his list-traversing thing]
> Zippy. Hey, I thought you could not use eq on numbers?
Well, no, but that's your fault. It would be better for
the function to be specified as taking the *cons cell*
to terminate the search. There isn't a right way to do
this with the interface as specified.
> Anyway, the
> problem is that the test functions would be a /lot/ heftier than
> evenp, perhaps:
>
> (lambda (self) (eq sought-name (model-name self)))
>
> where model name is a GF slot accessor. And the lists would be just a
> few things long, so not so much stack call-frame construction (my fake
> attempt at sounding all compiler-y).
Ah. Well, you didn't say any of that.
Anyway: iterating backwards over a list is not something
LOOP does, any more than it searches trees. I suspect it's
often better to avoid having to do it altogether. :-)
--
Gareth McCaughan
.sig under construc
Gareth McCaughan wrote:
> Kenny Tilton wrote:
>
> [SNIP: my solution to his list-traversing thing]
>
>>Zippy. Hey, I thought you could not use eq on numbers?
>
>
> Well, no, but that's your fault. It would be better for
> the function to be specified as taking the *cons cell*
> to terminate the search.
uh, it's the requirment's fault. we have self, not its cons in the list.
There isn't a right way to do
> this with the interface as specified.
heh-heh, that's all I was asking.
kenny
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
I compared Gareth McCaughan's solution to one I wrote based on nreversing
the list before and after looking for the appropriate sibling. The test
code was
;;; solution based on nreverse before and after
(defun find-preceding-sib-if (self list predicate)
(let ((rlist (nreverse list))
(result nil))
(loop for x on rlist while (not (eq (car x) self)) finally
(setf result (find-if predicate (cdr x)))
(nreverse rlist) )
result))
(defun test1 (n)
(let* ((list (list 0))
(last (first list)))
(loop for i from 1 to n do
(push i list)
(find-preceding-sib-if last list #'evenp))))
;;; Gareth McCaughan's solution and test
(defun prior-sib-if (self list &optional (test-fn #'true-that))
"Find nearest preceding sibling passing TEST-FN"
(let ((latest nil))
(loop for x in list until (eq x self) do
(when (funcall test-fn x)
(setq latest x)))
latest))
(defun test2 (n)
(let* ((list (list 0))
(last (first list)))
(loop for i from 1 to n do
(push i list)
(prior-sib-if last list #'evenp))))
Even though my version requires 3 passes through the list (including one for
each nreverse), it runs faster (almost 3x faster) in this contrived test
case, presumably because it calls the predicate function much less often
(O(n) as opposed to O(n^2) times) over the duration of the test, because it
doesn't call the test function until it has already found self in the list.
This would not happen in a different version of the test. If the relevant
prior sibling were at the beginning of the list rather than just before the
end, my solution would be left in the dust because the nreverse calls cost
O(n^2) over the duration of the test. I tested in CormanLisp 1.5, following
McCaughan's prescription of calling (gc) before each test.
So whether nreversing the list is a good idea depends upon how expensive it
is to compute the test function and how far, on the average, the prior
sibling that satisfies the predicate is from the selected item in the list.
Jeff
Jeff Greif wrote:
> I compared Gareth McCaughan's solution to one I wrote based on nreversing
> the list before and after looking for the appropriate sibling. The test
> code was
...
> Even though my version requires 3 passes through the list (including one for
> each nreverse), it runs faster (almost 3x faster) in this contrived test
> case, presumably because it calls the predicate function much less often
> (O(n) as opposed to O(n^2) times) over the duration of the test, because it
> doesn't call the test function until it has already found self in the list.
> This would not happen in a different version of the test. If the relevant
> prior sibling were at the beginning of the list rather than just before the
> end, my solution would be left in the dust because the nreverse calls cost
> O(n^2) over the duration of the test. I tested in CormanLisp 1.5, following
> McCaughan's prescription of calling (gc) before each test.
>
> So whether nreversing the list is a good idea depends upon how expensive it
> is to compute the test function and how far, on the average, the prior
> sibling that satisfies the predicate is from the selected item in the list.
Yep. Just one more instance where saying "make this code fast"
is meaningless without details of how it's going to be used.
A black mark for Kenny, there. :-)
--
Gareth McCaughan
.sig under construc
Paul Foley wrote:
> On Sun, 19 Oct 2003 18:05:29 GMT, Jeff Greif wrote:
>
>
>>I compared Gareth McCaughan's solution to one I wrote based on nreversing
>>the list before and after looking for the appropriate sibling. The test
>>code was
>
>
>>;;; solution based on nreverse before and after
>>(defun find-preceding-sib-if (self list predicate)
>> (let ((rlist (nreverse list))
>> (result nil))
>> (loop for x on rlist while (not (eq (car x) self)) finally
>> (setf result (find-if predicate (cdr x)))
>> (nreverse rlist) )
>> result))
>
>
> You don't need the last NREVERSE - you're just throwing the result
> away anyway; but trashing the input list may not be a great idea.
>
Having trashed the input list, he has to untrash it. But here's a question:
(equal list (nreverse (nreverse list)))=> what?
Not enough coffee yet to figure that out.
kenny
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
Kenny Tilton <·······@nyc.rr.com> wrote in message news:<····················@twister.nyc.rr.com>...
> Paul Foley wrote:
>
> > On Sun, 19 Oct 2003 18:05:29 GMT, Jeff Greif wrote:
> >
> >
> >>I compared Gareth McCaughan's solution to one I wrote based on nreversing
> >>the list before and after looking for the appropriate sibling. The test
> >>code was
> >
> >
> >>;;; solution based on nreverse before and after
> >>(defun find-preceding-sib-if (self list predicate)
> >> (let ((rlist (nreverse list))
> >> (result nil))
> >> (loop for x on rlist while (not (eq (car x) self)) finally
> >> (setf result (find-if predicate (cdr x)))
> >> (nreverse rlist) )
> >> result))
> >
> >
> > You don't need the last NREVERSE - you're just throwing the result
> > away anyway; but trashing the input list may not be a great idea.
> >
>
> Having trashed the input list, he has to untrash it. But here's a question:
>
> (equal list (nreverse (nreverse list)))=> what?
>
> Not enough coffee yet to figure that out.
If you look up nreverse in CLHS you'll note under Side Effects:
"nreverse might either create a new sequence, modify the argument
sequence, or both. (reverse does not modify sequence.)"
So, it would be perfectly legal to have nreverse be identical to
reverse. The n in nreverse just says that it can be destructive if it
feels like it.
However, for the test of #'equal, it will return true regardless of
whether you use nreverse or reverse because #'equal simply recurses on
a cons and reverse and nreverse both maintain the identity of the
objects being reversed.
cl-user(0): (setf x (list 1 2 3 4 5))
(1 2 3 4 5)
cl-user(1): (equal x (reverse (reverse x))) ; note: not nreverse
t
If #'equal passes for reverse, it MUST pass for nreverse.
More interstingly, in any good Lisp implementation nreverse ought not
to cons at all. This being the case, the original list and the result
of two nreverses of that list should not only be #'equal, they should
in fact be #'eq.
ACL seems to work this way:
cl-user(0): (setf x (list 1 2 3 4 5))
(1 2 3 4 5)
cl-user(1): (eq x (nreverse (nreverse x)))
t
This, of course, should not be relied upon.
Justin Dubs
On 20 Oct 2003 10:36:11 -0700, ······@eos.ncsu.edu (Justin Dubs) wrote:
> If you look up nreverse in CLHS you'll note under Side Effects:
>
> "nreverse might either create a new sequence, modify the argument
> sequence, or both. (reverse does not modify sequence.)"
>
> So, it would be perfectly legal to have nreverse be identical to
> reverse. The n in nreverse just says that it can be destructive if
> it feels like it.
>
> However, for the test of #'equal, it will return true regardless of
> whether you use nreverse or reverse because #'equal simply recurses
> on a cons and reverse and nreverse both maintain the identity of the
> objects being reversed.
>
> cl-user(0): (setf x (list 1 2 3 4 5))
> (1 2 3 4 5)
> cl-user(1): (equal x (reverse (reverse x))) ; note: not nreverse
> t
>
> If #'equal passes for reverse, it MUST pass for nreverse.
As Peter Seibel has already pointed out this is probably not
true. According to the CLHS, NREVERSE "might either create a new
sequence, modify the argument sequence, or both." So, in my
understanding it would be conforming if the inner call to NREVERSE
actually modified X while the outer call created a new sequence. Try
this:
(let ((x (list 1 2 3)))
(equal x (reverse (nreverse x))))
AllegroCL, CMUCL, CLISP, SBCL, and LispWorks all return NIL on my
machine.
I'd say that the fact that the result of the form above is T in most
(all?) current implementations is pure coincidence.
Edi.
Edi Weitz <···@agharta.de> wrote in message news:<··············@bird.agharta.de>...
> On 20 Oct 2003 10:36:11 -0700, ······@eos.ncsu.edu (Justin Dubs) wrote:
>
> > If you look up nreverse in CLHS you'll note under Side Effects:
> >
> > "nreverse might either create a new sequence, modify the argument
> > sequence, or both. (reverse does not modify sequence.)"
> >
> > So, it would be perfectly legal to have nreverse be identical to
> > reverse. The n in nreverse just says that it can be destructive if
> > it feels like it.
> >
> > However, for the test of #'equal, it will return true regardless of
> > whether you use nreverse or reverse because #'equal simply recurses
> > on a cons and reverse and nreverse both maintain the identity of the
> > objects being reversed.
> >
> > cl-user(0): (setf x (list 1 2 3 4 5))
> > (1 2 3 4 5)
> > cl-user(1): (equal x (reverse (reverse x))) ; note: not nreverse
> > t
> >
> > If #'equal passes for reverse, it MUST pass for nreverse.
>
> As Peter Seibel has already pointed out this is probably not
> true. According to the CLHS, NREVERSE "might either create a new
> sequence, modify the argument sequence, or both." So, in my
> understanding it would be conforming if the inner call to NREVERSE
> actually modified X while the outer call created a new sequence. Try
> this:
>
> (let ((x (list 1 2 3)))
> (equal x (reverse (nreverse x))))
>
> AllegroCL, CMUCL, CLISP, SBCL, and LispWorks all return NIL on my
> machine.
>
> I'd say that the fact that the result of the form above is T in most
> (all?) current implementations is pure coincidence.
Clearly you are right. For some reason the word "destructive" just
went right over my head. Once x has been destructively modified all
bets are off.
You've won this time Edi! But I'll be back! *shakes fist menacingly*
Justin
equal must certainly be true, as the conses of the original list must be
used to hold the same contents in the same order. I think in most
implementations, eq is also true, but it probably is not guaranteed, as it
is implementation dependent. The reason eq is usually true is that one
efficient implementation of nreverse just reverses the pointers (the second
cons cell of the orig. list points at the first cons cell after nreverse),
so (nreverse (nreverse list)) would give exactly the original list. It
probably wouldn't (couldn't?) work this way on a Lisp machine if the
original list were cdr-coded.
Jeff
"Kenny Tilton" <·······@nyc.rr.com> wrote in message
·························@twister.nyc.rr.com...
>
But here's a question:
>
> (equal list (nreverse (nreverse list)))=> what?
>
> Not enough coffee yet to figure that out.
>
> kenny
>
> --
> http://tilton-technology.com
> What?! You are a newbie and you haven't answered my:
> http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
>
"Jeff Greif" <······@spam-me-not.alumni.princeton.edu> writes:
> equal must certainly be true, as the conses of the original list must be
> used to hold the same contents in the same order.
I don't think so, since by the time EQUAL is run, list was destroyed
by a call to NREVERSE. I think all bets are off at this point.
-Peter
> I think in most implementations, eq is also true, but it probably is
> not guaranteed, as it is implementation dependent. The reason eq is
> usually true is that one efficient implementation of nreverse just
> reverses the pointers (the second cons cell of the orig. list points
> at the first cons cell after nreverse), so (nreverse (nreverse
> list)) would give exactly the original list. It probably wouldn't
> (couldn't?) work this way on a Lisp machine if the original list
> were cdr-coded.
>
> Jeff
>
> "Kenny Tilton" <·······@nyc.rr.com> wrote in message
> ·························@twister.nyc.rr.com...
> >
> But here's a question:
> >
> > (equal list (nreverse (nreverse list)))=> what?
> >
> > Not enough coffee yet to figure that out.
> >
> > kenny
> >
> > --
> > http://tilton-technology.com
> > What?! You are a newbie and you haven't answered my:
> > http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
> >
>
>
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
One slightly different approach:
nreverse the list (to avoid consing) and then do the obvious traversal,
first to find self, and then continuing to find the first succeeding item
passing the test, and finally nreverse the list to its original form at the
end.
Jeff
"Kenny Tilton" <·······@nyc.rr.com> wrote in message
··························@twister.nyc.rr.com...
> Could you please do my homework for me? The teacher wants us to convert
> this to LOOP /and/ make it clearer yet as efficient as the recursive
> version. I can't see a way (no downfrom for lists), but maybe I am
> missing something. Here is the recursive version:
>
> (defun prior-sib-if (self list &optional (test-fn #'true-that))
> "Find nearest preceding sibling passing TEST-FN"
> (labels ((check-priors (sibs)
> (if (eql self (first sibs))
> nil
> (or (check-priors (rest sibs))
> (when (funcall test-fn (first sibs))
> (first sibs))))))
> (check-priors list)))