The following input
(loop for x in '(1 2 3 4)
for y upfrom 0
collect x into temp
when (oddp y)
collect temp
and do (print temp)
(setq temp nil))
results in
(1 2)
(3 4)
((1 2) (3 4))
with CLISP and LispWorks - which is what I expected. But CMUCL shows
(1 2)
(1 2 3 4)
((1 2 3 4) (1 2 3 4))
instead. Is this a bug or are both behaviors conforming?
(Pardon me if this is trivial, I'm just starting with LOOP...)
Thanks,
Edi.
In article <··············@duke.agharta.de>,
Dr. Edmund Weitz <···@agharta.de> wrote:
>The following input
>
> (loop for x in '(1 2 3 4)
> for y upfrom 0
> collect x into temp
> when (oddp y)
> collect temp
> and do (print temp)
> (setq temp nil))
>
>results in
>
> (1 2)
> (3 4)
> ((1 2) (3 4))
>
>with CLISP and LispWorks - which is what I expected. But CMUCL shows
>
> (1 2)
> (1 2 3 4)
> ((1 2 3 4) (1 2 3 4))
>
>instead. Is this a bug or are both behaviors conforming?
>
>(Pardon me if this is trivial, I'm just starting with LOOP...)
The LOOP specification is silent about how it keeps track of the values
it's accumulating with COLLECT or what happens if you modify the INTO
variable out from under it. So don't do it: if it doesn't say what the
effect is, you can't depend on anything.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
···@agharta.de (Dr. Edmund Weitz) writes:
> The following input
>
> (loop for x in '(1 2 3 4)
> for y upfrom 0
> collect x into temp
> when (oddp y)
> collect temp
> and do (print temp)
> (setq temp nil))
>
> results in
>
> (1 2)
> (3 4)
> ((1 2) (3 4))
>
> with CLISP and LispWorks - which is what I expected. But CMUCL shows
>
> (1 2)
> (1 2 3 4)
> ((1 2 3 4) (1 2 3 4))
>
> instead. Is this a bug or are both behaviors conforming?
>
> (Pardon me if this is trivial, I'm just starting with LOOP...)
I'll look at this later, and maybe someone will chime in before I do
with a spec analysis, but a good programming style rule for dealing
with LOOP is that if it's doing management of a variable's assignment,
you should not assign it manually. Whenever I want to do something
like you've got here, I basically assume I want to take control of the
implementation, and so I resort to lower-level primitives rather than
trying to "fake out" the higher-level ones. That doesn't mean you
aren't within your rights, of course. It's just that if I had my say,
you really wouldn't be. It cramps LOOP's style too much for you to be
allowed to do what you're doing.
Just my personal opinion.
Kent M Pitman <······@world.std.com> writes:
> I'll look at this later, and maybe someone will chime in before I do
> with a spec analysis, but a good programming style rule for dealing
> with LOOP is that if it's doing management of a variable's
> assignment, you should not assign it manually. Whenever I want to
> do something like you've got here, I basically assume I want to take
> control of the implementation, and so I resort to lower-level
> primitives rather than trying to "fake out" the higher-level ones.
> That doesn't mean you aren't within your rights, of course. It's
> just that if I had my say, you really wouldn't be. It cramps LOOP's
> style too much for you to be allowed to do what you're doing.
>
> Just my personal opinion.
Thanks for your reply (and also thanks to Barry Margolin). I
understand now that I shouldn't mess with variables that are managed
by LOOP. [I took a quick peek at CMUCL's and CLISP's macro expansion
of my LOOP code and that gave me an idea why I really shouldn't do
what I did... :)]
Let me bother you with another thing that came to my mind while
working with this problem:
What I actually wanted to have was a function that - for want of
better words - I called SUBDIVIDE. It was intended to accept a list
and return a list of lists of length INCR such that the concatenation
of these lists would result in the original list, i.e.
(subdivide '(1 2 3 4 5 6) :incr 2) => ((1 2) (3 4) (5 6))
My first attempt was this function:
(defun subdivide (list &key (incr 1))
(let ((counter 0))
(labels ((get-subseq-or-nil (seq)
(prog1
(if (= 0 (mod counter incr))
(subseq seq 0 (min incr (length seq)))
nil)
(incf counter))))
(delete nil
(maplist #'get-subseq-or-nil list)))))
Now, while this did what I wanted, I wasn't happy with my solution
'cause I created a lot of NIL entries with the call to MAPLIST only to
get rid of them afterwards with DELETE. This was why I started to
think about using LOOP and why I came up with the problem I discussed
in my orginal posting.
I now have another version, using LOOP, that I like better than the
first attempt:
(defun subdivide (list &key (incr 1))
(loop for sublist on list by #'(lambda (list)
(nthcdr incr list))
collect (subseq sublist 0 (min incr (length sublist)))))
This one also seems to work. My problem is: I started learning CL
about ten months ago (working on it in my spare time) and my feeling
is that the language seems so big and powerful to me that I'm almost
always looking at my code and beginning to suspect that there _must_
be a significantly better (shorter, more elegant, less CONSing,
whatever) solution. I know that you can't help me with this but maybe
you can look at this particular function and tell me what might be
wrong with it. I'm sure there's a better way of doing this but I can't
see it (yet). [The worst scenario would be that there's already a CL
function that's doing what I want, I've read it about some months ago
but I forgot it... :)]
Thanks in advance for your time,
Edi.
···@agharta.de (Dr. Edmund Weitz) writes:
> I now have another version, using LOOP, that I like better than the
> first attempt:
>
> (defun subdivide (list &key (incr 1))
> (loop for sublist on list by #'(lambda (list)
> (nthcdr incr list))
> collect (subseq sublist 0 (min incr (length sublist)))))
>
> This one also seems to work. My problem is: I started learning CL
> about ten months ago (working on it in my spare time) and my feeling
> is that the language seems so big and powerful to me that I'm almost
> always looking at my code and beginning to suspect that there _must_
> be a significantly better (shorter, more elegant, less CONSing,
> whatever) solution.
The following is what came to me in the first 15 seconds thinking about
this. I didn't test it extensively but it seems right. But keep in mind,
even if you like this one better, that I wrote it having the benefit of
your analysis and not cold from a problem description. So even if it is
"better" (and I'm not asserting on such brief thought that it is), you
shouldn't dispair. There's a phenomenon called "having someone look over
your shoulder" which is "known" in CS to always produce better results in
shorter time than the person sitting at the chair banging away endlessly
the first time. Just explaining it to someone else invariably results in
them pointing out something obvious. Would probably have worked the same
in reverse (e.g., people are always pointing out really obvious fixes to
my code here, and I try not to let it get me, and instead write it off
to the same thing):
CL-USER 1 > (defun subdivide (list &optional (increment 1))
(let ((tail list))
(loop while tail
collect (loop repeat increment
while tail
collect (pop tail)))))
SUBDIVIDE
CL-USER 2 > (subdivide '(a b c d e f g) )
((A) (B) (C) (D) (E) (F) (G))
CL-USER 3 > (subdivide '(a b c d e f g) 2)
((A B) (C D) (E F) (G))
Oh, sorry about not making that &key like you did. I'll leave you to fix
that...
> I know that you can't help me with this
Well, the generic piece of information I can give you is that if you're
having to traverse the list twice, you can probably make it more elegant.
Then again double list traversal just means O(2n) instead of O(n) and since
O(2n)=O(n), it's not a huge deal either way.
> but maybe
> you can look at this particular function and tell me what might be
> wrong with it. I'm sure there's a better way of doing this but I can't
> see it (yet). [The worst scenario would be that there's already a CL
> function that's doing what I want, I've read it about some months ago
> but I forgot it... :)]
As far as I know, there are some functions that come close, but not
quite. (Then again, there are functions I fail to use sometimes, too,
so my lack of noting one is no formal proof that you haven't
overlooked something. :-) I was almost going to try something with
LDIFF instead of SUBSEQ but it gets you the same end as you had
already. EVEN SO, you might find it fun to try LDIFF instead of
SUBSEQ in your version, just to learn about how it works. I think the
LDIFF solution is "as good" and I think LDIFF is often overlooked
where it can be used, usually out of people not knowing it's there.
Kent M Pitman <······@world.std.com> writes:
> CL-USER 1 > (defun subdivide (list &optional (increment 1))
> (let ((tail list))
> (loop while tail
> collect (loop repeat increment
> while tail
> collect (pop tail)))))
>
> [...]
>
> As far as I know, there are some functions that come close, but not
> quite. (Then again, there are functions I fail to use sometimes,
> too, so my lack of noting one is no formal proof that you haven't
> overlooked something. :-) I was almost going to try something with
> LDIFF instead of SUBSEQ but it gets you the same end as you had
> already. EVEN SO, you might find it fun to try LDIFF instead of
> SUBSEQ in your version, just to learn about how it works. I think
> the LDIFF solution is "as good" and I think LDIFF is often
> overlooked where it can be used, usually out of people not knowing
> it's there.
Yes, as I expected I learned at least two things:
1. a better way to solve my problem using a LOOP technique that I
probably wouldn't have come up with myself
2. a function (LDIFF) that I didn't know so far (or only, er,
subconsciously)
Looks like I should read my daily dose of the CLHS instead of the
newspaper during breakfast... :)
Thanks again,
Edi.
PS: For the sake of completeness, here's my take on LDIFF
(defun subdivide (list &key (incr 1))
(loop for sublist on list by #'(lambda (list)
(nthcdr incr list))
collect (ldiff sublist (nthcdr incr sublist))))
As far as I can see this version is also in the O(2n) ballpark which I
think you anticipated.
···@agharta.de (Dr. Edmund Weitz) writes:
> PS: For the sake of completeness, here's my take on LDIFF
>
> (defun subdivide (list &key (incr 1))
> (loop for sublist on list by #'(lambda (list)
> (nthcdr incr list))
> collect (ldiff sublist (nthcdr incr sublist))))
>
> As far as I can see this version is also in the O(2n) ballpark which I
> think you anticipated.
I was thinking something more like the following. Doing two identical
nthcdrs should make you suspicious...
(defun subdivide (list &optional (increment 1))
(loop with sublist = list
while sublist
for next = (nthcdr increment sublist)
collect (ldiff sublist next)
do (setq sublist next)))
Kent M Pitman <······@world.std.com> writes:
> I was thinking something more like the following. Doing two
> identical nthcdrs should make you suspicious...
Urgh - it did. I just couldn't see how to get rid of this with my yet
limited experience with LOOP. Now I can... :)
> (defun subdivide (list &optional (increment 1))
> (loop with sublist = list
> while sublist
> for next = (nthcdr increment sublist)
> collect (ldiff sublist next)
> do (setq sublist next)))
Kent M Pitman <······@world.std.com> writes:
> ···@agharta.de (Dr. Edmund Weitz) writes:
>
> > PS: For the sake of completeness, here's my take on LDIFF
> >
> > (defun subdivide (list &key (incr 1))
> > (loop for sublist on list by #'(lambda (list)
> > (nthcdr incr list))
> > collect (ldiff sublist (nthcdr incr sublist))))
> >
> > As far as I can see this version is also in the O(2n) ballpark which I
> > think you anticipated.
>
> I was thinking something more like the following. Doing two identical
> nthcdrs should make you suspicious...
>
> (defun subdivide (list &optional (increment 1))
> (loop with sublist = list
> while sublist
> for next = (nthcdr increment sublist)
> collect (ldiff sublist next)
> do (setq sublist next)))
Actually I think you are not allowed to do it this way: LOOP requires
that variable binding clauses appear before main-clauses like while.
The MIT loop code does allow it, and deals with it correctly, and most
independent implementations seem to also allow it, though some warn
about this. But sadly the standard doesn't require this (I think
there were reservations about the exact semantics of mixing and
matching such clauses). I say sadly, because this forces portable
code to sometimes be much more convoluted than would otherwise have
been necessary. Interleaving stepping and checking clauses is a very
common idiom, which could have been supported by LOOP.
In this case one can just fudge it by interchanging the for and while
clauses, because nthcdr also works on nil, but often it isn't possible
to do this, so that one has to write quite convoluted code instead.
(defun subdivide (list &optional (increment 1))
(loop with sublist = list
for next = (nthcdr increment sublist)
while sublist
collect (ldiff sublist next)
do (setq sublist next)))
Regs, Pierre.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
In article <··············@duke.agharta.de>, ···@agharta.de (Dr. Edmund
Weitz) wrote:
>2. a function (LDIFF) that I didn't know so far (or only, er,
> subconsciously)
LDIFF may win a prize for the simplest, oldest, most useful
least known Lisp function. It doesn't win on any single
factor, but on the combination.
···@agharta.de (Dr. Edmund Weitz) writes:
...
> What I actually wanted to have was a function that - for want of
> better words - I called SUBDIVIDE. It was intended to accept a list
> and return a list of lists of length INCR such that the concatenation
> of these lists would result in the original list, i.e.
>
> (subdivide '(1 2 3 4 5 6) :incr 2) => ((1 2) (3 4) (5 6))
>
> My first attempt was this function:
>
> (defun subdivide (list &key (incr 1))
> (let ((counter 0))
> (labels ((get-subseq-or-nil (seq)
> (prog1
> (if (= 0 (mod counter incr))
> (subseq seq 0 (min incr (length seq)))
> nil)
> (incf counter))))
> (delete nil
> (maplist #'get-subseq-or-nil list)))))
If we had MAPSEQ (equivalent of MAPLIST), the function could become
general purpose.
(defun subdivide (seq &key (incr 1))
(declare (type sequence seq))
(let ((counter 0))
(labels ((get-subseq-or-nil (s)
(prog1
(if (= 0 (mod counter incr))
(subseq s 0 (min incr (length s)))
nil)
(incf counter))))
(delete nil
(mapseq #'get-subseq-or-nil list)))))
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th 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'.
Is it ok to be destructive? This will divide the list in place.
It's a little ugly, but it keeps the cons to a minimum (and I got
to play with recursion).
(defun subdivide (list increment)
(if (null list)
nil
(let* ((thisend (nthcdr (1- increment) list))
(rest (cdr thisend)))
(prog1 (cons list (subdivide rest increment))
(when thisend (setf (cdr thisend) nil))))))
Note: I've only been learning Lisp a couple of weeks myself.
Ed Symanzik <···@msu.edu> writes:
> Is it ok to be destructive? This will divide the list in place.
> It's a little ugly, but it keeps the cons to a minimum (and I got
> to play with recursion).
>
> (defun subdivide (list increment)
> (if (null list)
> nil
> (let* ((thisend (nthcdr (1- increment) list))
> (rest (cdr thisend)))
> (prog1 (cons list (subdivide rest increment))
> (when thisend (setf (cdr thisend) nil))))))
Usually one would name the function in some way that hinted at its
destructive nature. Some would use a prefix "n" (for reasons lost
in history), as in "nsubdivide". Others would do as Scheme does,
and as I kinda like for most situations (other than their use of
"set!", which I regard as confused because I don't think "setq" is
"destructive"), and call it "subdivide!". Another option would be
to add "-destructively" to the name [although if you learn to
pronounce "!" as "destructively" (and "?" as "pee"), you get some nicer
names and still have audio compatibility with more Lispy spellings].
> Note: I've only been learning Lisp a couple of weeks myself.
Cool. Glad to know we have another counterexample to the frequent claims
by outsiders that Lisp takes a long time to learn.
- - - - -
Since you are new, here are some xextra style tips:
Your indentation could use work. open parens for bindings should align.
body of a binder like LET should go only two spaces in, not all the way
out to the level where the bindings are:
(defun subdivide (list increment)
(if (null list)
'()
(let* ((thisend (nthcdr (1- increment) list))
(rest (cdr thisend)))
(prog1 (cons list (subdivide rest increment))
(when thisend (setf (cdr thisend) nil))))))
And as a point of style, by the way, you should use '() instead of NIL
[as I've done in my re-indented version above]
even though they evaluate to the selfsame object when you are giving the
sense that you mean NIL qua empty list instead of NIL qua boolean.
I also use 'NIL rather than NIL when referring to NIL qua symbol.
All three of 'NIL, NIL, and '() evaluate to the same object and have
the same operational effect in an ordinary for-evaluation position in code;
it's just a matter of cueing the human reader to the right style.
Further, I don't see any practical problem in just doing the side-effects
in the normal order instead of using PROG1 to force the side-effect to
happen after. In some sense, it makes me cringe to think you're going
to cons the wrong list in and then bash it after-the-fact; I'd rather first
do the surgery and then cons it in, even though it makes not a hill of beans
of difference... except it will look in the debugger like it's doing the
wrong thing if you get a breakpoint before the recursive calls to SUBDIVIDE
run to completion...
There's also an issue about whether cdr-side recursion is a good idea.
Lists can be arbitrarily long and you can run out of stack depth. My
practical solution to this is to say to recurse into cars and iterate
on cdrs where you can, since we don't have tail call elimination here.
Nothing technically wrong with what you did, but your code will be
more robust if you iterate with a looping primitive where you can
(LOOP and DO are your major candidates here).