* 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)))))
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.
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.
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))))
Arthur Lemmens 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))))
Look at that:(4 9)
(1-i)
Don't you think that that should be:
(1- i)
or
(- i 1)
?
It's shorter when you use a Lispy language instead of CL.
Gauche Scheme
(use srfi-42) ; list-ec
(define (precedes obj vec)
(list-ec (: x (index i) vec)
(if (and (> i 0) (equal? x obj)))
(ref vec (- i 1))))
(precedes 5 #(5 0 4 5 8 9 5))
(4 9)
Another way:
(define (precedes o v)
(let ((l (vector->list vec)))
(filter-map
(^(a b) (and (equal? o a) b))
(cdr l)
l)))
(match @(scan-all (@x 5 . @nil)) '(5 0 4 5 8 9 5) x)
(window-mappend 1 nil (do if (and @1 (= @2 5)) (list @1)) #(5 0 4 5 8 9 5))#(4 9)
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 388 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 09:58:44 |
| Calls: | 8,221 |
| Files: | 13,122 |
| Messages: | 5,872,631 |