From: Lowell Kirsh
Subject: is there a more concise or efficient way to code this fn ?
Date:
Message-ID: <c2j8v9$62e$1@mughi.cs.ubc.ca>
I have a function that will take a list and return another list in which
consecutive elements which are 'duplicates' of each other are pared
down to a single element. The function can also take an optional
function parameter to define what is meant by 'duplicates'.
My code is below - it works fine, but I have a gut feeling it could be
better, especially in its readability.
(defun remove-consecutives (list &optional (test #'eql))
"Remove consecutive elements of a list.
i.e. (remove-consecutives '(0 0 1 2 2 3)) => (0 1 2 3)"
(labels ((help (list acc)
(cond ((null list)
(nreverse acc))
((funcall test (car list) (car acc))
(help (cdr list) acc))
(t
(help (cdr list) (cons (car list) acc))))))
(help (cdr list) (list (car list)))))
Lowell
In article <············@mughi.cs.ubc.ca>,
Lowell Kirsh <······@cs.ubc.ca> wrote:
> I have a function that will take a list and return another list in which
> consecutive elements which are 'duplicates' of each other are pared
> down to a single element. The function can also take an optional
> function parameter to define what is meant by 'duplicates'.
(defun remove-consecutives (list &optional (test #'eql))
(loop for old-val = '#:initial then cur-val
and cur-val in list
unless (funcall test old-val cur-val) collect cur-val))
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
From: Brian Downing
Subject: Re: is there a more concise or efficient way to code this fn ?
Date:
Message-ID: <lCb3c.88003$ko6.480393@attbi_s02>
In article <····························@comcast.ash.giganews.com>,
Barry Margolin <······@alum.mit.edu> wrote:
> (defun remove-consecutives (list &optional (test #'eql))
> (loop for old-val = '#:initial then cur-val
> and cur-val in list
> unless (funcall test old-val cur-val) collect cur-val))
This is probably too picky for an answer to what was probably homework. :)
CL-USER> (remove-consecutives '("INITIAL" "bad" "bad" "worse") #'string=)
("bad" "worse")
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
From: Lowell Kirsh
Subject: Re: is there a more concise or efficient way to code this fn ?
Date:
Message-ID: <c2lhbb$l01$1@mughi.cs.ubc.ca>
It's not homework!
;-)
Brian Downing wrote:
> In article <····························@comcast.ash.giganews.com>,
> Barry Margolin <······@alum.mit.edu> wrote:
>
>>(defun remove-consecutives (list &optional (test #'eql))
>> (loop for old-val = '#:initial then cur-val
>> and cur-val in list
>> unless (funcall test old-val cur-val) collect cur-val))
>
>
> This is probably too picky for an answer to what was probably homework. :)
>
> CL-USER> (remove-consecutives '("INITIAL" "bad" "bad" "worse") #'string=)
> ("bad" "worse")
>
> -bcd
> --
> *** Brian Downing <bdowning at lavos dot net>
Barry Margolin wrote:
> In article <············@mughi.cs.ubc.ca>,
> Lowell Kirsh <······@cs.ubc.ca> wrote:
>
>
>>I have a function that will take a list and return another list in which
>> consecutive elements which are 'duplicates' of each other are pared
>>down to a single element. The function can also take an optional
>>function parameter to define what is meant by 'duplicates'.
>
>
> (defun remove-consecutives (list &optional (test #'eql))
> (loop for old-val = '#:initial then cur-val
> and cur-val in list
> unless (funcall test old-val cur-val) collect cur-val))
>
(loop for (a b) on list
unless (funcall test a b)
collect a)
?
--
http://tilton-technology.com
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
From: Alain Picard
Subject: Re: is there a more concise or efficient way to code this fn ?
Date:
Message-ID: <87znaqp7y3.fsf@memetrics.com>
Kenny Tilton <·······@nyc.rr.com> writes:
> (loop for (a b) on list
> unless (funcall test a b)
> collect a)
> ?
Nope.
CL-USER>
(defun no-duplicates (list &key (test #'eql))
(loop for (a b) on list
unless (funcall test a b)
collect a))
NO-DUPLICATES
CL-USER> (no-duplicates '(a b b nil c d e nil))
(A B NIL C D E)
CL-USER>
In article <··············@memetrics.com>,
Alain Picard <············@memetrics.com> wrote:
>Kenny Tilton <·······@nyc.rr.com> writes:
>
>> (loop for (a b) on list
>> unless (funcall test a b)
>> collect a)
>> ?
>
>Nope.
>
>CL-USER>
>(defun no-duplicates (list &key (test #'eql))
> (loop for (a b) on list
> unless (funcall test a b)
> collect a))
>NO-DUPLICATES
>CL-USER> (no-duplicates '(a b b nil c d e nil))
>(A B NIL C D E)
>CL-USER>
>
a slight variation will suffice:
(defun no-duplicates (list &key (test #'eql))
(loop for (a . b) on list
when (or (null b) (not (funcall test a (first b))))
collect a))
--
---------------------------------------------------------------------
Bernhard Pfahringer, Dept. of Computer Science, University of Waikato
http://www.cs.waikato.ac.nz/~bernhard +64 7 838 4041
From: Joe Marshall
Subject: Re: is there a more concise or efficient way to code this fn ?
Date:
Message-ID: <d67mlq0m.fsf@comcast.net>
Lowell Kirsh <······@cs.ubc.ca> writes:
> I have a function that will take a list and return another list in
> which consecutive elements which are 'duplicates' of each other are
> pared down to a single element. The function can also take an optional
> function parameter to define what is meant by 'duplicates'.
>
> My code is below - it works fine, but I have a gut feeling it could be
> better, especially in its readability.
>
> (defun remove-consecutives (list &optional (test #'eql))
> "Remove consecutive elements of a list.
> i.e. (remove-consecutives '(0 0 1 2 2 3)) => (0 1 2 3)"
> (labels ((help (list acc)
> (cond ((null list)
> (nreverse acc))
> ((funcall test (car list) (car acc))
> (help (cdr list) acc))
> (t
> (help (cdr list) (cons (car list) acc))))))
> (help (cdr list) (list (car list)))))
Here's another alternative. Dunno if you can read it.
(defun remove-consecutives (list &optional (test #'eql))
(if (or (null list)
(null (cdr list)))
list
(do ((tail (cdr list) (cdr tail))
(result (list (car list)) (if (funcall test (car tail) (car result))
result
(cons (car tail) result))))
((null tail) (nreverse result)))))
Note the tests at the beginning avoid problems with
'(nil 3 4) => '(3 4)
--
~jrm
Lowell Kirsh wrote:
> I have a function that will take a list and return another list in which
> consecutive elements which are 'duplicates' of each other are pared
> down to a single element. The function can also take an optional
> function parameter to define what is meant by 'duplicates'.
>
> My code is below - it works fine, but I have a gut feeling it could be
> better, especially in its readability.
>
> (defun remove-consecutives (list &optional (test #'eql))
> "Remove consecutive elements of a list.
> i.e. (remove-consecutives '(0 0 1 2 2 3)) => (0 1 2 3)"
> (labels ((help (list acc)
> (cond ((null list)
> (nreverse acc))
> ((funcall test (car list) (car acc))
> (help (cdr list) acc))
> (t
> (help (cdr list) (cons (car list) acc))))))
> (help (cdr list) (list (car list)))))
>
> Lowell
>
Your code is fine and no less concise than any recursive version I can
think of. The alternatives that others have suggested are probably more
efficient (as well as being quite concise) since they are
iterative--unless you know that your compiler is properly tail-recursive
(you have written it correctly to take advantage of tail recursion, but
Common Lisp doesn't guarantee that a compiler will cooperate).
(One nitpick--your documentation should say 'e.g.' rather than 'i.e.')
David Sletten
David Sletten <·····@slytobias.com> wrote in message news:<····················@twister.socal.rr.com>...
> Lowell Kirsh wrote:
> > My code is below - it works fine, but I have a gut feeling it could be
> > better, especially in its readability.
> >
> > (defun remove-consecutives (list &optional (test #'eql))
> > "Remove consecutive elements of a list.
> > i.e. (remove-consecutives '(0 0 1 2 2 3)) => (0 1 2 3)"
> > (labels ((help (list acc)
> > (cond ((null list)
> > (nreverse acc))
> > ((funcall test (car list) (car acc))
> > (help (cdr list) acc))
> > (t
> > (help (cdr list) (cons (car list) acc))))))
> > (help (cdr list) (list (car list)))))
>
> Your code is fine and no less concise than any recursive version I can
> think of. The alternatives that others have suggested are probably more
> efficient (as well as being quite concise) since they are
> iterative--unless you know that your compiler is properly tail-recursive
> (you have written it correctly to take advantage of tail recursion, but
> Common Lisp doesn't guarantee that a compiler will cooperate).
I personally would use this to bang out code, but I know it's not the
sort of thing common lispers love...
(defun remove-consecutives (list &optional (test #'eql))
(fold-right (lambda (item accum)
(if (and (consp accum)
(funcall test item (first accum)))
accum
(cons item accum)))
list))
Where fold-right is predefined in my environment as...
(defun fold-right (fun list &optional (init nil))
"f(x1, f(x2, ... f(xn, init)))"
(if (null list)
init
(funcall fun (car list)
(fold-right fun (cdr list) init))))
A couple test cases check out...
(equal '(0 1 2 3 nil)
(remove-consecutives '(0 0 1 2 2 3 nil)))
(equal '(0 1 2 3 nil)
(remove-consecutives '(0 0 1 2 2 3 nil nil)))
(equal '(nil 0 1 2 3 nil)
(remove-consecutives '(nil nil 0 0 1 2 2 3 nil nil)))
After all, why explicitly accumulate a data structure when lisp
already has a nice invisible function stack? ;) Seriously, Duane
Rettig kindly explains the tradeoffs in
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&safe=off&selm=4u14u8ejg.fsf%40franz.com
But I am an arrogant codemonkey who does not think the rules apply to
him. Of course I would likely not do this if I were responsible for
someone else's needs. However, lisp represents for me a liberation
for my personal uses, and I would not use it if I had to tiptoe around
some compiler in order to create the best notation. My real version
of fold-right even uses the "nil?" macro because "null" is too
irregular and I won't put up with that crap.
Tayssir John Gabbour wrote:
> Where fold-right is predefined in my environment as...
>
> (defun fold-right (fun list &optional (init nil))
> "f(x1, f(x2, ... f(xn, init)))"
> (if (null list)
> init
> (funcall fun (car list)
> (fold-right fun (cdr list) init))))
Sidenote: You can implement fold-right like this.
(defun fold-right (fun list &optional (init nil)
(reduce fun list :from-end t :initial-value init))
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
From: Marcus Breiing
Subject: Re: is there a more concise or efficient way to code this fn ?
Date:
Message-ID: <WHDBINfdhqr@breiing.com>
* Tayssir John Gabbour
> I personally would use this to bang out code, but I know it's not the
> sort of thing common lispers love...
> (defun remove-consecutives (list &optional (test #'eql))
> (fold-right (lambda (item accum)
> (if (and (consp accum)
> (funcall test item (first accum)))
> accum
> (cons item accum)))
> list))
Interesting! Having dabbled in CL for a while now, I notice that I
have come to use a noticeably more "imperative" style with it than I
might have guessed beforehand. (Did evil macros make me do it?)
Here's how I probably would have written the function, using a DO-RUNS
macro I defined a while ago:
(defun remove-consecutives (list &key (test #'eql))
(collecting
(do-runs (begin end repr list :test test)
(collect repr))))
This expands to
(defun remove-consecutives (list &key (test #'eql))
(let (|01| |02|)
(flet ((collect (x) x))
(declare (inline collect))
(flet ((collect (elt)
(setf |02|
(if |02|
(setf (cdr |02|) (list elt))
(setf |01| (list elt))))
(collect elt)))
(declare (inline collect))
(symbol-macrolet nil
(do ((begin list end)
(end))
((null begin))
(let ((repr (car begin)))
(setf end (do ((e (cdr begin) (cdr e)))
((not (and e (funcall test repr (car e)))) e) ))
(collect repr)))
(values |01|))))))
The OP says he's after an efficient version, so I'm posting this,
since (on LispWorks for Windows) I timed it as somewhat faster than
Wolfgang's LOOP variant.
Marcus
--
Marcus Breiing http://breiing.com/postings/WHDBINfdhqr
On 10 Mar 2004, Marcus Breiing <- ···············@breiing.com wrote:
> The OP says he's after an efficient version, so I'm posting this,
> since (on LispWorks for Windows) I timed it as somewhat faster than
> Wolfgang's LOOP variant.
With Clisp (Windows/Cygwin) the loop is the fastest and most space
efficient solution. A tail recursive solution is second best and third
are your solution and a version with reduce (but written as fold-left
not as fold-right as from another poster) (the fold-left uses a bit less
space than your version). The fold-right version is the worst.
All functions compiled only with compile.
KP
--
M�nner der Wissenschaft! Man sagt ihr viele nach,
aber die meisten mit Unrecht.
Karl Kraus 'Aphorismen'
From: Marcus Breiing
Subject: Re: is there a more concise or efficient way to code this fn ?
Date:
Message-ID: <ZN1iTPu6RQX@breiing.com>
* Karl Pfl�sterer
> With Clisp (Windows/Cygwin) the loop is the fastest and most space
> efficient solution. A tail recursive solution is second best and third
> are your solution and a version with reduce (but written as fold-left
> not as fold-right as from another poster) (the fold-left uses a bit less
> space than your version). The fold-right version is the worst.
Indeed: Clisp doesn't seem to inline the local functions that result
from expanding my version of the COLLECTING macro. Versions of that
macro floating around the net mostly use MACROLET. I replaced that
with local inline functions because I like the added functionality,
and found no significant performance differences under Lispworks
(Windows) or Cmucl (Linux). I don't know if Clisp could be persuaded
to do the inlining at all, I'm not using it much.
Marcus
--
Marcus Breiing http://breiing.com/postings/ZN1iTPu6RQX
······@12move.de (Karl Pfl�sterer) wrote in message news:<··············@hamster.pflaesterer.de>...
> On 10 Mar 2004, Marcus Breiing <- ···············@breiing.com wrote:
>
> > The OP says he's after an efficient version, so I'm posting this,
> > since (on LispWorks for Windows) I timed it as somewhat faster than
> > Wolfgang's LOOP variant.
>
> With Clisp (Windows/Cygwin) the loop is the fastest and most space
> efficient solution. A tail recursive solution is second best and third
> are your solution and a version with reduce (but written as fold-left
> not as fold-right as from another poster) (the fold-left uses a bit less
> space than your version). The fold-right version is the worst.
>
> All functions compiled only with compile.
A couple ad-hoc tests show that the space efficiency of the non-loop
versions converge near the loop version's, as the input list grows
larger. Clisp 2.32 (Windows 2k, under DOS).
Also, the tail recursive version (from the original poster) happens to
have the same speed as the loop version. Despite the tail recursive
one having less than half the bytecode footprint. Nice to know there
are no absolutes. ;)
(defmacro time-a-lot (times (&rest functions-to-compile) &rest form)
"Execute form times times. Compile functions-to-compile
beforehand."
(let ((unused-var (gensym)))
`(progn
,@(mapcar (lambda (f) `(compile (quote ,f)))
functions-to-compile)
(time (dotimes (,unused-var ,times)
(declare (ignore ,unused-var))
,@form)))))
Incidentally, fold-right can trivially be defined iteratively, so my
solution is not as interestingly dangerous as I'd like it to be. ;)
After all, it just does f(x1, f(x2, ... f(xn, init))).
(defun remove-consecutives (list &optional (test #'eql))
(fold-right (lambda (item accum)
(if (and (consp accum) ;take care of pesky empty-list
(funcall test item (first accum)))
accum
(cons item accum)))
list))
* Lowell Kirsh writes:
> I have a function that will take a list and return another list in
> which consecutive elements which are 'duplicates' of each other are
> pared down to a single element. The function can also take an optional
> function parameter to define what is meant by 'duplicates'.
Barry's ansatz, slightly polished:
(defun remove-consecutives (list &key (test #'eql))
(loop for (item . rest) on list
unless (and rest (funcall test item (first rest)))
collect item))
--
"Hurry if you still want to see something. Everything is vanishing."
-- Paul C�zanne (1839-1906)
From: Lowell Kirsh
Subject: Re: is there a more concise or efficient way to code this fn ?
Date:
Message-ID: <c2lhva$l8h$1@mughi.cs.ubc.ca>
It looks like this may be the best answer. Maginally better than mine in
readability imho, and probably faster becasue it's non-recursive. I will
test it to see.
Wolfhard Bu� wrote:
> * Lowell Kirsh writes:
>
>
>>I have a function that will take a list and return another list in
>>which consecutive elements which are 'duplicates' of each other are
>>pared down to a single element. The function can also take an optional
>>function parameter to define what is meant by 'duplicates'.
>
>
> Barry's ansatz, slightly polished:
>
> (defun remove-consecutives (list &key (test #'eql))
> (loop for (item . rest) on list
> unless (and rest (funcall test item (first rest)))
> collect item))
>
* Lowell Kirsh wrote:
> I have a function that will take a list and return another list in
> which consecutive elements which are 'duplicates' of each other are
> pared down to a single element. The function can also take an optional
> function parameter to define what is meant by 'duplicates'.
* I wrote:
> Barry's ansatz, slightly polished:
>
> (defun remove-consecutives (list &key (test #'eql))
> (loop for (item . rest) on list
> unless (and rest (funcall test item (first rest)))
> collect item))
A bit more polished...
(defun remove-consecutives (list &key (test #'eql))
(unless (endp list)
(cons (first list)
(loop for item = (first list) then next-item
and next-item in (rest list)
unless (funcall test item next-item)
collect next-item))))
--
"Hurry if you still want to see something. Everything is vanishing."
-- Paul C�zanne (1839-1906)
* Lowell Kirsh wrote:
> I have a function that will take a list and return another list in
> which consecutive elements which are 'duplicates' of each other are
> pared down to a single element. The function can also take an optional
> function parameter to define what is meant by 'duplicates'.
* I wrote:
> Barry's ansatz, slightly polished:
>
> (defun remove-consecutives (list &key (test #'eql))
> (loop for (item . rest) on list
> unless (and rest (funcall test item (first rest)))
> collect item))
> A bit more polished...
>
> (defun remove-consecutives (list &key (test #'eql))
> (unless (endp list)
> (cons (first list)
> (loop for item = (first list) then next-item
> and next-item in (rest list)
> unless (funcall test item next-item)
> collect next-item))))
A bit more efficient...
(defun remove-consecutives (list &key (test #'eql))
(unless (endp list)
(cons (first list)
(loop with item = (first list)
for next-item in (rest list)
unless (funcall test item next-item)
collect (setq item next-item)))))
--
"Hurry if you still want to see something. Everything is vanishing."
-- Paul C�zanne (1839-1906)
From: Marco Antoniotti
Subject: Re: is there a more concise or efficient way to code this fn ?
Date:
Message-ID: <Fw14c.95$IJ5.77113@typhoon.nyu.edu>
Pardon my obtuseness, but...
(remove-duplicates '(0 0 1 2 2 3)) ==> (0 1 2 3)
or
(remove-duplicates '(0 0 1 2 2 3) :test #'=) ==> (0 1 2 3)
Cheers
marco
Lowell Kirsh wrote:
> I have a function that will take a list and return another list in which
> consecutive elements which are 'duplicates' of each other are pared
> down to a single element. The function can also take an optional
> function parameter to define what is meant by 'duplicates'.
>
> My code is below - it works fine, but I have a gut feeling it could be
> better, especially in its readability.
>
> (defun remove-consecutives (list &optional (test #'eql))
> "Remove consecutive elements of a list.
> i.e. (remove-consecutives '(0 0 1 2 2 3)) => (0 1 2 3)"
> (labels ((help (list acc)
> (cond ((null list)
> (nreverse acc))
> ((funcall test (car list) (car acc))
> (help (cdr list) acc))
> (t
> (help (cdr list) (cons (car list) acc))))))
> (help (cdr list) (list (car list)))))
>
> Lowell
>
* Lowell Kirsh wrote:
> I have a function that will take a list and return another list in
> which consecutive elements which are 'duplicates' of each other are
> pared down to a single element. The function can also take an
> optional function parameter to define what is meant by 'duplicates'.
* Marco Antoniotti writes:
> Pardon my obtuseness, but...
>
> (remove-duplicates '(0 0 1 2 2 3)) ==> (0 1 2 3)
>
> or
>
> (remove-duplicates '(0 0 1 2 2 3) :test #'=) ==> (0 1 2 3)
remove-consecutives is not remove-duplicates, at least not for all
arguments.
(remove-consecutives '(0 0 1 2 2 0)) ==> (0 1 2 0)
--
"Thomas had been the driver of the doomed car."
-- Irving 1998
From: Marco Antoniotti
Subject: Re: is there a more concise or efficient way to code this fn ?
Date:
Message-ID: <DJ24c.96$IJ5.76881@typhoon.nyu.edu>
Wolfhard Bu� wrote:
> * Lowell Kirsh wrote:
>
>
>>I have a function that will take a list and return another list in
>>which consecutive elements which are 'duplicates' of each other are
>>pared down to a single element. The function can also take an
>>optional function parameter to define what is meant by 'duplicates'.
>
>
> * Marco Antoniotti writes:
>
>
>>Pardon my obtuseness, but...
>>
>> (remove-duplicates '(0 0 1 2 2 3)) ==> (0 1 2 3)
>>
>>or
>>
>> (remove-duplicates '(0 0 1 2 2 3) :test #'=) ==> (0 1 2 3)
>
>
> remove-consecutives is not remove-duplicates, at least not for all
> arguments.
>
> (remove-consecutives '(0 0 1 2 2 0)) ==> (0 1 2 0)
>
Ok. Now it is clear.
Apologies for the noise
Cheers
--
Marco