Well, I hope that this is a little better than the last batch.
This is my solution to Ex. 5 on p. 97 of Paul Graham's "ANSI Common
Lisp"
<QUOTE>
Define iterative and recursive versions of a function that takes an
object x and a vector v, and returns a list of all the objects that
immediately precede x in v.
> (precedes #\a "abracadabra")
(#\c #\d #\r)
</QUOTE>
(I'll just ask about the iterative solution I developed.)
;;;;Ex. 5
(defun precedes (object vector)
(let ((maximum-vector-index (- (length vector) 1))
(return-list nil))
(dotimes (vector-index maximum-vector-index return-list)
(let ((test-vector-element (aref vector (+ vector-index 1)))
(preceding-vector-element (aref vector vector-index)))
(if (and (eql object test-vector-element)
(not (member preceding-vector-element return-list)))
(push preceding-vector-element return-list))))))
Do you think that the use of DOTIMES is better than DO in this case?
This is my solution to Ex. 6 on p. 97 of Paul Graham's "ANSI Common
Lisp"
<QUOTE>
Define iterative and recursive versions of a function that takes an
object and a list, and returns a new list in which the object appears
between each pair of elements in the original list:
> (intersprerse '- '(a b c d))
(A - B - C - C)
<\QUOTE>
(I'll just ask about the iterative solution I developed.)
;;;;Ex. 6
(defun intersperse (element list)
(let ((return-list (list (car list))))
(do ((rest-input-list (cdr list) (cdr rest-input-list))
(rest-return-list return-list (cddr rest-return-list)))
((not (consp rest-input-list)) return-list)
(setf (cdr rest-return-list)
(list element (car rest-input-list))))))
This one I'm a little more unsure about. Is the use of CDDR
acceptable? Should the RETURN-LIST variable creation be placed in the
DO construct?
Martin Pomije wrote:
> Well, I hope that this is a little better than the last batch.
>
> This is my solution to Ex. 5 on p. 97 of Paul Graham's "ANSI Common
> Lisp"
>
> <QUOTE>
> Define iterative and recursive versions of a function that takes an
> object x and a vector v, and returns a list of all the objects that
> immediately precede x in v.
>
>
>>(precedes #\a "abracadabra")
>
> (#\c #\d #\r)
> </QUOTE>
>
> (I'll just ask about the iterative solution I developed.)
>
> ;;;;Ex. 5
> (defun precedes (object vector)
> (let ((maximum-vector-index (- (length vector) 1))
> (return-list nil))
> (dotimes (vector-index maximum-vector-index return-list)
> (let ((test-vector-element (aref vector (+ vector-index 1)))
> (preceding-vector-element (aref vector vector-index)))
> (if (and (eql object test-vector-element)
> (not (member preceding-vector-element return-list)))
> (push preceding-vector-element return-list))))))
>
> Do you think that the use of DOTIMES is better than DO in this case?
toss-up. meanwhile, look up pushnew. and when to use 'when'. not a lisp
issue, but those long variable names sure make the code hard to read. X
would be fine for vector-index, and item would be fine for vector
element. don't you want to nreverse the list when done?
>
>
>
> This is my solution to Ex. 6 on p. 97 of Paul Graham's "ANSI Common
> Lisp"
>
> <QUOTE>
> Define iterative and recursive versions of a function that takes an
> object and a list, and returns a new list in which the object appears
> between each pair of elements in the original list:
>
>
>>(intersprerse '- '(a b c d))
>
> (A - B - C - C)
> <\QUOTE>
>
> (I'll just ask about the iterative solution I developed.)
>
> ;;;;Ex. 6
> (defun intersperse (element list)
> (let ((return-list (list (car list))))
> (do ((rest-input-list (cdr list) (cdr rest-input-list))
> (rest-return-list return-list (cddr rest-return-list)))
> ((not (consp rest-input-list)) return-list)
> (setf (cdr rest-return-list)
> (list element (car rest-input-list))))))
Can't use map? Well, the whole thing looks a lot clearer I think if you
just establish a return-tail var (your rest-return-list, which goes
away) outside the do along with return-list, then just setf that as you
go. (as you create that cons cell, not by using CCDR on the prior tail.)
And that (not (consp...)) test has me curious.
>
> This one I'm a little more unsure about. Is the use of CDDR
> acceptable? Should the RETURN-LIST variable creation be placed in the
> DO construct?
kt
--
http://tilton-technology.com
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
Kenny Tilton <·······@nyc.rr.com> wrote in message news:<························@twister.nyc.rr.com>...
> Martin Pomije wrote:
>
(snip)
>don't you want to nreverse the list when done?
I don't see that as being implied in the problem statement. What am I
missing?
>
> >
> >
> >
> > This is my solution to Ex. 6 on p. 97 of Paul Graham's "ANSI Common
> > Lisp"
> >
> > <QUOTE>
> > Define iterative and recursive versions of a function that takes an
> > object and a list, and returns a new list in which the object appears
> > between each pair of elements in the original list:
> >
> >
> >>(intersprerse '- '(a b c d))
> >
> > (A - B - C - C)
> > <\QUOTE>
> >
> > (I'll just ask about the iterative solution I developed.)
> >
> > ;;;;Ex. 6
> > (defun intersperse (element list)
> > (let ((return-list (list (car list))))
> > (do ((rest-input-list (cdr list) (cdr rest-input-list))
> > (rest-return-list return-list (cddr rest-return-list)))
> > ((not (consp rest-input-list)) return-list)
> > (setf (cdr rest-return-list)
> > (list element (car rest-input-list))))))
>
> Can't use map?
MAP is introduced much later in the book.
> Well, the whole thing looks a lot clearer I think if you
> just establish a return-tail var (your rest-return-list, which goes
> away) outside the do along with return-list, then just setf that as you
> go. (as you create that cons cell, not by using CCDR on the prior tail.)
> And that (not (consp...)) test has me curious.
Did you have something like this in mind?
(defun intersperse (object list)
(let ((return-list (list (car list))))
(let ((return-tail return-list))
(dolist (element (cdr list) return-list)
(setf (cdr return-tail) (list object element))
(setf return-tail (cddr return-tail))))))
I realize that I could get by with one SETF, but I find it more clear
to have two SETF calls since they both involve the same variable.
Martin Pomije wrote:
> Kenny Tilton <·······@nyc.rr.com> wrote in message news:<························@twister.nyc.rr.com>...
>
>>Martin Pomije wrote:
>>
>
>
> (snip)
>
>
>>don't you want to nreverse the list when done?
>
>
> I don't see that as being implied in the problem statement. What am I
> missing?
Nothing, except perhaps the thread subject where it mentions "code
review". If it were required by the spec I would have said, "Dude!
Nreverse the result!!"
So why nreverse it? Why write a function to find things in a list and
reverse the order in which they were found? That's just perverse, asking
for trouble, and diminishing the value of the function.
Note that a number of people also commented, as did I, on the huge data
names, and that some of the bindings could be dispensed with altogether.
The spec also did not say "avoid long data names and unnecessary
bindings". It was in that spirit that the nreverse was suggested, not
strict correctness of the result.
kt
--
http://tilton-technology.com
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
>Martin Pomije wrote:
>> Kenny Tilton <·······@nyc.rr.com> wrote in message news:<························@twister.nyc.rr.com>...
>>>Martin Pomije wrote:
>>>don't you want to nreverse the list when done?
>>
>> I don't see that as being implied in the problem statement. What am I
>> missing?
>
>Nothing, except perhaps the thread subject where it mentions "code
>review". If it were required by the spec I would have said, "Dude!
>Nreverse the result!!"
>
>So why nreverse it? Why write a function to find things in a list and
>reverse the order in which they were found? That's just perverse, asking
>for trouble, and diminishing the value of the function.
>
I write code to specs all the time, and I definitely read an implication that
the results should be in the same order. I know that it doesn't say that
explicitly, but if the spec doesn't say "the results should be in reverse order"
or "the results can be in any arbitrary order" I would assume they should be in
the original order. It's simply the most common case, and therefore often not
spelled out explicitly. The problem also doesn't say that if an object appears
more than once in the vector that you should return the multiple instances in
the list, but most of us assumed that is what was meant. The problem is to
return an ordered sequence, not an order-less set, because lacking language to
the contrary this is the most common thing. Lacking language describing the
ordering of the sequence, you assume the order is unchanged.
Roger Corman
Corman Technologies
www.cormanlisp.com
* Kenny Tilton:
> don't you want to nreverse the list when done?
* Martin Pomije:
> What am I missing?
Lispniks don't use queues to collect some data in a list. Lispniks
cons if inevitable and nreverse. Lispniks share conses.
Lispniks usually don't write:
(defun intersperse (object list)
(unless (endp list)
(let ((queue (queue (list (first list)))))
(dolist (item (rest list) (queue-list queue))
(enqueue* item object queue)))))
or similar.
--
"Hurry if you still want to see something. Everything is vanishing."
-- Paul C�zanne (1839-1906)
······@MartinPomije.eiomail.com (Martin Pomije) writes:
> Well, I hope that this is a little better than the last batch.
>
> This is my solution to Ex. 5 on p. 97 of Paul Graham's "ANSI Common
> Lisp"
>
> <QUOTE>
> Define iterative and recursive versions of a function that takes an
> object x and a vector v, and returns a list of all the objects that
> immediately precede x in v.
>
> > (precedes #\a "abracadabra")
> (#\c #\d #\r)
> </QUOTE>
>
> (I'll just ask about the iterative solution I developed.)
>
> ;;;;Ex. 5
> (defun precedes (object vector)
> (let ((maximum-vector-index (- (length vector) 1))
> (return-list nil))
> (dotimes (vector-index maximum-vector-index return-list)
> (let ((test-vector-element (aref vector (+ vector-index 1)))
> (preceding-vector-element (aref vector vector-index)))
> (if (and (eql object test-vector-element)
> (not (member preceding-vector-element return-list)))
> (push preceding-vector-element return-list))))))
>
> Do you think that the use of DOTIMES is better than DO in this case?
DOTIMES is fine. My main commentt is, while it's good to use
descriptive names, you don't want to go overboard. And you don't
really need to pull the (- (length vector) 1) expression out since
it's only used once--I think it's actually more clear to use it
directly in place; seeing it in place in the DOTIMES I know what it's
for immediately. (Also, that's one of the benefits of using DOTIMES
compared to DO, is that it only evaluates the count-form once).
Finally, you can use PUSHNEW to do the membership test for you.
Anyway, here's how I'd modify your original to make it (IMO) a bit
more clear but otherwise about the same. Note how I haven't
abbreviated any names--they're all full words. But I don't think
anything is lost by, for example, using a single word, `index' instead
of `vector-index':
(defun precedes (object vector)
(let ((results nil))
(dotimes (index (1- (length vector)) results)
(let ((current (aref vector (1+ index)))
(previous (aref vector index)))
(when (eql object current)
(pushnew previous results))))))
Now that I can sort of see what's going on, I see that `current' and
`previous' are also only used once each so I think it'll further
clarify things to inline the expressions. I'd also abbreviate the
index variable--not because it's less typing but because I can tell at
a glance that it's just a regular index variable. Matter of taste:
(defun precedes (object vector)
(let ((results nil))
(dotimes (idx (1- (length vector)) results)
(when (eql object (aref vector (1+ idx)))
(pushnew (aref vector idx) results)))))
That we've got things boiled down a bit we can try writing the
equivalent using DO. Because we can control the starting value of the
index with a DO loop I switch to starting at 1 and looping up to the
end of the vector. I always try to have my index variable actually
looping over the indices I want to use--I always screw it up if the
end test is anything more complicated than (= idx (length vector)).
(defun precedes (object vector)
(do ((length (length vector))
(results nil)
(idx 1 (1+ idx)))
((= idx length) results)
(when (eql object (aref vector idx))
(pushnew (aref vector (1- idx)) results))))
I don't think that's really any better. Maybe LOOP:
(defun precedes (object vector)
(loop with results = nil
for idx from 1 below (length vector)
when (eql object (aref vector idx))
do (pushnew (aref vector (1- idx)) results)
finally (return results)))
About the same as the DOTIMES version. However I might opt for
expressing the removal of duplicates more explicitly, by using
DELETE-DUPLICATES (which also lets me use LOOP's collect mechanism):
(defun precedes (object vector)
(delete-duplicates
(loop for idx from 1 below (length vector)
when (eql object (aref vector idx))
collect (aref vector (1- idx)))
Or for a fairly different way of looking at it, there's already a
function to find the position of a given object in a sequence. Maybe
we can use it:
(defun precedes (object vector)
(delete-duplicates
(loop for start = 1 then (1+ pos)
for pos = (position object vector :start start)
while pos collect (aref vector (1- pos)))))
I don't know if this last one is really better in any way but it's
worth considering that there are a bunch of built in functions for
doing good stuff with sequences.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Martin Pomije <······@MartinPomije.eiomail.com> wrote:
> Define iterative and recursive versions of a function that takes an
> object x and a vector v, and returns a list of all the objects that
> immediately precede x in v.
Graham doesn't like LOOP, but I do. So here's a LOOP-version:
(defun precedes (object vector)
(loop for x across vector
and i from 0
when (and (equal x object) (> i 0))
collect (elt vector (1-i))))
> Define iterative and recursive versions of a function that takes an
> object and a list, and returns a new list in which the object appears
> between each pair of elements in the original list:
This one is also pretty easy with LOOP:
(defun intersperse (x list)
(loop for (a . rest) on list
collect a
when rest
collect x))
Arthur Lemmens
Hi Arthur Lemmens,
> I wrote:
>
>> collect (elt vector (1-i))))
> ^^^
>
> That should have been (1-i), or just (-i 1) if you find
> that easier to read. Sorry.
I know what one of those days feels like ;-) Arthur meant to write:
> That should have been (1- i), or just (- i 1) if you find
> that easier to read. Sorry.
Martin, the form (1- x) should never be pronounced "one minus x". Rather
make sure you always recognise it as "x minus one".
Regards,
Adam
Adam Warner <······@consulting.net.nz> wrote:
> I know what one of those days feels like ;-) Arthur meant to write:
> [I would have quoted Adam here, but it seems that I can't with this
> bloody Opera mailer]
Actually, I wrote exactly the same thing that Adam wrote, but my mailer
thought it knew better. I recently switched to Opera for handling my mail.
It turns out that Opera has a couple of disgusting DWIM habits with respect
to space and return characters. If anybody knows of a way to let Opera respect
my spaces and returns, I'd appreciate a hint. Otherwise, I'll have to switch
to another mailer.
But thanks for correcting me, anyway.
Arthur Lemmens
···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> I usually write these in pairs: a MAP-FOO function, and a DO-FOO
> macro.
Which relies on which?
James Anderson gave me a similar suggestion, but I find it hard to
decide how to relate the two.
--
Steven E. Harris :: ········@raytheon.com
Raytheon :: http://www.raytheon.com
"Steven E. Harris" <········@raytheon.com> writes:
> ···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
> > I usually write these in pairs: a MAP-FOO function, and a DO-FOO
> > macro.
>
> Which relies on which?
One relies on the other :-)
> James Anderson gave me a similar suggestion, but I find it hard to
> decide how to relate the two.
Usually, I write the mapping function, then make the macro just sugar
around it. However, sometimes I need a maximally efficient macro, in
which case, I often put the logic in the DO- macro, and have the body
of the MAP- function just use the macro. The main advantage of the
former is that if you change the function, all the macro uses change
along with it. My rule of thumb: put the logic in the function, and
make the macro be just sugar around it, unless you have a specific
need to do the reverse.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> My rule of thumb: put the logic in the function, and make the macro
> be just sugar around it, unless you have a specific need to do the
> reverse.
I understand that; it's easier to test and easier to change. But am I
correct in seeing that the macro version is usually more efficient
because it cuts out one or more "lambda wrappers" around the loop
body? That is, when the macro calls the mapping function, it must
synthesize a function around the loop body to be funcalled in the
mapping function. If the mapping function calls the macro, no extra
function need be "synthesized."
Hence my indecision.
--
Steven E. Harris :: ········@raytheon.com
Raytheon :: http://www.raytheon.com
"Steven E. Harris" <········@raytheon.com> writes:
> ···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
> > My rule of thumb: put the logic in the function, and make the macro
> > be just sugar around it, unless you have a specific need to do the
> > reverse.
>
> I understand that; it's easier to test and easier to change.
Which should be your main concern, "unless you have a specific need"
otherwise.
> But am I correct in seeing that the macro version is usually more
> efficient because it cuts out one or more "lambda wrappers" around
> the loop body? That is, when the macro calls the mapping function,
> it must synthesize a function around the loop body to be funcalled
> in the mapping function.
One little function indirection doesn't matter most of the time. I
love micro-optimizing code as much as the next guy (actually, probably
much more than the next guy), but one function indirection probably
doesn't matter. If *all* you're doing is calling a thunk that does
nothing, it's probably 4x (or so) slower to use a thunk than to just
do nothing directly. If you do anything more complicated than CDR'ing
down a list, it's probably lost in the noise.
> If the mapping function calls the macro, no extra function need be
> "synthesized."
Well, yeah, but it almost never matters. In those cases where it *is*
useful to avoid the function indirection, however, declaim MAP-FOO
inline. Local use of LAMBDAs should be free.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
* Martin Pomije with an exercise from Paul Grahams ACL:
> Define iterative and recursive versions of a function that takes an
> object and a list, and returns a new list in which the object appears
> between each pair of elements in the original list:
>
> > (intersprerse '- '(a b c d))
> (A - B - C - C)
The iterative variant (loop-less):
(defun intersperse (object list)
(let ((result (and list (list (first list)))))
(dolist (item (rest list) (nreverse result))
(setq result (list* item object result)))))
--
"Hurry if you still want to see something. Everything is vanishing."
-- Paul C�zanne (1839-1906)