Hi,
I would like to submit a recipe to the lisp cookbook (http://cl-
cookbook.sourceforge.net/). So before poisoning the unsuspected, I
thought that the expert tasters could inspect this for obvious
errors.
The routine parses a sorted list and returns a list of duplicates.
Thus, for the following list
(-1 0 0 1 1 2 3 3 3 4 5 8 9 9 10 11 11)
the routine returns
((0 0) (1 1) (3 3 3) (9 9) (11 11)
What follows is a simplified version:
(defun collect-repeats-simple (sorted-list)
(loop
with repeats = nil
and acc = nil
for a in sorted-list
for b in (cdr sorted-list)
when (and (not repeats)
(equal a b))
do (progn
(setf acc (list a b))
(setf repeats t))
else
when repeats
when (equal a b)
do (push b acc)
else
collect acc into result and
do (progn
(setf acc nil)
(setf repeats nil))
finally (print (if acc (append result (list acc))
result))))
A more complete version would allow for the key and test keywords. My
version of the defun is:
(defun collect-repeats (sorted-list &key (key #'(lambda (arg) arg))
(test #'equal))
(Is there a more concise way to specify the default key?)
Thanks,
Mirko
·············@gmail.com writes:
> Hi,
>
> I would like to submit a recipe to the lisp cookbook (http://cl-
> cookbook.sourceforge.net/). So before poisoning the unsuspected, I
> thought that the expert tasters could inspect this for obvious
> errors.
>
> The routine parses a sorted list and returns a list of duplicates.
> Thus, for the following list
> (-1 0 0 1 1 2 3 3 3 4 5 8 9 9 10 11 11)
> the routine returns
> ((0 0) (1 1) (3 3 3) (9 9) (11 11)
>
> What follows is a simplified version:
>
> (defun collect-repeats-simple (sorted-list)
> (loop
> with repeats = nil
> and acc = nil
> for a in sorted-list
> for b in (cdr sorted-list)
>
> when (and (not repeats)
> (equal a b))
> do (progn
> (setf acc (list a b))
> (setf repeats t))
>
> else
> when repeats
> when (equal a b)
> do (push b acc)
> else
> collect acc into result and
> do (progn
> (setf acc nil)
> (setf repeats nil))
>
> finally (print (if acc (append result (list acc))
> result))))
>
>
> A more complete version would allow for the key and test keywords. My
> version of the defun is:
> (defun collect-repeats (sorted-list &key (key #'(lambda (arg) arg))
> (test #'equal))
> (Is there a more concise way to specify the default key?)
(lambda (arg) arg) is identity is Common Lisp.
However, I don't understand why everybody here seems to be so obsessed
with loop solutions full of non-functional setf's that have so many
lines that they don't fit on my screen while elegant recursive
solutions exist? Is it because Paul Graham's "ANSI Common Lisp" was my
first book that I don't like loops and do like recursion?
(defun collect-repeats-simple (sorted-list &optional (acc nil))
(cond
((null sorted-list)
(remove-if (lambda (l)
(null (cdr l))) (reverse acc)))
((equal (car sorted-list)
(caar acc))
(push (car sorted-list) (car acc))
(collect-repeats-simple (cdr sorted-list) acc))
(t (collect-repeats-simple (cdr sorted-list)
(cons (list (car sorted-list)) acc)))))
Regards,
Victor.
--
http://macrodefinition.blogspot.com
Victor Kryukov wrote:
> However, I don't understand why everybody here seems to be so obsessed
> with loop solutions full of non-functional setf's that have so many
> lines that they don't fit on my screen while elegant recursive
> solutions exist?
Maybe it is because the Common Lisp spec doesn't require tail call
elimination?
Brian <··············@gmail.com> writes:
> Victor Kryukov wrote:
>> However, I don't understand why everybody here seems to be so obsessed
>> with loop solutions full of non-functional setf's that have so many
>> lines that they don't fit on my screen while elegant recursive
>> solutions exist?
> Maybe it is because the Common Lisp spec doesn't require tail call
> elimination?
Try (declare (optimize 3)) - that will work for SBCL, CMUCL and
commercial lisps, at least.
--
http://macrodefinition.blogspot.com
P� Mon, 24 Mar 2008 05:09:59 +0100, skrev Victor Kryukov
<··············@gmail.com>:
> Brian <··············@gmail.com> writes:
>
>> Victor Kryukov wrote:
>>> However, I don't understand why everybody here seems to be so obsessed
>>> with loop solutions full of non-functional setf's that have so many
>>> lines that they don't fit on my screen while elegant recursive
>>> solutions exist?
>> Maybe it is because the Common Lisp spec doesn't require tail call
>> elimination?
>
> Try (declare (optimize 3)) - that will work for SBCL, CMUCL and
> commercial lisps, at least.
More specifically you will usually tail recurse if speed > safety.
In LispWorks tail recursion elimination is not done if debug is 3.
The problem with tail recursion elimination is that not all compilers can
optimize the same things.
This is a bigger problem than that it is not in the standard.
--------------
John Thingstad
??>>> However, I don't understand why everybody here seems to be so
??>>> obsessed with loop solutions full of non-functional setf's that have
??>>> so many lines that they don't fit on my screen while elegant
??>>> recursive solutions exist?
??>> Maybe it is because the Common Lisp spec doesn't require tail call
??>> elimination?
VK> Try (declare (optimize 3)) - that will work for SBCL, CMUCL and
VK> commercial lisps, at least.
you mean to run this code one needs to find implementation that supports it
and configure compiler switches appropriately? niiice.
it's not a theoretical problems -- i actually had problems using recursive
code with CLISP. so for now i prefer more robust solutions.
"Alex Mizrahi" <········@users.sourceforge.net> writes:
> ??>>> However, I don't understand why everybody here seems to be so
> ??>>> obsessed with loop solutions full of non-functional setf's that have
> ??>>> so many lines that they don't fit on my screen while elegant
> ??>>> recursive solutions exist?
> ??>> Maybe it is because the Common Lisp spec doesn't require tail call
> ??>> elimination?
>
> VK> Try (declare (optimize 3)) - that will work for SBCL, CMUCL and
> VK> commercial lisps, at least.
>
> you mean to run this code one needs to find implementation that supports it
> and configure compiler switches appropriately? niiice.
I see what you're saying and agree that a 'universal' solutions could
be better in some cases, but I think you're exaggerating the problem a
little bit. Usually every programmer knows his 'regular'
implementation fairly well and can easily configure optimization
declarations. They are often necessary in production code that needs
to be efficient anyway - check CL-PPCRE library for an example - and
libraries could adapt for different compilers with #+ reader macro.
I prefer recursion solutions over explicit loops for the same reasons
I prefer to code in Lisp and not C. That way I can stay at higher
level of abstraction, and in most cases good compiler can generate
effecient code for me.
Regards,
Victor.
--
http://macrodefinition.blogspot.com
VK> I prefer recursion solutions over explicit loops for the same reasons
VK> I prefer to code in Lisp and not C. That way I can stay at higher
VK> level of abstraction, and in most cases good compiler can generate
VK> effecient code for me.
if you really prefer recursion, you might find Haskell (or at least Scheme)
better suiting your needs.
"Alex Mizrahi" <········@users.sourceforge.net> writes:
> VK> I prefer recursion solutions over explicit loops for the same reasons
> VK> I prefer to code in Lisp and not C. That way I can stay at higher
> VK> level of abstraction, and in most cases good compiler can generate
> VK> effecient code for me.
>
> if you really prefer recursion, you might find Haskell (or at least Scheme)
> better suiting your needs.
I do like recursion, but I'm not a dogmatist. I prefer Common Lisp to
Scheme in the production environment. I know next to nothing about
Haskell, but I have yet to see a Haskell-based web startup.
--
http://macrodefinition.blogspot.com
On Mar 24, 1:30 pm, "Alex Mizrahi" <········@users.sourceforge.net>
wrote:
> VK> I prefer recursion solutions over explicit loops for the same reasons
> VK> I prefer to code in Lisp and not C. That way I can stay at higher
> VK> level of abstraction, and in most cases good compiler can generate
> VK> effecient code for me.
>
> if you really prefer recursion, you might find Haskell (or at least Scheme)
> better suiting your needs.
Quite correct. COBOL and its descendant COBOL-LISP (CL) are very
business-oriented. What has a bookkeeper to do with elegance?
On Mar 23, 7:39 pm, Victor Kryukov <··············@gmail.com> wrote:
> I don't understand why everybody here seems to be
> so obsessed with loop solutions full of non-functional
> setf's that have so many lines that they don't fit on
> my screen while elegant recursive solutions exist?
Or less clunky iterative solutions. Shamelessly stealing
your post-accumulation non-duplicate removal,
(defun collect-dupes (sorted-list &key (test #'equal)
(key #'identity))
(let ((clumps '()))
(dolist (x sorted-list)
(if (funcall test (funcall key x)
(funcall key (caar clumps)))
(push x (car clumps))
(push (list x) clumps)))
(nreverse (delete-if-not #'cdr clumps))))
--Dan
------------------------------------------------
Dan Bensen
http://www.prairienet.org/~dsb/
·············@gmail.com wrote:
> Hi,
>
> I would like to submit a recipe to the lisp cookbook (http://cl-
> cookbook.sourceforge.net/). So before poisoning the unsuspected, I
> thought that the expert tasters could inspect this for obvious
> errors.
>
> The routine parses a sorted list and returns a list of duplicates.
> Thus, for the following list
> (-1 0 0 1 1 2 3 3 3 4 5 8 9 9 10 11 11)
> the routine returns
> ((0 0) (1 1) (3 3 3) (9 9) (11 11)
>
> What follows is a simplified version:
>
> (defun collect-repeats-simple (sorted-list)
I am expecting ... &key test test-not key start end).
[Oops. You got to that eventually]
> (loop
> with repeats = nil
> and acc = nil
A casual scan of what you did suggests acc could serve as "repeats".
And no need to say "acc = nil" just say acc.
> for a in sorted-list
> for b in (cdr sorted-list)
>
> when (and (not repeats)
> (equal a b))
> do (progn
One of the charms of loop is the implicit progn-ing it provides.
> (setf acc (list a b))
> (setf repeats t))
>
> else
"when...else"? I am not sure what is more horrifying, that it is
legal and works as if it were if or that you used it. :)
> when repeats
> when (equal a b)
EQL seems to be the CL default in these matters.
> do (push b acc)
Looks like you might be a little clearer with:
if (funcall test a b) ;; one suggestion
if acc collect b into acc ;; another suggestion (no repeats var)
else collect a into acc
and collect b into acc
Your push of the third after starting by collecting the first in second
in order means you are reordering, which will matter if you are not just
processing numbers or chars.
Seems to me a "stable" segmentation would be desirable.
> else
> collect acc into result and
> do (progn
> (setf acc nil)
> (setf repeats nil))
>
> finally (print (if acc (append result (list acc))
No need to append, we "own" the result structure. Use nconc.
> result))))
>
>
> A more complete version would allow for the key and test keywords. My
> version of the defun is:
> (defun collect-repeats (sorted-list &key (key #'(lambda (arg) arg))
> (test #'equal))
> (Is there a more concise way to specify the default key?)
'identity
So far I have (untested):
(defun collect-repeats-simple (sorted-list &key (test 'eql))
(loop with acc
for a in sorted-list
for b in (cdr sorted-list)
if (funcall test (funcall key a) (funcall key b))
if acc collect b into acc
else collect a into acc
and collect b into acc
else
collect acc into result
and (setf acc nil)
finally (nconc result (when acc (list acc)))))
hth,kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
Ken Tilton wrote:
> So far I have (untested):
>
> (defun collect-repeats-simple (sorted-list &key (test 'eql))
> (loop with acc
> for a in sorted-list
> for b in (cdr sorted-list)
>
> if (funcall test (funcall key a) (funcall key b))
> if acc collect b into acc
> else collect a into acc
> and collect b into acc
>
> else
> collect acc into result
> and (setf acc nil)
> finally (nconc result (when acc (list acc)))))
Haha, ignore that!
kt
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Mar 23, 11:03 pm, Ken Tilton <···········@optonline.net> wrote:
> ·············@gmail.com wrote:
> > Hi,
>
> > I would like to submit a recipe to the lisp cookbook (http://cl-
> > cookbook.sourceforge.net/). So before poisoning the unsuspected, I
> > thought that the experttasterscould inspect this for obvious
> > errors.
>
> > The routine parses a sorted list and returns a list of duplicates.
> > Thus, for the following list
> > (-1 0 0 1 1 2 3 3 3 4 5 8 9 9 10 11 11)
> > the routine returns
> > ((0 0) (1 1) (3 3 3) (9 9) (11 11)
>
> > What follows is a simplified version:
>
> > (defun collect-repeats-simple (sorted-list)
>
> I am expecting ... &key test test-not key start end).
>
> [Oops. You got to that eventually]
>
> > (loop
> > with repeats = nil
> > and acc = nil
>
> A casual scan of what you did suggests acc could serve as "repeats".
>
> And no need to say "acc = nil" just say acc.
>
> > for a in sorted-list
> > for b in (cdr sorted-list)
>
> > when (and (not repeats)
> > (equal a b))
> > do (progn
>
> One of the charms of loop is the implicit progn-ing it provides.
>
> > (setf acc (list a b))
> > (setf repeats t))
>
> > else
>
> "when...else"? I am not sure what is more horrifying, that it is
> legal and works as if it were if or that you used it. :)
>
> > when repeats
> > when (equal a b)
>
> EQL seems to be the CL default in these matters.
>
> > do (push b acc)
>
> Looks like you might be a little clearer with:
>
> if (funcall test a b) ;; one suggestion
> if acc collect b into acc ;; another suggestion (no repeats var)
> else collect a into acc
> and collect b into acc
>
> Your push of the third after starting by collecting the first in second
> in order means you are reordering, which will matter if you are not just
> processing numbers or chars.
>
> Seems to me a "stable" segmentation would be desirable.
>
> > else
> > collect acc into result and
> > do (progn
> > (setf acc nil)
> > (setf repeats nil))
>
> > finally (print (if acc (append result (list acc))
>
> No need to append, we "own" the result structure. Use nconc.
>
> > result))))
>
> > A more complete version would allow for the key and test keywords. My
> > version of the defun is:
> > (defun collect-repeats (sorted-list &key (key #'(lambda (arg) arg))
> > (test #'equal))
> > (Is there a more concise way to specify the default key?)
>
> 'identity
>
> So far I have (untested):
>
> (defun collect-repeats-simple (sorted-list &key (test 'eql))
> (loop with acc
> for a in sorted-list
> for b in (cdr sorted-list)
>
> if (funcall test (funcall key a) (funcall key b))
> if acc collect b into acc
> else collect a into acc
> and collect b into acc
>
> else
> collect acc into result
> and (setf acc nil)
> finally (nconc result (when acc (list acc)))))
>
> hth,kenny
>
> --http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>
> "In the morning, hear the Way;
> in the evening, die content!"
> -- Confucius
Um, it does work, but for the life of me, I don't understand why.
Here it is in action at repl:
MY-UTILS> (let* ((tail (list 'b))
(acc (list* 'a tail)))
(print tail)
(print acc)
(setf tail (cdr (rplacd tail (list 'c))))
(print tail)
(print acc)
(setf tail (cdr (rplacd tail (list 'd))))
(print tail)
acc)
(B) ;; understand
(A B) ;; understand
(C) ;; I thought I understood
(A B C) ;; I would have expected (A C)
(D) ;; OK,
(A B C D) ;; again, I would have expected (A D)
MY-UTILS> (thank-you)
·············@gmail.com wrote:
> On Mar 23, 11:03 pm, Ken Tilton <···········@optonline.net> wrote:
>
>>·············@gmail.com wrote:
>>
>>>Hi,
>>
>>>I would like to submit a recipe to the lisp cookbook (http://cl-
>>>cookbook.sourceforge.net/). So before poisoning the unsuspected, I
>>>thought that the experttasterscould inspect this for obvious
>>>errors.
>>
>>>The routine parses a sorted list and returns a list of duplicates.
>>>Thus, for the following list
>>>(-1 0 0 1 1 2 3 3 3 4 5 8 9 9 10 11 11)
>>>the routine returns
>>>((0 0) (1 1) (3 3 3) (9 9) (11 11)
>>
>>>What follows is a simplified version:
>>
>>>(defun collect-repeats-simple (sorted-list)
>>
>>I am expecting ... &key test test-not key start end).
>>
>>[Oops. You got to that eventually]
>>
>>
>>> (loop
>>> with repeats = nil
>>> and acc = nil
>>
>>A casual scan of what you did suggests acc could serve as "repeats".
>>
>>And no need to say "acc = nil" just say acc.
>>
>>
>>> for a in sorted-list
>>> for b in (cdr sorted-list)
>>
>>> when (and (not repeats)
>>> (equal a b))
>>> do (progn
>>
>>One of the charms of loop is the implicit progn-ing it provides.
>>
>>
>>> (setf acc (list a b))
>>> (setf repeats t))
>>
>>> else
>>
>> "when...else"? I am not sure what is more horrifying, that it is
>>legal and works as if it were if or that you used it. :)
>>
>>
>>> when repeats
>>> when (equal a b)
>>
>>EQL seems to be the CL default in these matters.
>>
>>
>>> do (push b acc)
>>
>>Looks like you might be a little clearer with:
>>
>> if (funcall test a b) ;; one suggestion
>> if acc collect b into acc ;; another suggestion (no repeats var)
>> else collect a into acc
>> and collect b into acc
>>
>>Your push of the third after starting by collecting the first in second
>>in order means you are reordering, which will matter if you are not just
>>processing numbers or chars.
>>
>>Seems to me a "stable" segmentation would be desirable.
>>
>>
>>> else
>>> collect acc into result and
>>> do (progn
>>> (setf acc nil)
>>> (setf repeats nil))
>>
>>> finally (print (if acc (append result (list acc))
>>
>>No need to append, we "own" the result structure. Use nconc.
>>
>>
>>> result))))
>>
>>>A more complete version would allow for the key and test keywords. My
>>>version of the defun is:
>>>(defun collect-repeats (sorted-list &key (key #'(lambda (arg) arg))
>>> (test #'equal))
>>>(Is there a more concise way to specify the default key?)
>>
>>'identity
>>
>>So far I have (untested):
>>
>>(defun collect-repeats-simple (sorted-list &key (test 'eql))
>> (loop with acc
>> for a in sorted-list
>> for b in (cdr sorted-list)
>>
>> if (funcall test (funcall key a) (funcall key b))
>> if acc collect b into acc
>> else collect a into acc
>> and collect b into acc
>>
>> else
>> collect acc into result
>> and (setf acc nil)
>> finally (nconc result (when acc (list acc)))))
>>
>>hth,kenny
>>
>>--http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>>
>>"In the morning, hear the Way;
>> in the evening, die content!"
>> -- Confucius
>
>
>
>
> Um, it does work, but for the life of me, I don't understand why.
> Here it is in action at repl:
>
> MY-UTILS> (let* ((tail (list 'b))
> (acc (list* 'a tail)))
> (print tail)
> (print acc)
> (setf tail (cdr (rplacd tail (list 'c))))
> (print tail)
> (print acc)
> (setf tail (cdr (rplacd tail (list 'd))))
> (print tail)
> acc)
>
> (B) ;; understand
> (A B) ;; understand
> (C) ;; I thought I understood
(a) I hope you realize tho that this is what you want: you want tail to
hold the last cons cell so you can quickly extend the list without
traversing it to find the last cons, as would happen with NCONC, eg.
(b) you understood that tail began as (b), or (b . nil) to show off the
car and cdr explicitly. Then:
(list 'c)
-> (c . nil)
rplacd places that in the cdr of (b . nil)
-> (b . (c . nil)) aka (b c)
btw, recall I screwed this up in the first go, assuming rplacd like setf
would return the value it was storing. nope, it returns the cons whose
cdr is being replaced.
cdr (in (cdr (rplacd taik (list 'c)))) goes and gets the new tail
-> (c . nil)
setf then rebinds tail to the new tail, exactly what we want.
> (A B C) ;; I would have expected (A C)
OK, I see. You just need to look up RPLACD. It is the same as (setf
cdr), so you could do (setf (cdr tail) (list 'c)). But look at all those
parnetheses! Hmmhh, but then I do not need the CDR!
(setf tail (setf (cdr tail) (list 'c)))
(let ((acc (list 0)))
(loop with tail = acc
for n upfrom 1 to 5
do (setf tail (setf (cdr tail) (list n)))
finally (print acc)))
-> (0 1 2 3 4 5)
Cool. But I like rplacd.
> (D) ;; OK,
Wait, because it is the same as the (C) you did not understand? I think
that is what you meant based on the next:
> (A B C D) ;; again, I would have expected (A D)
> MY-UTILS> (thank-you)
At times like these one has to forget the crazy idea that Lisp processes
lists and understand that it really only understands the cons cell,
something that simply has two slots called car and cdr.
Can you tell what this returns without trying it?:
(rplacd (loop for n below 1000 collecting n) 'migod!)
kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Mar 29, 4:24 pm, Ken Tilton <···········@optonline.net> wrote:
> ·············@gmail.com wrote:
> > On Mar 23, 11:03 pm, Ken Tilton <···········@optonline.net> wrote:
>
> >>·············@gmail.com wrote:
>
> >>>Hi,
>
> >>>I would like to submit a recipe to the lisp cookbook (http://cl-
> >>>cookbook.sourceforge.net/). So before poisoning the unsuspected, I
> >>>thought that the experttasterscould inspect this for obvious
> >>>errors.
>
> >>>The routine parses a sorted list and returns a list of duplicates.
> >>>Thus, for the following list
> >>>(-1 0 0 1 1 2 3 3 3 4 5 8 9 9 10 11 11)
> >>>the routine returns
> >>>((0 0) (1 1) (3 3 3) (9 9) (11 11)
>
> >>>What follows is a simplified version:
>
> >>>(defun collect-repeats-simple (sorted-list)
>
> >>I am expecting ... &key test test-not key start end).
>
> >>[Oops. You got to that eventually]
>
> >>> (loop
> >>> with repeats = nil
> >>> and acc = nil
>
> >>A casual scan of what you did suggests acc could serve as "repeats".
>
> >>And no need to say "acc = nil" just say acc.
>
> >>> for a in sorted-list
> >>> for b in (cdr sorted-list)
>
> >>> when (and (not repeats)
> >>> (equal a b))
> >>> do (progn
>
> >>One of the charms of loop is the implicit progn-ing it provides.
>
> >>> (setf acc (list a b))
> >>> (setf repeats t))
>
> >>> else
>
> >> "when...else"? I am not sure what is more horrifying, that it is
> >>legal and works as if it were if or that you used it. :)
>
> >>> when repeats
> >>> when (equal a b)
>
> >>EQL seems to be the CL default in these matters.
>
> >>> do (push b acc)
>
> >>Looks like you might be a little clearer with:
>
> >> if (funcall test a b) ;; one suggestion
> >> if acc collect b into acc ;; another suggestion (no repeats var)
> >> else collect a into acc
> >> and collect b into acc
>
> >>Your push of the third after starting by collecting the first in second
> >>in order means you are reordering, which will matter if you are not just
> >>processing numbers or chars.
>
> >>Seems to me a "stable" segmentation would be desirable.
>
> >>> else
> >>> collect acc into result and
> >>> do (progn
> >>> (setf acc nil)
> >>> (setf repeats nil))
>
> >>> finally (print (if acc (append result (list acc))
>
> >>No need to append, we "own" the result structure. Use nconc.
>
> >>> result))))
>
> >>>A more complete version would allow for the key and test keywords. My
> >>>version of the defun is:
> >>>(defun collect-repeats (sorted-list &key (key #'(lambda (arg) arg))
> >>> (test #'equal))
> >>>(Is there a more concise way to specify the default key?)
>
> >>'identity
>
> >>So far I have (untested):
>
> >>(defun collect-repeats-simple (sorted-list &key (test 'eql))
> >> (loop with acc
> >> for a in sorted-list
> >> for b in (cdr sorted-list)
>
> >> if (funcall test (funcall key a) (funcall key b))
> >> if acc collect b into acc
> >> else collect a into acc
> >> and collect b into acc
>
> >> else
> >> collect acc into result
> >> and (setf acc nil)
> >> finally (nconc result (when acc (list acc)))))
>
> >>hth,kenny
>
> >>--http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>
> >>"In the morning, hear the Way;
> >> in the evening, die content!"
> >> -- Confucius
>
> > Um, it does work, but for the life of me, I don't understand why.
> > Here it is in action at repl:
>
> > MY-UTILS> (let* ((tail (list 'b))
> > (acc (list* 'a tail)))
> > (print tail)
> > (print acc)
> > (setf tail (cdr (rplacd tail (list 'c))))
> > (print tail)
> > (print acc)
> > (setf tail (cdr (rplacd tail (list 'd))))
> > (print tail)
> > acc)
>
> > (B) ;; understand
> > (A B) ;; understand
> > (C) ;; I thought I understood
>
> (a) I hope you realize tho that this is what you want: you want tail to
> hold the last cons cell so you can quickly extend the list without
> traversing it to find the last cons, as would happen with NCONC, eg.
>
> (b) you understood that tail began as (b), or (b . nil) to show off the
> car and cdr explicitly. Then:
>
> (list 'c)
> -> (c . nil)
>
> rplacd places that in the cdr of (b . nil)
> -> (b . (c . nil)) aka (b c)
>
> btw, recall I screwed this up in the first go, assuming rplacd like setf
> would return the value it was storing. nope, it returns the cons whose
> cdr is being replaced.
>
> cdr (in (cdr (rplacd taik (list 'c)))) goes and gets the new tail
> -> (c . nil)
>
> setf then rebinds tail to the new tail, exactly what we want.
>
> > (A B C) ;; I would have expected (A C)
>
> OK, I see. You just need to look up RPLACD. It is the same as (setf
> cdr), so you could do (setf (cdr tail) (list 'c)). But look at all those
> parnetheses! Hmmhh, but then I do not need the CDR!
>
> (setf tail (setf (cdr tail) (list 'c)))
>
> (let ((acc (list 0)))
> (loop with tail = acc
> for n upfrom 1 to 5
> do (setf tail (setf (cdr tail) (list n)))
> finally (print acc)))
> -> (0 1 2 3 4 5)
>
> Cool. But I like rplacd.
>
> > (D) ;; OK,
>
> Wait, because it is the same as the (C) you did not understand? I think
> that is what you meant based on the next:
>
> > (A B C D) ;; again, I would have expected (A D)
> > MY-UTILS> (thank-you)
>
> At times like these one has to forget the crazy idea that Lisp processes
> lists and understand that it really only understands the cons cell,
> something that simply has two slots called car and cdr.
>
> Can you tell what this returns without trying it?:
>
> (rplacd (loop for n below 1000 collecting n) 'migod!)
>
> kenny
>
> --http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>
> "In the morning, hear the Way;
> in the evening, die content!"
> -- Confucius
I did not study the rest of your post. But regarding the last
question, I would say, (1 'migod'). Now I will go to and try it
out :-)
(Till later, I have lisp on another machine)
Mirko
On Mar 29, 4:36 pm, ·············@gmail.com wrote:
> On Mar 29, 4:24 pm, Ken Tilton <···········@optonline.net> wrote:
>
>
>
> > ·············@gmail.com wrote:
> > > On Mar 23, 11:03 pm, Ken Tilton <···········@optonline.net> wrote:
>
> > >>·············@gmail.com wrote:
>
> > >>>Hi,
>
> > >>>I would like to submit a recipe to the lisp cookbook (http://cl-
> > >>>cookbook.sourceforge.net/). So before poisoning the unsuspected, I
> > >>>thought that the experttasterscould inspect this for obvious
> > >>>errors.
>
> > >>>The routine parses a sorted list and returns a list of duplicates.
> > >>>Thus, for the following list
> > >>>(-1 0 0 1 1 2 3 3 3 4 5 8 9 9 10 11 11)
> > >>>the routine returns
> > >>>((0 0) (1 1) (3 3 3) (9 9) (11 11)
>
> > >>>What follows is a simplified version:
>
> > >>>(defun collect-repeats-simple (sorted-list)
>
> > >>I am expecting ... &key test test-not key start end).
>
> > >>[Oops. You got to that eventually]
>
> > >>> (loop
> > >>> with repeats = nil
> > >>> and acc = nil
>
> > >>A casual scan of what you did suggests acc could serve as "repeats".
>
> > >>And no need to say "acc = nil" just say acc.
>
> > >>> for a in sorted-list
> > >>> for b in (cdr sorted-list)
>
> > >>> when (and (not repeats)
> > >>> (equal a b))
> > >>> do (progn
>
> > >>One of the charms of loop is the implicit progn-ing it provides.
>
> > >>> (setf acc (list a b))
> > >>> (setf repeats t))
>
> > >>> else
>
> > >> "when...else"? I am not sure what is more horrifying, that it is
> > >>legal and works as if it were if or that you used it. :)
>
> > >>> when repeats
> > >>> when (equal a b)
>
> > >>EQL seems to be the CL default in these matters.
>
> > >>> do (push b acc)
>
> > >>Looks like you might be a little clearer with:
>
> > >> if (funcall test a b) ;; one suggestion
> > >> if acc collect b into acc ;; another suggestion (no repeats var)
> > >> else collect a into acc
> > >> and collect b into acc
>
> > >>Your push of the third after starting by collecting the first in second
> > >>in order means you are reordering, which will matter if you are not just
> > >>processing numbers or chars.
>
> > >>Seems to me a "stable" segmentation would be desirable.
>
> > >>> else
> > >>> collect acc into result and
> > >>> do (progn
> > >>> (setf acc nil)
> > >>> (setf repeats nil))
>
> > >>> finally (print (if acc (append result (list acc))
>
> > >>No need to append, we "own" the result structure. Use nconc.
>
> > >>> result))))
>
> > >>>A more complete version would allow for the key and test keywords. My
> > >>>version of the defun is:
> > >>>(defun collect-repeats (sorted-list &key (key #'(lambda (arg) arg))
> > >>> (test #'equal))
> > >>>(Is there a more concise way to specify the default key?)
>
> > >>'identity
>
> > >>So far I have (untested):
>
> > >>(defun collect-repeats-simple (sorted-list &key (test 'eql))
> > >> (loop with acc
> > >> for a in sorted-list
> > >> for b in (cdr sorted-list)
>
> > >> if (funcall test (funcall key a) (funcall key b))
> > >> if acc collect b into acc
> > >> else collect a into acc
> > >> and collect b into acc
>
> > >> else
> > >> collect acc into result
> > >> and (setf acc nil)
> > >> finally (nconc result (when acc (list acc)))))
>
> > >>hth,kenny
>
> > >>--http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>
> > >>"In the morning, hear the Way;
> > >> in the evening, die content!"
> > >> -- Confucius
>
> > > Um, it does work, but for the life of me, I don't understand why.
> > > Here it is in action at repl:
>
> > > MY-UTILS> (let* ((tail (list 'b))
> > > (acc (list* 'a tail)))
> > > (print tail)
> > > (print acc)
> > > (setf tail (cdr (rplacd tail (list 'c))))
> > > (print tail)
> > > (print acc)
> > > (setf tail (cdr (rplacd tail (list 'd))))
> > > (print tail)
> > > acc)
>
> > > (B) ;; understand
> > > (A B) ;; understand
> > > (C) ;; I thought I understood
>
> > (a) I hope you realize tho that this is what you want: you want tail to
> > hold the last cons cell so you can quickly extend the list without
> > traversing it to find the last cons, as would happen with NCONC, eg.
>
> > (b) you understood that tail began as (b), or (b . nil) to show off the
> > car and cdr explicitly. Then:
>
> > (list 'c)
> > -> (c . nil)
>
> > rplacd places that in the cdr of (b . nil)
> > -> (b . (c . nil)) aka (b c)
>
> > btw, recall I screwed this up in the first go, assuming rplacd like setf
> > would return the value it was storing. nope, it returns the cons whose
> > cdr is being replaced.
>
> > cdr (in (cdr (rplacd taik (list 'c)))) goes and gets the new tail
> > -> (c . nil)
>
> > setf then rebinds tail to the new tail, exactly what we want.
>
> > > (A B C) ;; I would have expected (A C)
>
> > OK, I see. You just need to look up RPLACD. It is the same as (setf
> > cdr), so you could do (setf (cdr tail) (list 'c)). But look at all those
> > parnetheses! Hmmhh, but then I do not need the CDR!
>
> > (setf tail (setf (cdr tail) (list 'c)))
>
> > (let ((acc (list 0)))
> > (loop with tail = acc
> > for n upfrom 1 to 5
> > do (setf tail (setf (cdr tail) (list n)))
> > finally (print acc)))
> > -> (0 1 2 3 4 5)
>
> > Cool. But I like rplacd.
>
> > > (D) ;; OK,
>
> > Wait, because it is the same as the (C) you did not understand? I think
> > that is what you meant based on the next:
>
> > > (A B C D) ;; again, I would have expected (A D)
> > > MY-UTILS> (thank-you)
>
> > At times like these one has to forget the crazy idea that Lisp processes
> > lists and understand that it really only understands the cons cell,
> > something that simply has two slots called car and cdr.
>
> > Can you tell what this returns without trying it?:
>
> > (rplacd (loop for n below 1000 collecting n) 'migod!)
>
> > kenny
>
> > --http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>
> > "In the morning, hear the Way;
> > in the evening, die content!"
> > -- Confucius
>
> I did not study the rest of your post. But regarding the last
> question, I would say, (1 'migod'). Now I will go to and try it
> out :-)
>
> (Till later, I have lisp on another machine)
>
> Mirko
OK, I just tried it, and sure enough, I was wrong (on two counts):
clisp gave me (0 . 'migod!) -- well at least I will remember from now
on that loop for n starts from 0 (as evidently all of lisp's indexing
and counting).
I'll single-step through your exposition to understand it better.
Mirko
>>>Can you tell what this returns without trying it?:
>>
>>> (rplacd (loop for n below 1000 collecting n) 'migod!)
>>
>>>kenny
>>
>>>--http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>>
>>>"In the morning, hear the Way;
>>> in the evening, die content!"
>>> -- Confucius
>>
>>I did not study the rest of your post. But regarding the last
>>question, I would say, (1 'migod'). Now I will go to and try it
>>out :-)
>>
>>(Till later, I have lisp on another machine)
>>
>>Mirko
>
>
> OK, I just tried it, and sure enough, I was wrong (on two counts):
> clisp gave me (0 . 'migod!) -- well at least I will remember from now
> on that loop for n starts from 0 (as evidently all of lisp's indexing
> and counting).
>
> I'll single-step through your exposition to understand it better.
Well it was a slightly tricky question because everywhere else we were
talking about building a proper list by adding directly to its tail, and
we were doing that with (rplacd tail (list 'migod)) and I changed things
up on you with (rplacd <list> 'migod).
But I wanted to get away from list-think and get to cons-think, ie the
cons data structure and its two slots, car and cdr. Here is another
exercise. You want to gues at *c* all along the way:
(defvar *c*)
(setf *c* (cons 0 nil))
(setf *c* (cons nil nil))
(setf (car *c*) 1)
(setf (cdr *c*) 2)
Now we'll use "list", but remember:
(list 1 2) is just (cons 1 (cons 2 nil))
...and so the above form returns the cons cell returned by the outermost
call to cons.
(rplacd *c* (list 2 3))
(rplaca *c* (list 0 1))
kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Mar 29, 5:59 pm, Ken Tilton <···········@optonline.net> wrote:
> >>>Can you tell what this returns without trying it?:
>
> >>> (rplacd (loop for n below 1000 collecting n) 'migod!)
>
> >>>kenny
>
> >>>--http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>
> >>>"In the morning, hear the Way;
> >>> in the evening, die content!"
> >>> -- Confucius
>
> >>I did not study the rest of your post. But regarding the last
> >>question, I would say, (1 'migod'). Now I will go to and try it
> >>out :-)
>
> >>(Till later, I have lisp on another machine)
>
> >>Mirko
>
> > OK, I just tried it, and sure enough, I was wrong (on two counts):
> > clisp gave me (0 . 'migod!) -- well at least I will remember from now
> > on that loop for n starts from 0 (as evidently all of lisp's indexing
> > and counting).
>
> > I'll single-step through your exposition to understand it better.
>
> Well it was a slightly tricky question because everywhere else we were
> talking about building a proper list by adding directly to its tail, and
> we were doing that with (rplacd tail (list 'migod)) and I changed things
> up on you with (rplacd <list> 'migod).
>
> But I wanted to get away from list-think and get to cons-think, ie the
> cons data structure and its two slots, car and cdr. Here is another
> exercise. You want to gues at *c* all along the way:
>
> (defvar *c*)
> (setf *c* (cons 0 nil))
> (setf *c* (cons nil nil))
> (setf (car *c*) 1)
> (setf (cdr *c*) 2)
>
> Now we'll use "list", but remember:
>
> (list 1 2) is just (cons 1 (cons 2 nil))
>
> ...and so the above form returns the cons cell returned by the outermost
> call to cons.
>
> (rplacd *c* (list 2 3))
> (rplaca *c* (list 0 1))
>
> kenny
>
> --http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>
> "In the morning, hear the Way;
> in the evening, die content!"
> -- Confucius
Is this how it works? (in an explosion of enthusiasm, I started
writing the recipe entry, thus the bits of html. This is very rough
draft -- for example, no attributions yet)
** excerpt from draft **
Instead, we use a pointer, tail, to the sublist's (acc) last element.
We use the pointer to add a new element to the sublist, and then move
the pointer to the new last element.
Here it is in steps. The first time we meet two elements that are
equal (say elements a & b), we initialize the sublist and the pointer
as follows:
<pre>
(setf acc (list* a (setf tail (list b))))
</pre>
acc will be of the form (a b), result of (list* a (list b))). In
between, we have the statement pointing tail to b. At this stage,
tail is this cons:
<pre>tail --> (b . nil) </pre>
But this is embedded in acc which itself looks as
<pre>
acc --> (a . (b . nil))
^
|
+--- tail
</pre>
Now, if the next element, say c is equal to b, it needs to be added to
acc, and the tail pointer needs to be moved to it. We first set
tail's cdr to (c . nil) (just as before it was (b . nil))
<pre>
(setf (cdr tail) (list c))
</pre>
or, equivalently
<pre>
(rplacd tail (list c))
</pre>
Now, we have the following situation:
acc --> (a . (b . (c .nil)))
^
|
+--- tail
and we have to move tail to point to (c.nil). This can be
accompished with
<pre>
(setf tail (cdr tail))
</pre>
We now put the two steps together:
<pre>
(setf tail (cdr (rplacd (tail (list c)))))
^ ^ ^
| | |
| | +-- add next element to tail (and to acc)
| +-----+
| |
+-- point tail to c
</pre>
Thanks for the patience
Mirko
Mirko
The good news is that you are documenting what you learn for those who
follow, Lisp needs more noobs like you.
The bad news is "don't post yet!!". :) Read on.
·············@gmail.com wrote:
> On Mar 29, 5:59 pm, Ken Tilton <···········@optonline.net> wrote:
>
>>>>>Can you tell what this returns without trying it?:
>>
>>>>> (rplacd (loop for n below 1000 collecting n) 'migod!)
>>
>>>>>kenny
>>
>>>>>--http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>>
>>>>>"In the morning, hear the Way;
>>>>> in the evening, die content!"
>>>>> -- Confucius
>>
>>>>I did not study the rest of your post. But regarding the last
>>>>question, I would say, (1 'migod'). Now I will go to and try it
>>>>out :-)
>>
>>>>(Till later, I have lisp on another machine)
>>
>>>>Mirko
>>
>>>OK, I just tried it, and sure enough, I was wrong (on two counts):
>>>clisp gave me (0 . 'migod!) -- well at least I will remember from now
>>>on that loop for n starts from 0 (as evidently all of lisp's indexing
>>>and counting).
>>
>>>I'll single-step through your exposition to understand it better.
>>
>>Well it was a slightly tricky question because everywhere else we were
>>talking about building a proper list by adding directly to its tail, and
>>we were doing that with (rplacd tail (list 'migod)) and I changed things
>>up on you with (rplacd <list> 'migod).
>>
>>But I wanted to get away from list-think and get to cons-think, ie the
>>cons data structure and its two slots, car and cdr. Here is another
>>exercise. You want to gues at *c* all along the way:
>>
>>(defvar *c*)
>>(setf *c* (cons 0 nil))
>>(setf *c* (cons nil nil))
>>(setf (car *c*) 1)
>>(setf (cdr *c*) 2)
>>
>>Now we'll use "list", but remember:
>>
>> (list 1 2) is just (cons 1 (cons 2 nil))
>>
>>...and so the above form returns the cons cell returned by the outermost
>>call to cons.
>>
>>(rplacd *c* (list 2 3))
>>(rplaca *c* (list 0 1))
>>
>>kenny
>>
>>--http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>>
>>"In the morning, hear the Way;
>> in the evening, die content!"
>> -- Confucius
>
>
> Is this how it works? (in an explosion of enthusiasm, I started
> writing the recipe entry, thus the bits of html. This is very rough
> draft -- for example, no attributions yet)
>
> ** excerpt from draft **
>
> Instead, we use a pointer, tail, to the sublist's (acc) last element.
> We use the pointer to add a new element to the sublist, and then move
> the pointer to the new last element.
>
> Here it is in steps. The first time we meet two elements that are
> equal (say elements a & b), we initialize the sublist and the pointer
> as follows:
> <pre>
> (setf acc (list* a (setf tail (list b))))
> </pre>
> acc will be of the form (a b), result of (list* a (list b))). In
> between, we have the statement pointing tail to b.
No, tail points to (is bound to) the cons cell formed by (list b). Which
you briefly get right!:
> At this stage,
> tail is this cons:
> <pre>tail --> (b . nil) </pre>
Yes!!!
> But this is embedded in acc which itself looks as
> <pre>
> acc --> (a . (b . nil))
> ^
> |
> +--- tail
> </pre>
No!!!! Move the arrow cover to the opening parens, which is signifying
the cons cell. You have the arrow pointing to the CAR.
Hey, who has one of those cons-drawing deals? But you can find them in
all the tutorials.
> Now, if the next element, say c is equal to b, it needs to be added to
> acc, and the tail pointer needs to be moved to it.
"needs to be moved to the cons cell that will be created to hold c (in
its CAR)." Which you almost say next!:
> We first set
> tail's cdr to (c . nil) (just as before it was (b . nil))
No, it (tail) was (b . nil) and tail's CDR was nil.
> <pre>
> (setf (cdr tail) (list c))
> </pre>
> or, equivalently
> <pre>
> (rplacd tail (list c))
> </pre>
> Now, we have the following situation:
> acc --> (a . (b . (c .nil)))
> ^
> |
> +--- tail
> and we have to move tail to point to (c.nil).
Yes!!! On the "point to (c . nil)", but you /do/ need the spaces around
the . cuz this is Lisp.
> This can be
> accompished with
> <pre>
> (setf tail (cdr tail))
> </pre>
>
> We now put the two steps together:
> <pre>
> (setf tail (cdr (rplacd (tail (list c)))))
> ^ ^ ^
> | | |
> | | +-- add next element to tail (and to acc)
> | +-----+
> | |
> +-- point tail to c
> </pre>
And now the wheels fall straight off. :)
Working inside out, our first problem is:
(rplacd (tail (list c)))
...so you will get a runtime error when Lisp tries to call tail. You
meant that to be:
(rplacd tail (list c))
Now I can point out that without explanation you have settled on (cdr
(rplacd tail ...)) instead of (setf (cdr tail) ...) and this adds a
little complexity (even I tripped over it) because now you have to
discuss what RPLACD returns (necessitating the outer CDR) vs what you
also have not discussed, which is the convenience that (setf (cdr tail)
...) will return exactly what we want, the new tail.
It is fun doing (cdr (rplacd ...)), but maybe that is not a complexity
we need here (in which case you might chop the rplacd mention earlier).
Getting back to that last bit, don't forget to make the same fix here
about the tail pointing always to a cons, not b or c.
>
> Thanks for the patience
Let's see how yours is doing. :)
kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
Man, I butchered that...
Ken Tilton wrote:
> The good news is that you are documenting what you learn for those who
> follow, Lisp needs more noobs like you.
>
> The bad news is "don't post yet!!". :) Read on.
>
> ·············@gmail.com wrote:
>
>> On Mar 29, 5:59 pm, Ken Tilton <···········@optonline.net> wrote:
>>
>>>>>> Can you tell what this returns without trying it?:
>>>
>>>
>>>>>> (rplacd (loop for n below 1000 collecting n) 'migod!)
>>>
>>>
>>>>>> kenny
>>>
>>>
>>>>>> --http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>>>
>>>
>>>>>> "In the morning, hear the Way;
>>>>>> in the evening, die content!"
>>>>>> -- Confucius
>>>
>>>
>>>>> I did not study the rest of your post. But regarding the last
>>>>> question, I would say, (1 'migod'). Now I will go to and try it
>>>>> out :-)
>>>
>>>
>>>>> (Till later, I have lisp on another machine)
>>>
>>>
>>>>> Mirko
>>>
>>>
>>>> OK, I just tried it, and sure enough, I was wrong (on two counts):
>>>> clisp gave me (0 . 'migod!) -- well at least I will remember from now
>>>> on that loop for n starts from 0 (as evidently all of lisp's indexing
>>>> and counting).
>>>
>>>
>>>> I'll single-step through your exposition to understand it better.
>>>
>>>
>>> Well it was a slightly tricky question because everywhere else we were
>>> talking about building a proper list by adding directly to its tail, and
>>> we were doing that with (rplacd tail (list 'migod)) and I changed things
>>> up on you with (rplacd <list> 'migod).
>>>
>>> But I wanted to get away from list-think and get to cons-think, ie the
>>> cons data structure and its two slots, car and cdr. Here is another
>>> exercise. You want to gues at *c* all along the way:
>>>
>>> (defvar *c*)
>>> (setf *c* (cons 0 nil))
>>> (setf *c* (cons nil nil))
>>> (setf (car *c*) 1)
>>> (setf (cdr *c*) 2)
>>>
>>> Now we'll use "list", but remember:
>>>
>>> (list 1 2) is just (cons 1 (cons 2 nil))
>>>
>>> ...and so the above form returns the cons cell returned by the outermost
>>> call to cons.
>>>
>>> (rplacd *c* (list 2 3))
>>> (rplaca *c* (list 0 1))
>>>
>>> kenny
>>>
>>> --http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>>>
>>> "In the morning, hear the Way;
>>> in the evening, die content!"
>>> -- Confucius
>>
>>
>>
>> Is this how it works? (in an explosion of enthusiasm, I started
>> writing the recipe entry, thus the bits of html. This is very rough
>> draft -- for example, no attributions yet)
>>
>> ** excerpt from draft **
>>
>> Instead, we use a pointer, tail, to the sublist's (acc) last element.
>> We use the pointer to add a new element to the sublist, and then move
>> the pointer to the new last element.
>>
>> Here it is in steps. The first time we meet two elements that are
>> equal (say elements a & b), we initialize the sublist and the pointer
>> as follows:
>> <pre>
>> (setf acc (list* a (setf tail (list b))))
>> </pre>
>> acc will be of the form (a b), result of (list* a (list b))). In
>> between, we have the statement pointing tail to b.
>
>
> No, tail points to (is bound to) the cons cell formed by (list b). Which
> you briefly get right!:
>
>> At this stage,
>> tail is this cons:
>> <pre>tail --> (b . nil) </pre>
>
>
> Yes!!!
>
>> But this is embedded in acc which itself looks as
>> <pre>
>> acc --> (a . (b . nil))
>> ^
>> |
>> +--- tail
>> </pre>
>
>
> No!!!! Move the arrow cover to the opening parens, which is signifying
> the cons cell. You have the arrow pointing to the CAR.
>
> Hey, who has one of those cons-drawing deals? But you can find them in
> all the tutorials.
>
>> Now, if the next element, say c is equal to b, it needs to be added to
>> acc, and the tail pointer needs to be moved to it.
>
>
> "needs to be moved to the cons cell that will be created to hold c (in
> its CAR)." Which you almost say next!:
>
>> We first set
>> tail's cdr to (c . nil) (just as before it was (b . nil))
>
>
> No, it (tail) was (b . nil) and tail's CDR was nil.
Awful. I should have said that the first bit was right, we set the old
tail's CDR to the new cons (c . nil), but then you said "before it
[meaning the tail's CDR] was (b . nil)" and I tried badly to say, no,
the tail's CDR was nil (naturally enough) and it was the tail itself
that was (b . nil).
>
>> <pre>
>> (setf (cdr tail) (list c))
>> </pre>
>> or, equivalently
>> <pre>
>> (rplacd tail (list c))
>> </pre>
I guess here I might have argued that the two forms are not equivalent
because one returns (c) and the other returns (b c).
>> Now, we have the following situation:
>> acc --> (a . (b . (c .nil)))
>> ^
>> |
>> +--- tail
>> and we have to move tail to point to (c.nil).
>
>
> Yes!!! On the "point to (c . nil)", but you /do/ need the spaces around
> the . cuz this is Lisp.
But I forgot to remind you that the arrow needs to point to the open
parens. I do not mean to beat a dead horse, I just do not want to leave
things implicit possibly making you wonder why I did not mention it this
time.
kenny
>
>> This can be
>> accompished with
>> <pre>
>> (setf tail (cdr tail))
>> </pre>
>>
>> We now put the two steps together:
>> <pre>
>> (setf tail (cdr (rplacd (tail (list c)))))
>> ^ ^ ^
>> | | |
>> | | +-- add next element to tail (and to acc)
>> | +-----+
>> | |
>> +-- point tail to c
>> </pre>
>
>
> And now the wheels fall straight off. :)
>
> Working inside out, our first problem is:
>
> (rplacd (tail (list c)))
>
> ...so you will get a runtime error when Lisp tries to call tail. You
> meant that to be:
>
> (rplacd tail (list c))
>
> Now I can point out that without explanation you have settled on (cdr
> (rplacd tail ...)) instead of (setf (cdr tail) ...) and this adds a
> little complexity (even I tripped over it) because now you have to
> discuss what RPLACD returns (necessitating the outer CDR) vs what you
> also have not discussed, which is the convenience that (setf (cdr tail)
> ...) will return exactly what we want, the new tail.
>
> It is fun doing (cdr (rplacd ...)), but maybe that is not a complexity
> we need here (in which case you might chop the rplacd mention earlier).
>
> Getting back to that last bit, don't forget to make the same fix here
> about the tail pointing always to a cons, not b or c.
>
>>
>> Thanks for the patience
>
>
> Let's see how yours is doing. :)
>
> kenny
>
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Mar 30, 3:09 pm, Ken Tilton <···········@optonline.net> wrote:
> The good news is that you are documenting what you learn for those who
> follow, Lisp needs more noobs like you.
>
> The bad news is "don't post yet!!". :) Read on.
>
>
>
> ·············@gmail.com wrote:
> > On Mar 29, 5:59 pm, Ken Tilton <···········@optonline.net> wrote:
>
> >>>>>Can you tell what this returns without trying it?:
>
> >>>>> (rplacd (loop for n below 1000 collecting n) 'migod!)
>
> >>>>>kenny
>
> >>>>>--http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>
> >>>>>"In the morning, hear the Way;
> >>>>> in the evening, die content!"
> >>>>> -- Confucius
>
> >>>>I did not study the rest of your post. But regarding the last
> >>>>question, I would say, (1 'migod'). Now I will go to and try it
> >>>>out :-)
>
> >>>>(Till later, I have lisp on another machine)
>
> >>>>Mirko
>
> >>>OK, I just tried it, and sure enough, I was wrong (on two counts):
> >>>clisp gave me (0 . 'migod!) -- well at least I will remember from now
> >>>on that loop for n starts from 0 (as evidently all of lisp's indexing
> >>>and counting).
>
> >>>I'll single-step through your exposition to understand it better.
>
> >>Well it was a slightly tricky question because everywhere else we were
> >>talking about building a proper list by adding directly to its tail, and
> >>we were doing that with (rplacd tail (list 'migod)) and I changed things
> >>up on you with (rplacd <list> 'migod).
>
> >>But I wanted to get away from list-think and get to cons-think, ie the
> >>cons data structure and its two slots, car and cdr. Here is another
> >>exercise. You want to gues at *c* all along the way:
>
> >>(defvar *c*)
> >>(setf *c* (cons 0 nil))
> >>(setf *c* (cons nil nil))
> >>(setf (car *c*) 1)
> >>(setf (cdr *c*) 2)
>
> >>Now we'll use "list", but remember:
>
> >> (list 1 2) is just (cons 1 (cons 2 nil))
>
> >>...and so the above form returns the cons cell returned by the outermost
> >>call to cons.
>
> >>(rplacd *c* (list 2 3))
> >>(rplaca *c* (list 0 1))
>
> >>kenny
>
> >>--http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>
> >>"In the morning, hear the Way;
> >> in the evening, die content!"
> >> -- Confucius
>
> > Is this how it works? (in an explosion of enthusiasm, I started
> > writing the recipe entry, thus the bits of html. This is very rough
> > draft -- for example, no attributions yet)
>
> > ** excerpt from draft **
>
> > Instead, we use a pointer, tail, to the sublist's (acc) last element.
> > We use the pointer to add a new element to the sublist, and then move
> > the pointer to the new last element.
>
> > Here it is in steps. The first time we meet two elements that are
> > equal (say elements a & b), we initialize the sublist and the pointer
> > as follows:
> > <pre>
> > (setf acc (list* a (setf tail (list b))))
> > </pre>
> > acc will be of the form (a b), result of (list* a (list b))). In
> > between, we have the statement pointing tail to b.
>
> No, tail points to (is bound to) the cons cell formed by (list b). Which
> you briefly get right!:
>
> > At this stage,
> > tail is this cons:
> > <pre>tail --> (b . nil) </pre>
>
> Yes!!!
>
> > But this is embedded in acc which itself looks as
> > <pre>
> > acc --> (a . (b . nil))
> > ^
> > |
> > +--- tail
> > </pre>
>
> No!!!! Move the arrow cover to the opening parens, which is signifying
> the cons cell. You have the arrow pointing to the CAR.
>
> Hey, who has one of those cons-drawing deals? But you can find them in
> all the tutorials.
>
> > Now, if the next element, say c is equal to b, it needs to be added to
> > acc, and the tail pointer needs to be moved to it.
>
> "needs to be moved to the cons cell that will be created to hold c (in
> its CAR)." Which you almost say next!:
>
> > We first set
> > tail's cdr to (c . nil) (just as before it was (b . nil))
>
> No, it (tail) was (b . nil) and tail's CDR was nil.
>
> > <pre>
> > (setf (cdr tail) (list c))
> > </pre>
> > or, equivalently
> > <pre>
> > (rplacd tail (list c))
> > </pre>
> > Now, we have the following situation:
> > acc --> (a . (b . (c .nil)))
> > ^
> > |
> > +--- tail
> > and we have to move tail to point to (c.nil).
>
> Yes!!! On the "point to (c . nil)", but you /do/ need the spaces around
> the . cuz this is Lisp.
>
>
>
> > This can be
> > accompished with
> > <pre>
> > (setf tail (cdr tail))
> > </pre>
>
> > We now put the two steps together:
> > <pre>
> > (setf tail (cdr (rplacd (tail (list c)))))
> > ^ ^ ^
> > | | |
> > | | +-- add next element to tail (and to acc)
> > | +-----+
> > | |
> > +-- point tail to c
> > </pre>
>
> And now the wheels fall straight off. :)
>
> Working inside out, our first problem is:
>
> (rplacd (tail (list c)))
>
> ...so you will get a runtime error when Lisp tries to call tail. You
> meant that to be:
>
> (rplacd tail (list c))
>
> Now I can point out that without explanation you have settled on (cdr
> (rplacd tail ...)) instead of (setf (cdr tail) ...) and this adds a
> little complexity (even I tripped over it) because now you have to
> discuss what RPLACD returns (necessitating the outer CDR) vs what you
> also have not discussed, which is the convenience that (setf (cdr tail)
> ...) will return exactly what we want, the new tail.
>
> It is fun doing (cdr (rplacd ...)), but maybe that is not a complexity
> we need here (in which case you might chop the rplacd mention earlier).
>
> Getting back to that last bit, don't forget to make the same fix here
> about the tail pointing always to a cons, not b or c.
>
>
>
> > Thanks for the patience
>
> Let's see how yours is doing. :)
>
> kenny
>
I made the corrections, and I am studying your comment regarding (setf
and rplacd -- next message I believe). But my brain is shutting
down, and next week is busy, so I'll be quiet for a while.
Thanks,
Mirko
MV> What follows is a simplified version:
awful.
function that just groups duplicate elements:
(defun group (list pred)
(loop with group = (list (first list))
and groups = ()
for e in (rest list)
if (funcall pred (first group) e)
do (push e group)
else do (push group groups)
and do (setf group (list e))
finally (return (nreverse (cons group groups)))))
much shorter and simplier, isn't it?
to collect only repeats, add check like this: (when (cdr group) (push group
groups))
or use external filter, i.e.
(defun group-repeated (list pred)
(delete-if-not #'cdr (group list pred)))
On Mar 24, 10:36 am, "Alex Mizrahi" <········@users.sourceforge.net>
wrote:
> MV> What follows is a simplified version:
>
> awful.
At least one honest person :-)
>
> function that just groups duplicate elements:
>
> (defun group (list pred)
> (loop with group = (list (first list))
> and groups = ()
>
> for e in (rest list)
> if (funcall pred (first group) e)
> do (push e group)
> else do (push group groups)
> and do (setf group (list e))
>
> finally (return (nreverse (cons group groups)))))
>
> much shorter and simplier, isn't it?
>
> to collect only repeats, add check like this: (when (cdr group) (push group
> groups))
>
> or use external filter, i.e.
>
> (defun group-repeated (list pred)
> (delete-if-not #'cdr (group list pred)))
I saw several really interesting replies. I'll have to check them
out. Do the authors mind if I use theirs in the cookbook entry?
(Properly attributed, of course)
Mirko
·············@gmail.com wrote:
> On Mar 24, 10:36 am, "Alex Mizrahi" <········@users.sourceforge.net>
> wrote:
>
>> MV> What follows is a simplified version:
>>
>>awful.
>
> At least one honest person :-)
>
>>function that just groups duplicate elements:
>>
>>(defun group (list pred)
>> (loop with group = (list (first list))
>> and groups = ()
>>
>> for e in (rest list)
>> if (funcall pred (first group) e)
>> do (push e group)
>> else do (push group groups)
>> and do (setf group (list e))
>>
>> finally (return (nreverse (cons group groups)))))
>>
>>much shorter and simplier, isn't it?
>>
>>to collect only repeats, add check like this: (when (cdr group) (push group
>>groups))
>>
>>or use external filter, i.e.
>>
>>(defun group-repeated (list pred)
>> (delete-if-not #'cdr (group list pred)))
>
>
> I saw several really interesting replies. I'll have to check them
> out. Do the authors mind if I use theirs in the cookbook entry?
> (Properly attributed, of course)
>
> Mirko
Ooh! Ooh! Lemme try again!
(defun collect-repeats-simple (sorted-list &key (test 'eql))
(loop with acc and tail
for a in sorted-list
for b in (cdr sorted-list)
if (funcall test a b)
if acc do (setf tail (rplacd tail (list b)))
else do (setf acc (list* a (setf tail (list b))))
else when acc collect acc into result
and do (setf acc nil)
finally (return (nconc result
(when acc (list acc))))))
God I love rplaca/d!
kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Mar 24, 12:01 pm, Ken Tilton <···········@optonline.net> wrote:
> ·············@gmail.com wrote:
> > On Mar 24, 10:36 am, "Alex Mizrahi" <········@users.sourceforge.net>
> > wrote:
>
> >> MV> What follows is a simplified version:
>
> >>awful.
>
> > At least one honest person :-)
>
> >>function that just groups duplicate elements:
>
> >>(defun group (list pred)
> >> (loop with group = (list (first list))
> >> and groups = ()
>
> >> for e in (rest list)
> >> if (funcall pred (first group) e)
> >> do (push e group)
> >> else do (push group groups)
> >> and do (setf group (list e))
>
> >> finally (return (nreverse (cons group groups)))))
>
> >>much shorter and simplier, isn't it?
>
> >>to collect only repeats, add check like this: (when (cdr group) (push group
> >>groups))
>
> >>or use external filter, i.e.
>
> >>(defun group-repeated (list pred)
> >> (delete-if-not #'cdr (group list pred)))
>
> > I saw several really interesting replies. I'll have to check them
> > out. Do the authors mind if I use theirs in the cookbook entry?
> > (Properly attributed, of course)
>
> > Mirko
>
> Ooh! Ooh! Lemme try again!
>
> (defun collect-repeats-simple (sorted-list &key (test 'eql))
> (loop with acc and tail
> for a in sorted-list
> for b in (cdr sorted-list)
>
> if (funcall test a b)
> if acc do (setf tail (rplacd tail (list b)))
> else do (setf acc (list* a (setf tail (list b))))
> else when acc collect acc into result
> and do (setf acc nil)
>
> finally (return (nconc result
> (when acc (list acc))))))
>
> God I love rplaca/d!
>
> kenny
>
> --http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>
> "In the morning, hear the Way;
> in the evening, die content!"
> -- Confucius
Bzzt! It fails on
(collect-repeats-simple (list 1 1 2 3 3 3 3 4 5 5 6))
((1 1) (3 3 3) (5 5))
The rplacd needs to be nconc:
(collect-repeats-simple (list 1 1 2 3 3 3 3 4 5 5 6))
((1 1) (3 3 3 3) (5 5))
But still, thanks. (man I still feel like slipping on ice with these
destructive operations. Need to sharpen those skates)
Cheers,
Mirko
·············@gmail.com wrote:
> On Mar 24, 12:01 pm, Ken Tilton <···········@optonline.net> wrote:
>
>>·············@gmail.com wrote:
>>
>>>On Mar 24, 10:36 am, "Alex Mizrahi" <········@users.sourceforge.net>
>>>wrote:
>>
>>>>MV> What follows is a simplified version:
>>
>>>>awful.
>>
>>>At least one honest person :-)
>>
>>>>function that just groups duplicate elements:
>>
>>>>(defun group (list pred)
>>>> (loop with group = (list (first list))
>>>> and groups = ()
>>
>>>> for e in (rest list)
>>>> if (funcall pred (first group) e)
>>>> do (push e group)
>>>> else do (push group groups)
>>>> and do (setf group (list e))
>>
>>>> finally (return (nreverse (cons group groups)))))
>>
>>>>much shorter and simplier, isn't it?
>>
>>>>to collect only repeats, add check like this: (when (cdr group) (push group
>>>>groups))
>>
>>>>or use external filter, i.e.
>>
>>>>(defun group-repeated (list pred)
>>>> (delete-if-not #'cdr (group list pred)))
>>
>>>I saw several really interesting replies. I'll have to check them
>>>out. Do the authors mind if I use theirs in the cookbook entry?
>>>(Properly attributed, of course)
>>
>>>Mirko
>>
>>Ooh! Ooh! Lemme try again!
>>
>>(defun collect-repeats-simple (sorted-list &key (test 'eql))
>> (loop with acc and tail
>> for a in sorted-list
>> for b in (cdr sorted-list)
>>
>> if (funcall test a b)
>> if acc do (setf tail (rplacd tail (list b)))
>> else do (setf acc (list* a (setf tail (list b))))
>> else when acc collect acc into result
>> and do (setf acc nil)
>>
>> finally (return (nconc result
>> (when acc (list acc))))))
>>
>>God I love rplaca/d!
>>
>>kenny
>>
>>--http://smuglispweeny.blogspot.com/http://www.theoryyalgebra.com/
>>
>>"In the morning, hear the Way;
>> in the evening, die content!"
>> -- Confucius
>
>
> Bzzt! It fails on
> (collect-repeats-simple (list 1 1 2 3 3 3 3 4 5 5 6))
> ((1 1) (3 3 3) (5 5))
>
> The rplacd needs to be nconc:
> (collect-repeats-simple (list 1 1 2 3 3 3 3 4 5 5 6))
> ((1 1) (3 3 3 3) (5 5))
>
> But still, thanks. (man I still feel like slipping on ice with these
> destructive operations. Need to sharpen those skates)
nconc? too inefficient! I must have my rplacd!!!
:)
Try: (setf tail (cdr (rplacd tail (list b))))
kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Mar 24, 9:36 am, "Alex Mizrahi" wrote:
> (delete-if-not #'cdr ...
Victor Kryukov and I already mentioned that.
(posts #2 and #4)
--Dan
------------------------------------------------
Dan Bensen
http://www.prairienet.org/~dsb/
??>> (delete-if-not #'cdr ...
d> Victor Kryukov and I already mentioned that.
d> (posts #2 and #4)
i honor your invention of using delete-if-not for deleting unneeded data
from list, each time i'll use it again i promise to write proper
attribution.
On Mar 23, 6:20 pm, ·············@gmail.com wrote:
> Hi,
>
> I would like to submit a recipe to the lisp cookbook (http://cl-
> cookbook.sourceforge.net/). So before poisoning the unsuspected, I
> thought that the expert tasters could inspect this for obvious
> errors.
>
> The routine parses a sorted list and returns a list of duplicates.
> Thus, for the following list
> (-1 0 0 1 1 2 3 3 3 4 5 8 9 9 10 11 11)
> the routine returns
> ((0 0) (1 1) (3 3 3) (9 9) (11 11)
>
> What follows is a simplified version:
>
> (defun collect-repeats-simple (sorted-list)
> (loop
> with repeats = nil
> and acc = nil
> for a in sorted-list
> for b in (cdr sorted-list)
>
> when (and (not repeats)
> (equal a b))
> do (progn
> (setf acc (list a b))
> (setf repeats t))
>
> else
> when repeats
> when (equal a b)
> do (push b acc)
> else
> collect acc into result and
> do (progn
> (setf acc nil)
> (setf repeats nil))
>
> finally (print (if acc (append result (list acc))
> result))))
Arc:
(def collect-dups (lst)
(rev (rem [< len._ 2]
(reduce
(fn (accum e)
(if (or (is accum '(())) (is caar.accum e))
(push e car.accum)
(push list.e accum))
accum)
(cons '(()) lst)))))
danb wrote:
> On Mar 26, 6:48 pm, William James <·········@yahoo.com> wrote:
>
>>Better:
>>(def collect-dups (lst)
>> (if (is lst nil)
>> nil
>> (rev (rem [< len._ 2]
>> (reduce
>> (fn (accum e)
>> (if (in caar.accum e nil)
>> (push e car.accum)
>> (push list.e accum))
>> accum)
>> (cons (list ()) lst))))))
>
>
> Best:
Is that how you spell "shortest" on your planet?
>
> (defun collect-dupes (list)
> (let (clumps)
> (dolist (x list)
> (if (eql x (caar clumps))
> (push x (car clumps))
> (push (list x) clumps)))
> (nreverse (delete-if-not #'cdr clumps))))
I was thinking "ugliest".
And when did this turn into a consing contest? Pre-emptively consing up
solos just in case there is a duplicate??!!! We're gonna have to detox
this thread.
kenny
ps. The CAAR was nice. k
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Mar 26, 8:10 pm, Ken Tilton <···········@optonline.net> wrote:
> danb wrote:
> > On Mar 26, 6:48 pm, William James <·········@yahoo.com> wrote:
>
> >>Better:
> >>(def collect-dups (lst)
> >> (if (is lst nil)
> >> nil
> >> (rev (rem [< len._ 2]
> >> (reduce
> >> (fn (accum e)
> >> (if (in caar.accum e nil)
> >> (push e car.accum)
> >> (push list.e accum))
> >> accum)
> >> (cons (list ()) lst))))))
>
> > Best:
>
> Is that how you spell "shortest" on your planet?
>
>
>
> > (defun collect-dupes (list)
> > (let (clumps)
> > (dolist (x list)
> > (if (eql x (caar clumps))
> > (push x (car clumps))
> > (push (list x) clumps)))
> > (nreverse (delete-if-not #'cdr clumps))))
>
> I was thinking "ugliest".
You were thinking of your previous post:
(defun collect-repeats-simple (sorted-list &key (test 'eql))
(loop with acc
for a in sorted-list
for b in (cdr sorted-list)
if (funcall test (funcall key a) (funcall key b))
if acc collect b into acc
else collect a into acc
and collect b into acc
else
collect acc into result
and (setf acc nil)
finally (nconc result (when acc (list acc)))))
You are the winner of the COBOL prize.
> On Mar 26, 8:10 pm, Ken Tilton <···········@optonline.net> wrote:
> > I was thinking "ugliest".
On Mar 26, 10:00 pm, William James <·········@yahoo.com> wrote:
> You were thinking of your previous post:
>
> (defun collect-repeats-simple (sorted-list &key (test 'eql))
> (loop with acc
> for a in sorted-list
> for b in (cdr sorted-list)
>
> if (funcall test (funcall key a) (funcall key b))
> if acc collect b into acc
> else collect a into acc
> and collect b into acc
>
> else
> collect acc into result
> and (setf acc nil)
> finally (nconc result (when acc (list acc)))))
>
> You are the winner of the COBOL prize.
Congradulations, Kenny. It's well deserved.
------------------------------------------------
Dan Bensen
http://www.prairienet.org/~dsb/
danb wrote:
>>On Mar 26, 8:10 pm, Ken Tilton <···········@optonline.net> wrote:
>>
>>>I was thinking "ugliest".
>
>
> On Mar 26, 10:00 pm, William James <·········@yahoo.com> wrote:
>
>>You were thinking of your previous post:
>>
>>(defun collect-repeats-simple (sorted-list &key (test 'eql))
>> (loop with acc
>> for a in sorted-list
>> for b in (cdr sorted-list)
>>
>> if (funcall test (funcall key a) (funcall key b))
>> if acc collect b into acc
>> else collect a into acc
>> and collect b into acc
>>
>> else
>> collect acc into result
>> and (setf acc nil)
>> finally (nconc result (when acc (list acc)))))
>>
>>You are the winner of the COBOL prize.
haha, now that you mention it the similarity is striking. Nice catch! I
am glad Dan quoted this, I would have missed it in my killfile.
> Congradulations, Kenny. It's well deserved.
You won't score many points dissing Cobol. Name another language with a
two-dimensional case statement!
One nice thing about loop is that it takes obvious code (easy to write
and get right) and expands it into very efficient code.
What you had was clever, terse, and an absolute horror which missed the
point of getting the job done and done well.
I am afraid you absolutely belong in the bottom three with William.
Randy? Paula?
hth, kenny
On Mar 27, 5:57 am, Ken Tilton <···········@optonline.net> wrote:
> What you had was clever, terse, and an absolute horror
> which missed the point of getting the job done and done well.
Ken, your code is buggy.
* (defun collect-repeats-simple (sorted-list &key (test 'eql))
(loop with acc and tail
for a in sorted-list
for b in (cdr sorted-list)
if (funcall test a b)
if acc do (setf tail (rplacd tail (list b)))
else do (setf acc (list* a (setf tail (list b))))
else when acc collect acc into result
and do (setf acc nil)
finally (return (nconc result
(when acc (list acc))))))
COLLECT-REPEATS-SIMPLE
* (collect-repeats-simple '(2 2 2 2 2 2 2 2 2 2 2 2))
((2 2 2))
> One nice thing about loop is that it takes obvious code
> (easy to write and get right) and expands it into very
> efficient code.
But it doesn't design your code for you. I don't even under-
stand what you're *trying* to do in that RPLACLOOP monstrosity,
much less what it actually *does*.
> What you had was clever, terse, and an absolute horror
Kenny, you've lost your mind. The code that Victor, William,
and I have been posting is childishly simple. You (a) seed a list
with the first copy of each value, (b) push EQL values onto the
list, (c) accumulate the lists, and (d) remove singetons at the
end. Using the CAR of the overall list to hold the current list
is somewhat obfuscated, but that's part you said you liked.
> I am afraid you absolutely belong in the bottom three with William.
Yes, Your Kennyness. Shall I inform Victor that he's on the list?
--Dan
------------------------------------------------
Dan Bensen
http://www.prairienet.org/~dsb/
On Mar 23, 5:20 pm, ·············@gmail.com wrote:
> Hi,
>
> I would like to submit a recipe to the lisp cookbook (http://cl-
> cookbook.sourceforge.net/). So before poisoning the unsuspected, I
> thought that the expert tasters could inspect this for obvious
> errors.
>
> The routine parses a sorted list and returns a list of duplicates.
> Thus, for the following list
> (-1 0 0 1 1 2 3 3 3 4 5 8 9 9 10 11 11)
> the routine returns
> ((0 0) (1 1) (3 3 3) (9 9) (11 11)
(defun collect-dupe-runs (list &key (test #'eql) (key #'identity))
(loop for (current lookahead) on list
with run
do (push current run)
unless (funcall test (funcall key current)
(funcall key lookahead))
if (rest run)
collect (nreverse run)
end
and do (setf run nil)))
Small bug: on last iteration, LOOKAHEAD is NIL. Thus (collect-dupe-
runs '(nil)) returns ((NIL NIL)).
Yawn. I couldn't CAAAR less.
Okay, fine, we can fix it like this:
(defun collect-dupe-runs (list &key (test #'eql) (key #'identity))
(loop for (current lookahead) on list
for remaining-tokens on list
with run
;; always collect current token into run
do (push current run)
;; if end of input beyond current token
;; (i.e no lookahead available)
;; ship out any residual run
if (endp (rest remaining-tokens))
if (rest run) collect (nreverse run) end
;; otherwise compare current token with lookahead
;; if they are different, ship out and clear run.
else unless (funcall test (funcall key current)
(funcall key lookahead))
if (rest run) collect (nreverse run) end
and do (setf run nil)))