The following function removes only the first occurrence of an element
from a list. Is this very different than how experienced Lispers do
things? The function is part of my homework assignment. However, my
homework is just to write a function that does its job. I am trying to
learn if there are better ways to do it.
(defun remv (item l)
"a function to remove (without modifying the list) the FIRST
occurrence of a given element"
(let ((result-list nil)(flag 0))
(dolist (curr l)
(if (equalp curr item)
( if(equalp flag 1) (push curr result-list) (setq flag 1))
(push curr result-list)))
(reverse result-list)))
Look at it this way, there are three things that can happen when you
call this function:
If the list is empty, return the list.
If the car of the list is equal to the item, return the cdr of the
list
Else cons the car of the list with the result of calling the function
with the cdr of the list
How would that look in Lisp?
Which do you like better?
Griff <·······@gmail.com> writes:
> Look at it this way, there are three things that can happen when you
> call this function:
>
> If the list is empty, return the list.
>
> If the car of the list is equal to the item, return the cdr of the
> list
>
> Else cons the car of the list with the result of calling the function
> with the cdr of the list
>
> How would that look in Lisp?
>
> Which do you like better?
Extra credit for the OP:
* Do you know about the difference between real recursion and tail recursion?
* Do you know how CL manages tail recursion?
* Do you know how the DO construct and tail recursion relate to one another?
(Aside: I just recently added some code examples in the Portuguese
Wikipedia that might or might not help illustrate these issues.
http://pt.wikipedia.org/wiki/Lisp#Fatorial
It may be possible to piece out the point even without understanding
the surrounding text, which isn't remarkably detailed on the point anyway.)
The reason I mention all of this is that Griff's remarks here might lead
you into a recursive solution, and I'm not sure that's a good idea in CL
for this particular problem.
I was actually extremely heartened to see someone taking a class actually
using DOLIST in a decent way that wasn't prone to stack overflow.
On Jan 30, 12:46 am, Kent M Pitman <······@nhplace.com> wrote:
> The reason I mention all of this is that Griff's remarks here might lead
> you into a recursive solution, and I'm not sure that's a good idea in CL
> for this particular problem.
I do not see anything wrong with Griff's suggestion, or with the
recursion entailed (pun not intended). And at least when I look at it
implemented, it is clearly tail recursive (or rather tail recursive,
modulo cons, which for any decent compiler is tail recursive), any
compiler worth it's salt will clean that up nicely. Further, I think
Griff's suggestion is one of the cleanest solutions to this problem
(presuming it's a pedagogical exercise which outlaws the use of the
REMOVE, etc.)
Presuming this is a pedagogical exercise, I would assume that it's
being used to illustrate potential lisp iteration mechanisms, like CDR-
ing down a list, or a DO loop, etc. to the OP, a PUSH nested in a
DOLIST is almost never what is needed/wanted.
And as Ken acknowledges, Griff's suggestion is even cleaner than the
LOOP version (and if there's a clean LOOP solution I trust Ken to find
it), in my implementation of Griff's suggestion, it uses fewer
symbols, is easier to see what's going on, and as I said, any good
compiler should have those performing at that same efficiency,
possibly even faster with the recursive solution, because it doesn't
require a flag to signal done.
As others have pointed out, to the OP, it would be good to contrast,
the various solutions, the original (DOLIST PUSH) is pure side effect
plus a reverse, a DO with a REVERSE at the end has no side effects,
but the disadvantage of the extra traversal for the REVERSE, the LOOP
is single iteration, but has a flag, and so it's quite as functional
in style as Griff's suggestion, which is also single iteration.
On Jan 30, 1:39 am, K Livingston <······················@gmail.com>
wrote:
>a DO with a REVERSE at the end has no side effects,
> but the disadvantage of the extra traversal for the REVERSE
just out of curiosity (and possibly in bad form for replying to my own
comment), it seems that a reasonably common form is
(do ((results nil (cons <something> results))
...)
(( ... ) (reverse results)))
it strikes me that a clever compiler could unroll that, and not
require the second traversal and just build up results in reverse, as
it would while performing a MAPCAR or the like. While it could do
this, do any compilers actually do that?
I understand of course, that LOOP could frequently be used to avoid
the second iteration, but since the results are effectively
isomorphic, it be nice if the compiler would "do what I mean" and
build the more efficient version whenever possible, allowing the
programmer to always write what's easiest to code/maintain/understand
for the situation.
From: Thomas A. Russ
Subject: Re: complier optimization for DO returning REVERSE, WAS: Re: newbie exploring better ways
Date:
Message-ID: <ymiejbzvy9s.fsf@blackcat.isi.edu>
K Livingston <······················@gmail.com> writes:
> On Jan 30, 1:39 am, K Livingston <······················@gmail.com>
> wrote:
> >a DO with a REVERSE at the end has no side effects,
> > but the disadvantage of the extra traversal for the REVERSE
>
> just out of curiosity (and possibly in bad form for replying to my own
> comment), it seems that a reasonably common form is
>
> (do ((results nil (cons <something> results))
> ...)
> (( ... ) (reverse results)))
>
> it strikes me that a clever compiler could unroll that, and not
> require the second traversal and just build up results in reverse, as
> it would while performing a MAPCAR or the like.
Well, first of all, the compiler would have to have some way of making
sure that there were no side effects contained in the ... or (even more
difficult), prove to itself that any side effects don't affect the
computation of the results.
For a simple example that would persumably give the compiler fits trying
to figure out:
(let ((counter 0)
(limit 10))
(do ((results nil (cons (incf counter) results)))
((>= counter limit) (reverse results))))
> While it could do
> this, do any compilers actually do that?
I doubt it. While unrolling a loop may be a standard compiler trick,
reversing the direction of loop traversal seems a bit much.
--
Thomas A. Russ, USC/Information Sciences Institute
Den Tue, 29 Jan 2008 23:39:59 -0800 skrev K Livingston:
> On Jan 30, 12:46 am, Kent M Pitman <······@nhplace.com> wrote:
>> The reason I mention all of this is that Griff's remarks here might
>> lead you into a recursive solution, and I'm not sure that's a good idea
>> in CL for this particular problem.
>
> I do not see anything wrong with Griff's suggestion, or with the
> recursion entailed (pun not intended). And at least when I look at it
> implemented, it is clearly tail recursive (or rather tail recursive,
> modulo cons, which for any decent compiler is tail recursive), any
> compiler worth it's salt will clean that up nicely.
This is absolutely untrue. TCO is not mandated by the language standard,
therefore relying on it is like writing code that depended on certain
variables being elided by the compiler in optimisation phase. It's been
discussed many times here; TCO is not just something you drop into your
code and merrily go your way, it depends on any number of factors and
might easily not kick in because there are some factors the compiler
decided precluded its use. For instance, in SBCL (declare (optimize
(debug 3))) will turn it off, because the transformation done by TCO is
too intrusive to allow having it. Would you consider code that failed to
work because you turned on debugging to be correct?
It's okay to present a recursive solution for its conceptual elegance,
but it's utterly and completely wrong to present it without appropriate
disclaimers about inherent limitations, or claim that these limitations
are just a matter of using a better compiler. They're not.
Cheers,
Maciej
On Jan 30, 5:16 am, Maciej Katafiasz <········@gmail.com> wrote:
> This is absolutely untrue. TCO is not mandated by the language standard,
> therefore relying on it is like writing code that depended on certain
> variables being elided by the compiler in optimisation phase. It's been
> discussed many times here; TCO is not just something you drop into your
> code and merrily go your way, it depends on any number of factors and
.. snip ..
> It's okay to present a recursive solution for its conceptual elegance,
> but it's utterly and completely wrong to present it without appropriate
> disclaimers about inherent limitations, or claim that these limitations
> are just a matter of using a better compiler. They're not.
That's a very good point. While the CL compiler I use daily (Allegro)
does it (I use CLISP periodically and thought it does it, I thought
most do, I could be very wrong), regardless I have probably grown to
count on it a little more than I should - as you are right it's not
something that is guaranteed or specified. When available though, I'm
going to use all the tools in my box.
And then, if it doesn't, or it's slow, when I profile it, I will see
that. If I can write a simple 3 line tail recursive version (when the
others seem longer or more difficult to conceive), I'm probably going
to write it, because it's fast to write and easy to maintain. If the
profiler says it is (too) slow, I'll change it when, and if, it's a
problem.
Thanks for not letting me reinforce only part of the story.
Thank you all. It isn't that I knew other solutions but the teacher
explicitly has asked to "Try to write this as an iterative function,
using either the function do or dolist.".
K Livingston <······················@gmail.com> writes:
> I do not see anything wrong with Griff's suggestion, or with the
> recursion entailed (pun not intended). And at least when I look at it
> implemented, it is clearly tail recursive (or rather tail recursive,
> modulo cons, which for any decent compiler is tail recursive), any
> compiler worth it's salt will clean that up nicely.
Sure, if by "any compiler worth it's salt" you mean "no existing CL
compiler". Unfortunately most of us need to program using real
implementations instead of the platonic ideal of a CL implementation.
--
Juho Snellman
vijay wrote:
> The following function removes only the first occurrence of an element
> from a list. Is this very different than how experienced Lispers do
> things? The function is part of my homework assignment. However, my
> homework is just to write a function that does its job. I am trying to
> learn if there are better ways to do it.
>
> (defun remv (item l)
> "a function to remove (without modifying the list) the FIRST
> occurrence of a given element"
> (let ((result-list nil)(flag 0))
> (dolist (curr l)
> (if (equalp curr item)
> ( if(equalp flag 1) (push curr result-list) (setq flag 1))
> (push curr result-list)))
> (reverse result-list)))
Not (remove item l :count 1)? :)
OK, presuming you were under orders to roll your own implementation from
more basic stuff, Griff has given you excellent guidance on how to
create a neater solution. On a grander level...
I think you asked because you already sensed it could be done more
easily. I know the feeling, witness a couple of threads I started here
on real-world problems that began "There's gotta be a better way" and
like you I was just going from a gut feel in re the contrast between the
task and the code I had produced to accomplish it.
So in this case, an experienced lisper would conclude (as you seemed to
have) whoa that is too much. How about?:
(loop with nailed
for x in l
if nailed collect x
else if (equalp x item) do (setf nailed t)
else collect x)
But in this case Griff's recursive solution is vastly nicer and more
elegant and functional and good with children, you should work that out.
Your teacher will know you got help, so show them both versions.
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
Ken Tilton <·········@gmail.com> wrote:
+---------------
| Not (remove item l :count 1)? :)
+---------------
Thanks!! That's what I love about CL! There's always more to learn.
Yes, call me slow, but in >6 years of coding CL I've never used :COUNT
with REMOVE/DELETE/etc. I've used REPEAT with LOOP, though... ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
vijay <········@gmail.com> writes:
> The following function removes only the first occurrence of an element
> from a list. Is this very different than how experienced Lispers do
> things? The function is part of my homework assignment. However, my
> homework is just to write a function that does its job. I am trying to
> learn if there are better ways to do it.
>
> (defun remv (item l)
> "a function to remove (without modifying the list) the FIRST
> occurrence of a given element"
> (let ((result-list nil)(flag 0))
> (dolist (curr l)
> (if (equalp curr item)
> ( if(equalp flag 1) (push curr result-list) (setq flag 1))
> (push curr result-list)))
> (reverse result-list)))
"nil)(flag" => "nil) (flag"
Never use ")(" without space between.
"( if" => "(if "
Try never to use an open paren followed by a symbol with horizontal
whitespace in between unless there is a strong special reason. (You
don't have such a reason here.)
"if(" => "if ("
A symbol folowed by an open-paren should always have whitespace between.
Instead of 0/1, why not use T/NIL values?
Did your teacher suggest EQUALP for the comparison of curr with item?
EQUALP is not the normal predicate Lisp uses.
Why are you using EQUALP rather than EQL for comparing to 1? EQUALP
is a "forgiving" compare that tends to be slow. In this case, a
compiler may optimize the use. But try to use EQL in cases where it
works. (If you rewrite without the 0/1 thing, this use may go away of
its own accord.
When talking about an empty list, use '() rather than nil as a matter
of style. They are the selfsame object, but notationally nil as a
variable usually cues the human programmer reading your code that
false is intended, while '() cues the human that it's an empty list.
remv is a terrible function name. If the teacher gave it to you, tell
him/her I suggested remove1 as a better name. Lisp isn't just a unix
shell scripting language. Vowels are ok.
Likewise, I encourage variable names spelled out in most cases. current
rather than curr, for example.
If I kept the text as you'd written it, I'd still rather nreverse at
the end than reverse. There's no reason to cons up new structure when
you've already just made a bunch of structure and are about to throw
it away. But ...
Extra credit: Rather than uselessly looping down the list after you find
the thing you want, why not learn about NRECONC. There are so few examples
of places you can use that function. And this is one of them.
Btw, since you asked: Real Lisp programmers would just call REMOVE
with appropriate args.
(remove 3 (list 1 2 3 1 2 3 1 2 3) :count 1)
=> (1 2 1 2 3 1 2 3)
On 30 Jan, 03:42, vijay <········@gmail.com> wrote:
> The following function removes only the first occurrence of an element
> from a list. Is this very different than how experienced Lispers do
> things? The function is part of my homework assignment. However, my
> homework is just to write a function that does its job. I am trying to
> learn if there are better ways to do it.
>
> (defun remv (item l)
> "a function to remove (without modifying the list) the FIRST
> occurrence of a given element"
> (let ((result-list nil)(flag 0))
> (dolist (curr l)
> (if (equalp curr item)
> ( if(equalp flag 1) (push curr result-list) (setq flag 1))
> (push curr result-list)))
> (reverse result-list)))
In Qi
(define remv
_ [] -> [] \second input = [] (NIL)? then return [] \
X [X | Y] -> Y \first input = head of second input, return
tail of second input\
X [_ | Y] -> (remv X Y)) \otherwise recurse on the tail of the
second input\
I generally give the Lisp equivalent to any Qi solution, but since you
mention 'the dreaded 'h word' I suppose I'd better not. You should be
able to figure out the Lisp.
Mark
On 30 Jan, 13:59, Mark Tarver <··········@ukonline.co.uk> wrote:
> On 30 Jan, 03:42, vijay <········@gmail.com> wrote:
>
> > The following function removes only the first occurrence of an element
> > from a list. Is this very different than how experienced Lispers do
> > things? The function is part of my homework assignment. However, my
> > homework is just to write a function that does its job. I am trying to
> > learn if there are better ways to do it.
>
> > (defun remv (item l)
> > "a function to remove (without modifying the list) the FIRST
> > occurrence of a given element"
> > (let ((result-list nil)(flag 0))
> > (dolist (curr l)
> > (if (equalp curr item)
> > ( if(equalp flag 1) (push curr result-list) (setq flag 1))
> > (push curr result-list)))
> > (reverse result-list)))
>
> In Qi
>
> (define remv
> _ [] -> [] \second input = [] (NIL)? then return [] \
> X [X | Y] -> Y \first input = head of second input, return
> tail of second input\
> X [_ | Y] -> (remv X Y)) \otherwise recurse on the tail of the
> second input\
>
> I generally give the Lisp equivalent to any Qi solution, but since you
> mention 'the dreaded 'h word' I suppose I'd better not. You should be
> able to figure out the Lisp.
>
> Mark
Darn - forgot to cons the head - should be
(define rem
\second input = [] (NIL)? then return [] \
_ [] -> []
\first input = head of second input return tail of second input\
X [X | Y] -> Y
\otherwise cons the head and recurse on the tail of the second input
\
X [Y | Z] -> [Y | (rem X Z)])
Mark
* vijay Wrote on Tue, 29 Jan 2008 19:42:21 -0800 (PST):
| The following function removes only the first occurrence of an element
| from a list. Is this very different than how experienced Lispers do
| things? The function is part of my homework assignment. However, my
| homework is just to write a function that does its job. I am trying to
| learn if there are better ways to do it.
Try this consing solution. Read the CL hyperspec for specifications of
the functions used here. If you want to share structure with the
original list, you can use NCONC instead of APPEND.
(defun remove-first-occurrence (item list)
(let ((cons (member item list)))
(append (ldiff list cons) (cdr cons))))
--
Madhu
Madhu <·······@meer.net> writes:
> * vijay Wrote on Tue, 29 Jan 2008 19:42:21 -0800 (PST):
>
> | The following function removes only the first occurrence of an element
> | from a list. Is this very different than how experienced Lispers do
> | things? The function is part of my homework assignment. However, my
> | homework is just to write a function that does its job. I am trying to
> | learn if there are better ways to do it.
>
> Try this consing solution. Read the CL hyperspec for specifications of
> the functions used here. If you want to share structure with the
> original list, you can use NCONC instead of APPEND.
Minor technical nit: APPEND will share structure with the original
list. The final list in append will be shared. NCONC will
destructively modify all but the last list.
> (defun remove-first-occurrence (item list)
> (let ((cons (member item list)))
> (append (ldiff list cons) (cdr cons))))
--
Thomas A. Russ, USC/Information Sciences Institute