As part of a larger program I needed a function which given a number
(n) and a vector (row), returns the index into row of the n'th nil in
row. Here's the first (working) version I came up with:
(defun nth-slot (n v)
"Find the nth nil cell in a vector v."
(loop with slots-seen = 0
for item across v
for idx from 0
counting (not item) into slots-seen
until (> slots-seen n)
finally (if (> slots-seen n) (return idx) (error "No slot"))))
One question right away: is it bad form to use ERROR this way? Given
the context in which this function is used, it's essentially a
pre-condition of this function that there be at least n nils in v. It
seems better to explode on purpose rather than returning something the
caller might choke on if they don't test for it (which they won't
because the only way the pre-condition would be violated is due to
some other programming error at the call site.)
Next, since I'm still learning Lisp I played around with several other
ways of implementing this function. Any preferences between the one
above and any of the ones below?
(defun nth-slot (n v)
(let ((start 0)
pos)
(dotimes (x (1+ n))
(setq pos (position nil v :start start))
(if (not pos) (error "No slot"))
(setq start (1+ pos)))
pos))
(defun nth-slot (n v)
(do* ((count 0 (incf count))
(start 0 (1+ pos))
(pos (position nil v :start start)
(position nil v :start start)))
((>= count n) (or pos (error "No slot")))))
(defun nth-slot (n v)
(loop for count from 0
for start = 0 then (1+ pos)
for pos = (position nil v :start start)
until (or (not pos) (>= count n))
finally (return (or pos (error "No slot")))))
(defun nth-slot (n v &optional (start 0))
(cond
((zerop (length v)) (error "No slot"))
((aref v start) (nth-slot n v (1+ start)))
((zerop n) start)
(t (nth-slot (1- n) v (1+ start)))))
Thanks.
-Peter
--
Peter Seibel
·····@javamonkey.com
Peter Seibel <·····@javamonkey.com> writes:
> As part of a larger program I needed a function which given a number
> (n) and a vector (row), returns the index into row of the n'th nil in
> row. Here's the first (working) version I came up with:
>
> (defun nth-slot (n v)
> "Find the nth nil cell in a vector v."
> (loop with slots-seen = 0
> for item across v
> for idx from 0
> counting (not item) into slots-seen
> until (> slots-seen n)
> finally (if (> slots-seen n) (return idx) (error "No slot"))))
(defun nth-nil (n v &aux (index 1))
(position-if (lambda (x)
(and (null x)
(= n (prog1 index
(incf index))))) ; index-- *is* nice :)
v))
* (setf xxx #(t t t nil t t nil nil t nil nil t))
#(T T T NIL T T NIL NIL T NIL NIL T)
* (nth-nil 0 xxx)
NIL
* (nth-nil 1 xxx)
3
* (nth-nil 2 xxx)
6
* (nth-nil 3 xxx)
7
* (nth-nil 4 xxx)
9
* (nth-nil 5 xxx)
10
* (nth-nil 11 xxx)
NIL
*
> One question right away: is it bad form to use ERROR this way?
Maybe. However, I'd like the NIL returned since it makes NTH-NIL
consistent with POSITION and POSITION-IF.
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
715 Broadway 10th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
"Peter Seibel" <·····@javamonkey.com> wrote in message ···················@localhost.localdomain...
>
> As part of a larger program I needed a function which given a number
> (n) and a vector (row), returns the index into row of the n'th nil in
> row. Here's the first (working) version I came up with:
>
> (defun nth-slot (n v)
> "Find the nth nil cell in a vector v."
> (loop with slots-seen = 0
> for item across v
> for idx from 0
> counting (not item) into slots-seen
> until (> slots-seen n)
> finally (if (> slots-seen n) (return idx) (error "No slot"))))
>
> One question right away: is it bad form to use ERROR this way? Given
> the context in which this function is used, it's essentially a
> pre-condition of this function that there be at least n nils in v. It
How about?
(defun nth-slot (n v)
"Find the nth nil cell in a vector v."
(let ((position 0))
(position n (map 'vector (lambda (cell)
(if (null cell) (incf position) nil))
v))))
I would not personally put a error in there but would wrap the call in some
kind of error handler.
(defmacro error-on-nil (error &body body)
`(or (progn ,@body) (error ,error)))
CL-USER 9 > (error-on-nil "No Slot" (nth-slot 1 '#(1 2 3)))
Error: No Slot
1 (abort) Return to level 0.
2 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
CL-USER 10 : 1 > :c 2
CL-USER 11 > (error-on-nil "No Slot" (nth-slot 1 '#(1 2 nil 10 nil)))
2
CL-USER 12 >
Wade
>>>>> "Wade" == Wade Humeniuk <····@nospam.nowhere> writes:
Wade> "Peter Seibel" <·····@javamonkey.com> wrote in message
Wade> ···················@localhost.localdomain...
>>
>> As part of a larger program I needed a function which given a
>> number (n) and a vector (row), returns the index into row of
>> the n'th nil in row. Here's the first (working) version I came
>> up with:
>>
>> (defun nth-slot (n v)
>> "Find the nth nil cell in a vector v."
>> (loop with slots-seen = 0
>> for item across v
>> for idx from 0
>> counting (not item) into slots-seen
>> until (> slots-seen n)
>> finally (if (> slots-seen n) (return idx) (error "No slot"))))
>>
>> One question right away: is it bad form to use ERROR this way?
>> Given the context in which this function is used, it's
>> essentially a pre-condition of this function that there be at
>> least n nils in v. It
Wade> How about?
Wade> (defun nth-slot (n v)
Wade> "Find the nth nil cell in a vector v."
Wade> (let ((position 0))
Wade> (position n (map 'vector (lambda (cell)
Wade> (if (null cell) (incf position) nil))
Wade> v))))
Well, it'd have to be this to be equivalent to my original (leaving
aside the error question):
(defun nth-slot (n v)
"Find the nth nil cell in a vector v."
(let ((position 0))
(position n
(map 'vector
(lambda (cell)
(if (null cell) (prog1 position (incf position)) nil))
;;-------------------------------> ^^^^^^^^^^^^^^^^ ^
v))))
But that quibble aside, why do you prefer this version? The functional style?
Wade> I would not personally put a error in there but would wrap
Wade> the call in some kind of error handler.
Why not? Is it because this seems like a generally useful function and
error'ing out is a bit extreme? In the context of my program using
error-on-nil as you suggest below would just mean that I'd have to go
change *all* the call sites to use that.
Wade> (defmacro error-on-nil (error &body body)
Wade> `(or (progn ,@body) (error ,error)))
-Peter
--
Peter Seibel
·····@javamonkey.com
"Peter Seibel" <·····@javamonkey.com> wrote in message ···················@localhost.localdomain...
>
> Wade> (defun nth-slot (n v)
> Wade> "Find the nth nil cell in a vector v."
> Wade> (let ((position 0))
> Wade> (position n (map 'vector (lambda (cell)
> Wade> (if (null cell) (incf position) nil))
> Wade> v))))
>
> Well, it'd have to be this to be equivalent to my original (leaving
> aside the error question):
>
> (defun nth-slot (n v)
> "Find the nth nil cell in a vector v."
> (let ((position 0))
> (position n
> (map 'vector
> (lambda (cell)
> (if (null cell) (prog1 position (incf position)) nil))
> ;;-------------------------------> ^^^^^^^^^^^^^^^^ ^
> v))))
>
>
> But that quibble aside, why do you prefer this version? The functional style?
You could just change the intial binding of position to -1 to handle 0 indexing.
Well, I looked at your functions and though in practice I would write them
like you did I had a sudden vision that they were too like C. So I coded
something different (as you said in a more functional style). I just
get tired after a while of coding things in loops, but instead see some
elegance in coding it in a transformational style.
I must say to really make a storage algorithm like this fly I would
create a specialized data type that holds the pre-hashed information
where the nth nil is. When the nth element is altered I would calculate
the new nil positions and store this info in this specialized data structure.
Using a generic vector is ok but as you see a lot of potential calculation
is needed (and it seems it might be what you are worried about).
>
> Wade> I would not personally put a error in there but would wrap
> Wade> the call in some kind of error handler.
>
> Why not? Is it because this seems like a generally useful function and
> error'ing out is a bit extreme? In the context of my program using
> error-on-nil as you suggest below would just mean that I'd have to go
> change *all* the call sites to use that.
>
> Wade> (defmacro error-on-nil (error &body body)
> Wade> `(or (progn ,@body) (error ,error)))
How many places are we talking? The reasons I think I would do this are:
nth-slot is a general utlity functions, in general I do not think utility
functions should not signal errors (unless they are type errors).
Think of assoc as an example.
This feels like an error which needs some kind of decision about
what to do when there is a problem. With an error-on-nil type of
wrapper I can change that error recovery functionality later on
if it is needed. So I put it in a centralized, orthogonal place (Lisp error
handling seems to be conceptualy orthogonal) for thought and
further consideration.
Wade
Peter Seibel <·····@javamonkey.com> writes:
> As part of a larger program I needed a function which given a number
> (n) and a vector (row), returns the index into row of the n'th nil in
> row. Here's the first (working) version I came up with:
>
> (defun nth-slot (n v)
> "Find the nth nil cell in a vector v."
> (loop with slots-seen = 0
> for item across v
> for idx from 0
> counting (not item) into slots-seen
> until (> slots-seen n)
> finally (if (> slots-seen n) (return idx) (error "No slot"))))
Here's how I'd write it (criticism welcome, of course!):
(defun nth-slot (n vector)
(loop for index from 0 below (length vector)
if (null (aref vector index))
do (decf n)
(when (zerop n)
(return index))))
> One question right away: is it bad form to use ERROR this way?
I'd write it to return NIL if there weren't n slots, and either check
the return value or write a function to do it for me:
(defun assured-nth-slot (n vector)
(or (nth-slot n vector)
(error "~A doesn't contain ~D NIL's!" vector n)))
Personally, I wouldn't expect a function like nth-slot to signal an
error because FIND, POSITION, etc. don't signal an error if the
sequence being searched doesn't contain what's being looked for.
You're also more likely to re-use a function like nth-slot if it
doesn't signal an error because you might someday want to use it
in code where it isn't an error...
Gabe Garza
Peter Seibel wrote:
> As part of a larger program I needed a function which given a number
> (n) and a vector (row), returns the index into row of the n'th nil in
> row. Here's the first (working) version I came up with:
>
> (defun nth-slot (n v)
> "Find the nth nil cell in a vector v."
> (loop with slots-seen = 0
> for item across v
> for idx from 0
> counting (not item) into slots-seen
> until (> slots-seen n)
> finally (if (> slots-seen n) (return idx) (error "No slot"))))
Please take that inscrutal glop to comp.lang.loop. <g>
(defun nth-null-slot-index (n v &optional must-find-p &aux (nil-ct 0))
"Return the index of the nth nil cell in vector v"
(dotimes (x (length v) (when must-find-p (error "bzzzt")))
(when (null (elt v x))
(when (= n (incf nil-ct)) ;; [1]
(return-from nth-null-slot-index x)))))
(nth-null-slot-index 3 #(nil 1 2 nil 3 4 nil 5 nil nil))
=>6
seriously, the loop bit demonstrates incredible mastery of that, um,
feature, but what strikes me is that it both giveth and taketh away--it
seems like english, but it's not at all, so stop the charade. i /know/
what it is doing so i can work backwards from the faux natural language
to the honest code into which it will expand, but the faux NL part does
nothing to help and in fact gets in the way because I have to clap my
hands over my hears so as not to hear the NL semantics.
--
1. I'm no looper, but I think your semantics were that n=0 should return
the index of the 1st null slot. hmm, I know /indexing/ starts at zero,
but doesn't counting start at 1? ie, the first (1th) null might be at
index 0?
kenny tilton
clinisys, inc
---------------------------------------------------------------
""Well, I've wrestled with reality for thirty-five years, Doctor,
and I'm happy to state I finally won out over it.""
Elwood P. Dowd
>>>>> "Kenny" == Kenny Tilton <·······@nyc.rr.com> writes:
Kenny> Peter Seibel wrote:
>> As part of a larger program I needed a function which given a
>> number (n) and a vector (row), returns the index into row of
>> the n'th nil in row. Here's the first (working) version I came
>> up with: (defun nth-slot (n v)
>> "Find the nth nil cell in a vector v."
>> (loop with slots-seen = 0
>> for item across v
>> for idx from 0
>> counting (not item) into slots-seen
>> until (> slots-seen n)
>> finally (if (> slots-seen n) (return idx) (error "No slot"))))
Kenny> Please take that inscrutal glop to comp.lang.loop. <g>
;-)
Kenny> (defun nth-null-slot-index (n v &optional must-find-p &aux (nil-ct 0))
Kenny> "Return the index of the nth nil cell in vector v"
Kenny> (dotimes (x (length v) (when must-find-p (error "bzzzt")))
Kenny> (when (null (elt v x))
Kenny> (when (= n (incf nil-ct)) ;; [1]
Kenny> (return-from nth-null-slot-index x)))))
Kenny> (nth-null-slot-index 3 #(nil 1 2 nil 3 4 nil 5 nil nil))
Kenny> =>6
Kenny> seriously, the loop bit demonstrates incredible mastery of
Kenny> that, um, feature, but what strikes me is that it both
Kenny> giveth and taketh away--it seems like english, but it's not
Kenny> at all, so stop the charade. i /know/ what it is doing so i
Kenny> can work backwards from the faux natural language to the
Kenny> honest code into which it will expand, but the faux NL part
Kenny> does nothing to help and in fact gets in the way because I
Kenny> have to clap my hands over my hears so as not to hear the
Kenny> NL semantics.
It did seem like a bit much by the time I was done with it. Thus my
question. I like your version a lot. Though I thought &aux variables
were frowned upon? But what do you know? You don't even like LOOP. ;-)
Kenny> 1. I'm no looper, but I think your semantics were that n=0
Kenny> should return the index of the 1st null slot. hmm, I know
Kenny> /indexing/ starts at zero, but doesn't counting start at 1?
Kenny> ie, the first (1th) null might be at index 0?
Actually, I have the brain damage enough that I start counting things
from the zero.[1] So I'd write your version of the function as:
(defun nth-slot (n v &aux (nil-ct -1))
"Return the index of the nth nil cell in vector v"
(dotimes (x (length v) (error "bzzzt"))
(when (null (elt v x))
(when (= n (incf nil-ct))
(return-from nth-slot x)))))
FWIW, that's consistent with NTH.
[1] CL-USER(6264): (defvar *mylist* '(a b c))
*MYLIST*
[1] CL-USER(6271): (nth 0 *mylist*)
A
[1] CL-USER(6274): (nth 1 *mylist*)
B
[1] CL-USER(6275): (nth 2 *mylist*)
C
[1] CL-USER(6276): (nth (length *mylist*) *mylist*)
NIL
-Peter
[1] I knew it was bad one time when I was programming and listening to
a CD. I wanted to know what song I was listening to so I looked at the
CD player and it said Track 7. I pick up the CD jewel box and look at
the track listing--no numbers, just the titles. So I start counting,
0, 1, 2, ... Doh!
--
Peter Seibel
·····@javamonkey.com
Peter Seibel wrote:
> Though I thought &aux variables
> were frowned upon?
Yep. I guess it goes back to my 24x80 VT100 days, hate to give up a
level of indentation just to get a local variable initialized to null
into the game.
> Actually, I have the brain damage enough that I start counting things
> from the zero.[1] ... FWIW, that's consistent with NTH.
It's worth a lot. I don't use nth, did not know that. gotta be
consistent if yer using nth (and i imagine if I /used/ nth zero<=>first
would make sense to me, Lisp is like that).
> [1] I knew it was bad one time when I was programming and listening to
> a CD. I wanted to know what song I was listening to so I looked at the
> CD player and it said Track 7. I pick up the CD jewel box and look at
> the track listing--no numbers, just the titles. So I start counting,
> 0, 1, 2, ... Doh!
Was that Roberta Flack's "The Zeroeth Time Ever I saw Your Face"?
:)
--
kenny tilton
clinisys, inc
---------------------------------------------------------------
""Well, I've wrestled with reality for thirty-five years, Doctor,
and I'm happy to state I finally won out over it.""
Elwood P. Dowd
Hello!
Kenny Tilton <·······@nyc.rr.com> wrote:
>Peter Seibel wrote:
>> Though I thought &aux variables
>> were frowned upon?
>Yep. I guess it goes back to my 24x80 VT100 days, hate to give up a
>level of indentation just to get a local variable initialized to null
>into the game.
I'm still using 80 columns wide editor windows.
And if one "let" indentation pushes your code over that boundary,
it's too wide anyway.
>[...]
Kind regards,
Hannah.
Hannah Schroeter wrote:
> Hello!
>
> Kenny Tilton <·······@nyc.rr.com> wrote:
>
>
>>Peter Seibel wrote:
>>
>>> Though I thought &aux variables
>>>were frowned upon?
>>
>
>>Yep. I guess it goes back to my 24x80 VT100 days, hate to give up a
>>level of indentation just to get a local variable initialized to null
>>into the game.
>
>
> I'm still using 80 columns wide editor windows.
>
> And if one "let" indentation pushes your code over that boundary,
> it's too wide anyway.
Actually, it is precisely because I have such a low threshhold for
indentation that I do not want to throw one level away on:
(let (temp)
...actually interesting stuff...
So i (sometimes) do a little premature indentation optimization and &aux
that bad boy in there.
:)
--
kenny tilton
clinisys, inc
---------------------------------------------------------------
""Well, I've wrestled with reality for thirty-five years, Doctor,
and I'm happy to state I finally won out over it.""
Elwood P. Dowd
Kenny Tilton <·······@nyc.rr.com> writes:
> Please take that inscrutal glop to comp.lang.loop. <g>
I guess I'll chip in a vote for the LOOP form. To me,
it seemed quite readable, and although I liked your
version as well, the RETURN-FROM form in it makes me
weigh in for the LOOP. I guess I just prefer FINALLY
to RETURN-FROM.
[This is not to denigrate your code; just to give Peter
some support! :-)]
Alain Picard wrote:
> Kenny Tilton <·······@nyc.rr.com> writes:
>
>
>>Please take that inscrutal glop to comp.lang.loop. <g>
>
>
> I guess I'll chip in a vote for the LOOP form...
I'll go for Jochen's, and overall I think we should all at least agree
not to generate an error since mimicking NTH is now part of the spec. As
someone said, handle errors in a wrapper dedicated to the semantic level
at which nil is a problem.
--
kenny tilton
clinisys, inc
---------------------------------------------------------------
""Well, I've wrestled with reality for thirty-five years, Doctor,
and I'm happy to state I finally won out over it.""
Elwood P. Dowd
Peter Seibel wrote:
How about
(defun nth-slot (n v &aux (nth-nil -1))
(position-if (lambda (e) (and (null e) (= n (incf nth-nil)))) v))
And if you really want the error instead of returning nil:
(defun nth-slot (n v &aux (nth-nil -1))
(or (position-if (lambda (e) (and (null e) (= n (incf nth-nil)))) v)
(error "n is too big")))
ciao,
Jochen
--
http://www.dataheaven.de
Jochen Schmidt wrote:
> Peter Seibel wrote:
>
> How about
>
> (defun nth-slot (n v &aux (nth-nil -1))
> (position-if (lambda (e) (and (null e) (= n (incf nth-nil)))) v))
>
> And if you really want the error instead of returning nil:
>
> (defun nth-slot (n v &aux (nth-nil -1))
> (or (position-if (lambda (e) (and (null e) (= n (incf nth-nil)))) v)
> (error "n is too big")))
Oops as I see now others have already submitted solutions very similar to
mine...
ciao,
Jochen
"Peter Seibel" <·····@javamonkey.com> wrote in message
···················@localhost.localdomain...
>
> As part of a larger program I needed a function which given a number
> (n) and a vector (row), returns the index into row of the n'th nil in
> row. Here's the first (working) version I came up with:
>
> (defun nth-slot (n v)
> "Find the nth nil cell in a vector v."
> (loop with slots-seen = 0
> for item across v
> for idx from 0
> counting (not item) into slots-seen
> until (> slots-seen n)
> finally (if (> slots-seen n) (return idx) (error "No slot"))))
>
> One question right away: is it bad form to use ERROR this way?
I personally would not expect an error to be thrown here if I were a user of
this code. NIL is just fine for saying it wasn't found and is the standard
idiom, the caller should decide what action to take. If as you say later
all of your callers will behave the same, perhaps write another thin wrapper
function that throws the error and give it a better name. nth-slot (why is
it not find-nth-nil ?) does not suggest it *must* be there. If that really
is your usage, then i strongly suspect you can and should give it a more
descriptive name based on what it is *really* doing in your application.
I caution about using loop variables in finally clauses: they are not always
what one (well, I) might expect. See this:
CL-USER 152 > (loop for i upfrom 0
for elt across #(0 1 2 3)
finally (return i))
4
CL-USER 153 > (loop for elt across #(0 1 2 3)
for i upfrom 0
finally (return i))
3
CL-USER 154 > (loop for i below 5 finally (return i))
5
I don't try to be a language lawyer, but my impression is none of this is
buggy but is the result of undefined behaviour.
> Given
> the context in which this function is used, it's essentially a
> pre-condition of this function that there be at least n nils in v.
This is why I think you don't have its True Name ;)
> (defun nth-slot (n v)
> (do* ((count 0 (incf count))
> (start 0 (1+ pos))
> (pos (position nil v :start start)
> (position nil v :start start)))
> ((>= count n) (or pos (error "No slot")))))
Every DO I see makes me less interested in using it!
>
> (defun nth-slot (n v)
> (loop for count from 0
> for start = 0 then (1+ pos)
> for pos = (position nil v :start start)
> until (or (not pos) (>= count n))
> finally (return (or pos (error "No slot")))))
You used pos before you declared it... seems like a bad idea?
> (defun nth-slot (n v &optional (start 0))
> (cond
> ((zerop (length v)) (error "No slot"))
> ((aref v start) (nth-slot n v (1+ start)))
> ((zerop n) start)
> (t (nth-slot (1- n) v (1+ start)))))
Yech. Never use recursion when you are really just iterating. (IMO)
Lisp offers so many ways to skin a cat...no wonder cats hate Lisp ;)
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
>>>>> "Coby" == Coby Beck <·····@mercury.bc.ca> writes:
Coby> "Peter Seibel" <·····@javamonkey.com> wrote in message
Coby> ···················@localhost.localdomain...
>>
>> As part of a larger program I needed a function which given a number
>> (n) and a vector (row), returns the index into row of the n'th nil in
>> row. Here's the first (working) version I came up with:
>>
>> (defun nth-slot (n v)
>> "Find the nth nil cell in a vector v."
>> (loop with slots-seen = 0
>> for item across v
>> for idx from 0
>> counting (not item) into slots-seen
>> until (> slots-seen n)
>> finally (if (> slots-seen n) (return idx) (error "No slot"))))
>>
>> One question right away: is it bad form to use ERROR this way?
Coby> I personally would not expect an error to be thrown here if
Coby> I were a user of this code. NIL is just fine for saying it
Coby> wasn't found and is the standard idiom, the caller should
Coby> decide what action to take. If as you say later all of your
Coby> callers will behave the same, perhaps write another thin
Coby> wrapper function that throws the error and give it a better
Coby> name. nth-slot (why is it not find-nth-nil ?) does not
Coby> suggest it *must* be there. If that really is your usage,
Coby> then i strongly suspect you can and should give it a more
Coby> descriptive name based on what it is *really* doing in your
Coby> application.
Okay, based on this (and other folks comments) I think the real
problem here is that the name I chose sound too general. Though it's
mildly amusing that on the one hand nth-slot is general enough that
everyone expects it to do the general thing of returning nil but you
still suggest that I should really rename it find-nth-nil. I even
thought, at one point, about renaming it to nth-nil but then decided
that would imply a more general function that it really is. So, in my
app (which is itself a very simple program) this really is a private
little utility function and since I don't happen to need the more
general function there's no reason to split them apart.
Coby> I caution about using loop variables in finally clauses:
Coby> they are not always what one (well, I) might expect. See
Coby> this:
Coby> CL-USER 152 > (loop for i upfrom 0
Coby> for elt across #(0 1 2 3)
Coby> finally (return i))
Coby> 4
Coby> CL-USER 153 > (loop for elt across #(0 1 2 3)
Coby> for i upfrom 0
Coby> finally (return i))
Coby> 3
Coby> CL-USER 154 > (loop for i below 5 finally (return i))
Coby> 5
Coby> I don't try to be a language lawyer, but my impression is
Coby> none of this is buggy but is the result of undefined
Coby> behaviour.
Is it even undefined? I'd have to read (I think) 6.1.2.1 more
carefully than I have the energy for right now. But at any rate, even
if a language lawyer does say it's okay, probably better to avoid
things that give non-language-lawyers the heebie-jeebies.
>> Given the context in which this function is used, it's
>> essentially a pre-condition of this function that there be at
>> least n nils in v.
Coby> This is why I think you don't have its True Name ;)
Fair enough. I should probably call it find-nth-empty-spot-for-piece
or something as it happens to be being used in little program that
generates a random board setting for Fischer Random Chess[1]. Then no
one would probably mind that it ERROR's out.
>> (defun nth-slot (n v)
>> (loop for count from 0
>> for start = 0 then (1+ pos)
>> for pos = (position nil v :start start)
>> until (or (not pos) (>= count n))
>> finally (return (or pos (error "No slot")))))
Coby> You used pos before you declared it... seems like a bad
Coby> idea?
I was wondering about that. It seemed to work but it was on my list to
go back to the CLHS and figure out if that's actually legal. My theory
of why it might be legal is that I'm not *actually* using pos before
(in a chronological sense) it's declared because it's in the stepping
form, not the initialization form. But it does look a bit odd.
>> (defun nth-slot (n v &optional (start 0))
>> (cond
>> ((zerop (length v)) (error "No slot"))
>> ((aref v start) (nth-slot n v (1+ start)))
>> ((zerop n) start)
>> (t (nth-slot (1- n) v (1+ start)))))
Coby> Yech. Never use recursion when you are really just
Coby> iterating. (IMO)
Indeed. I just threw this one in to make sure I could figure it out in
case I ever decided I wanted to be a Scheme programmer. ;-)
-Peter
[1] <http://www.chessvariants.com/diffsetup.dir/fischer.html>
--
Peter Seibel
·····@javamonkey.com
From: Larry Clapp
Subject: Re: Better way to write this function?
Date:
Message-ID: <e1cqsa.fcc.ln@127.0.0.1>
In article <··············@localhost.localdomain>, Peter Seibel wrote:
>>>>>> "Coby" == Coby Beck <·····@mercury.bc.ca> writes:
> >> (defun nth-slot (n v)
> >> (loop for count from 0
> >> for start = 0 then (1+ pos)
> >> for pos = (position nil v :start start)
> >> until (or (not pos) (>= count n))
> >> finally (return (or pos (error "No slot")))))
>
> Coby> You used pos before you declared it... seems like a bad
> Coby> idea?
>
> I was wondering about that. It seemed to work but it was on my list to go
> back to the CLHS and figure out if that's actually legal. My theory of why
> it might be legal is that I'm not *actually* using pos before (in a
> chronological sense) it's declared because it's in the stepping form, not
> the initialization form. But it does look a bit odd.
In CMUCL the loop expands to
(LET ((COUNT 0))
(DECLARE (TYPE REAL COUNT))
(LET ((START NIL))
(LET ((POS NIL))
(BLOCK NIL
(ANSI-LOOP::LOOP-BODY NIL
; <snip>
((RETURN (OR POS (ERROR "No slot")))))))))
, which shows POS defined before use.
Can one reliably deduce anything from a macroexpansion from a given
implementation?
-- Larry
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
Peter Seibel <·····@javamonkey.com> writes:
> As part of a larger program I needed a function which given a number
> (n) and a vector (row), returns the index into row of the n'th nil in
> row. Here's the first (working) version I came up with:
>
> (defun nth-slot (n v)
> "Find the nth nil cell in a vector v."
> (loop with slots-seen = 0
> for item across v
> for idx from 0
> counting (not item) into slots-seen
> until (> slots-seen n)
> finally (if (> slots-seen n) (return idx) (error "No slot"))))
>
> One question right away: is it bad form to use ERROR this way? Given
> the context in which this function is used, it's essentially a
> pre-condition of this function that there be at least n nils in v. It
> seems better to explode on purpose rather than returning something the
> caller might choke on if they don't test for it (which they won't
> because the only way the pre-condition would be violated is due to
> some other programming error at the call site.)
Well, I would be tempted to use a more specific CONDITION than the
default that you get with ERROR, but if you aren't planning to catch
the error, then this would work as well. The reason for using a more
specific condition is that it will have the same effect as using
error, but leaves open the possibility that you will, in the future,
more easily be able to change the way you handle this particular
problem.
In other words, your function becomes more easily reusable.
Actually, as I think about it even more, I would prefer returning NIL
from this function and raising the error in the caller. That way you
avoid making a commitment in the low-level utility function about how
to handle the situation with missing NIL values. In fact, you can
make this a much more general purpose routine by doing something like
the following. I use the loop form, even though it needs repetition
to handle both lists and vectors because it has better performance
on lists than a POSITION-based approach like you outline below.
(defun nth-position (target sequence n)
(etypecase sequence
(LIST
(loop with slots-seen = 0
for item in sequence
for idx from 0
counting (eq target item) into slots-seen
until (> slots-seen n)
finally (if (> slots-seen n) (return idx) (return NIL))))
(VECTOR
(loop with slots-seen = 0
for item across sequence
for idx from 0
counting (eq target item) into slots-seen
until (> slots-seen n)
finally (if (> slots-seen n) (return idx) (return NIL))))))
Then you call (nth-position nil sequence n).
>
> Next, since I'm still learning Lisp I played around with several other
> ways of implementing this function. Any preferences between the one
> above and any of the ones below?
As noted above, the following ones will work on lists as well as
vectors, but repeatedly calling POSITION on a list is inefficient
since it will have to start traversing the list from the beginning
on each call, leading to O (N * (length V)) runtime behavior, instead
of just O ((length V)).
> (defun nth-slot (n v)
> (let ((start 0)
> pos)
> (dotimes (x (1+ n))
> (setq pos (position nil v :start start))
> (if (not pos) (error "No slot"))
> (setq start (1+ pos)))
> pos))
>
> (defun nth-slot (n v)
> (do* ((count 0 (incf count))
> (start 0 (1+ pos))
> (pos (position nil v :start start)
> (position nil v :start start)))
> ((>= count n) (or pos (error "No slot")))))
>
> (defun nth-slot (n v)
> (loop for count from 0
> for start = 0 then (1+ pos)
> for pos = (position nil v :start start)
> until (or (not pos) (>= count n))
> finally (return (or pos (error "No slot")))))
>
> (defun nth-slot (n v &optional (start 0))
> (cond
> ((zerop (length v)) (error "No slot"))
> ((aref v start) (nth-slot n v (1+ start)))
> ((zerop n) start)
> (t (nth-slot (1- n) v (1+ start)))))
BTW, you show a very good command of the Lisp forms for someone
self-described as "still learning Lisp"!
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu