Hey everybody!
Can anybody explain me how to construct a Lisp function, which will
remove (without modifying the list) 1) the first occurrence of a given
element from a flat list, 2) all such occurences from the list. We
assume that if the element is not in the list, the original list will
be returned.
At least tell me, please, which constructs should I use to build such
a function.
I am just beginning to study Lisp, so any advice regarding such
constructs would be really helpful.
Thanks.
Arsen
The CL way is (remove what-to-remove list) or (remove what-to-remove
list :count 1)
If you wish to build the function yourself, you can do it through
iteration or recursion. The recursion approach (which may not work on
long lists) involves taking a list, looking at its car and cdr, seeing
if the car should be deleted. If so, simply recurse on the cdr of the
list; otherwise, return the cons of the current element with the
results of the recursive processing.
Since this sounds a lot like homework, I won't post any specific code,
though the text above should get you started; take a look at a basic
lisp tutorial or Practical Common Lisp (available online) for more
details.
Alex
On Feb 5, 5:24 pm, ············@gmail.com wrote:
> Hey everybody!
>
> Can anybody explain me how to construct a Lisp function, which will
> remove (without modifying the list) 1) the first occurrence of a given
> element from a flat list, 2) all such occurences from the list. We
> assume that if the element is not in the list, the original list will
> be returned.
>
> At least tell me, please, which constructs should I use to build such
> a function.
>
> I am just beginning to study Lisp, so any advice regarding such
> constructs would be really helpful.
>
> Thanks.
> Arsen
Alex,
It is a homework!
But what you are talking about is a removing of all occurences of an
element!
Or I am wrong?!
There is no need for the specific code. Please just clearify this
point.
And what do you mean when you say recurse on the cdr of the list?
Thanks
Arsen
On 5 ÆÅ×, 19:36, ··········@gmail.com wrote:
> The CL way is (remove what-to-remove list) or (remove what-to-remove
> list :count 1)
>
> If you wish to build the function yourself, you can do it through
> iteration or recursion. The recursion approach (which may not work on
> long lists) involves taking a list, looking at its car and cdr, seeing
> if the car should be deleted. If so, simply recurse on the cdr of the
> list; otherwise, return the cons of the current element with the
> results of the recursive processing.
>
> Since this sounds a lot like homework, I won't post any specific code,
> though the text above should get you started; take a look at a basic
> lisp tutorial or Practical Common Lisp (available online) for more
> details.
>
> Alex
>
> On Feb 5, 5:24 pm, ············@gmail.com wrote:
>
> > Hey everybody!
>
> > Can anybody explain me how to construct a Lisp function, which will
> > remove (without modifying the list) 1) the first occurrence of a given
> > element from a flat list, 2) all such occurences from the list. We
> > assume that if the element is not in the list, the original list will
> > be returned.
>
> > At least tell me, please, which constructs should I use to build such
> > a function.
>
> > I am just beginning to study Lisp, so any advice regarding such
> > constructs would be really helpful.
>
> > Thanks.
> > Arsen
From: Maciej Katafiasz
Subject: Re: Remove the occurences of a given element from a list.
Date:
Message-ID: <fobbqn$n8n$1@news.net.uni-c.dk>
Den Tue, 05 Feb 2008 19:38:50 -0800 skrev arsen.bagyan:
> But what you are talking about is a removing of all occurences of an
> element!
> Or I am wrong?!
Look up the :count keyword argument to REMOVE, which Alex used in his
suggestion.
> There is no need for the specific code. Please just clearify this point.
> And what do you mean when you say recurse on the cdr of the list?
Lists are defined to have structure of (head . rest) ("." stands for
dotted pair notation, it expresses a cons cell, you could get one by
calling (cons head rest)). The two opposite operations are CAR and CDR:
(car (cons head rest)) ==> head
(cdr (cons head rest)) ==> rest
You basically have two cases:
1) HEAD is the element you're looking to have removed, so the desired
result is REST.
2) HEAD is not what you're looking for, so the desired result is (head .
rest-with-elem-removed). And how do you get REST-WITH-ELEM-REMOVED? Well,
you happen to be defining a function which does just that, removes an
element from a list, ain't ya? So why not call it with REST and cons its
result up with the HEAD? That's exactly the recursion on CDR part.
Hope that clears things up, now you just need to express that in code.
Cheers,
Maciej
Great thanks!!!
I got the idea!!!
Arsen
On 5 ÆÅ×, 22:07, Maciej Katafiasz <········@gmail.com> wrote:
> Den Tue, 05 Feb 2008 19:38:50 -0800 skrev arsen.bagyan:
>
> > But what you are talking about is a removing of all occurences of an
> > element!
> > Or I am wrong?!
>
> Look up the :count keyword argument to REMOVE, which Alex used in his
> suggestion.
>
> > There is no need for the specific code. Please just clearify this point.
> > And what do you mean when you say recurse on the cdr of the list?
>
> Lists are defined to have structure of (head . rest) ("." stands for
> dotted pair notation, it expresses a cons cell, you could get one by
> calling (cons head rest)). The two opposite operations are CAR and CDR:
>
> (car (cons head rest)) ==> head
> (cdr (cons head rest)) ==> rest
>
> You basically have two cases:
>
> 1) HEAD is the element you're looking to have removed, so the desired
> result is REST.
> 2) HEAD is not what you're looking for, so the desired result is (head .
> rest-with-elem-removed). And how do you get REST-WITH-ELEM-REMOVED? Well,
> you happen to be defining a function which does just that, removes an
> element from a list, ain't ya? So why not call it with REST and cons its
> result up with the HEAD? That's exactly the recursion on CDR part.
>
> Hope that clears things up, now you just need to express that in code.
>
> Cheers,
> Maciej
And here what I did when we need to remove all the occurences of a
certain symbol:
(defun remvall (obj lst)
(if (null lst)
nil
(remove obj lst)))
But I also need to write this as an iterative function, using either
the function do or dolist.
Can you suggest me anything?
Thanks,
Arsen
On 5 фев, 23:44, ············@gmail.com wrote:
> Great thanks!!!
> I got the idea!!!
> Arsen
>
> On 5 ÆÅ×, 22:07, Maciej Katafiasz <········@gmail.com> wrote:
>
> > Den Tue, 05 Feb 2008 19:38:50 -0800 skrev arsen.bagyan:
>
> > > But what you are talking about is a removing of all occurences of an
> > > element!
> > > Or I am wrong?!
>
> > Look up the :count keyword argument to REMOVE, which Alex used in his
> > suggestion.
>
> > > There is no need for the specific code. Please just clearify this point.
> > > And what do you mean when you say recurse on the cdr of the list?
>
> > Lists are defined to have structure of (head . rest) ("." stands for
> > dotted pair notation, it expresses a cons cell, you could get one by
> > calling (cons head rest)). The two opposite operations are CAR and CDR:
>
> > (car (cons head rest)) ==> head
> > (cdr (cons head rest)) ==> rest
>
> > You basically have two cases:
>
> > 1) HEAD is the element you're looking to have removed, so the desired
> > result is REST.
> > 2) HEAD is not what you're looking for, so the desired result is (head .
> > rest-with-elem-removed). And how do you get REST-WITH-ELEM-REMOVED? Well,
> > you happen to be defining a function which does just that, removes an
> > element from a list, ain't ya? So why not call it with REST and cons its
> > result up with the HEAD? That's exactly the recursion on CDR part.
>
> > Hope that clears things up, now you just need to express that in code.
>
> > Cheers,
> > Maciej
In article
<····································@d70g2000hsb.googlegroups.com>,
············@gmail.com wrote:
> And here what I did when we need to remove all the occurences of a
> certain symbol:
> (defun remvall (obj lst)
> (if (null lst)
> nil
> (remove obj lst)))
Why the NULL check? Do you think REMOVE doesn't work with an empty list?
>
> But I also need to write this as an iterative function, using either
> the function do or dolist.
> Can you suggest me anything?
Use DOLIST to iterate over the elements. If it doesn't match OBJ, add
the element to the result list, and at the end return the result.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Barry:
First, yes, remove works well with an empty list. I just didn't know
that.
Second, why the following does not work? (Remove all occurences!)
(defun remvall (obj lst)
(dolist (obj lst)
(if (eql (car lst) obj)
(cdr lst)
(remval (obj (cdr(lst)))))))
············@gmail.com writes:
> Barry:
>
> First, yes, remove works well with an empty list. I just didn't know
> that.
> Second, why the following does not work? (Remove all occurences!)
>
> (defun remvall (obj lst)
> (dolist (obj lst)
> (if (eql (car lst) obj)
> (cdr lst)
> (remval (obj (cdr(lst)))))))
It doesn't work because you are mixing recursion and iteration randomly.
The prototypal recursive processing of a chain of cons cells (a list) would be:
(defun recursive-function (cons-chain)
(if (null cons-chain)
(base-result)
(build-result-from (car cons-chain) (recursive-function (cdr cons-chain)))))
Now, if you want to process proper lists, you would rather use endp, first and rest:
(defun recursive-function (list)
(if (endp list)
(base-result) ; (eq list nil) here.
(build-result-from (first list) (recursive-function (rest list)))))
And of course, in the case of a list, it could be better to write an
iterative function, since tail call optimization is not mandatory in
CL implementations, and not often possible in presence of niceties
like dynamic binding.
(defun iterative-function (list)
(mapcar (function build-new-item-from-old-item) list))
(defun iterative-function (list)
(maplist (function build-new-item-from-old-item-and-following) list))
(defun iterative-function (list)
(reduce (function build-new-result-from-old-result-and-item) list))
If you want to use dolist, you have to explicitely gather the result you want:
(defun iterative-function (list)
(let ((result '()))
(dolist (item list (nreverse result))
(push (build-new-item-from-old-item item) result))))
(defun iterative-function (list)
(let ((result (base-result)))
(dolist (item list result)
(setf result (build-new-result-from-old-result-and-item result item)))))
The really sophisticated Common Lisp programmer would use LOOP:
(defun iterative-function (list)
(loop
:for item :in list
:collect (build-new-item-from-old-item item)))
(defun iterative-function (list)
(loop
:for items :on list
:collect (build-new-item-from-old-item-and-following items)))
(defun iterative-function (list)
(loop
:for result = (base-result) :then (build-new-result-from-old-result-and-item result item)
:for item :in list
:finally (return result)))
--
__Pascal Bourguignon__
From: Thomas A. Russ
Subject: Re: Remove the occurences of a given element from a list.
Date:
Message-ID: <ymisl05269d.fsf@blackcat.isi.edu>
············@gmail.com writes:
> Barry:
>
> First, yes, remove works well with an empty list. I just didn't know
> that.
> Second, why the following does not work? (Remove all occurences!)
>
> (defun remvall (obj lst)
> (dolist (obj lst)
> (if (eql (car lst) obj)
> (cdr lst)
> (remval (obj (cdr(lst)))))))
Well, for starters, consider what sort of error messages you get. What
happens when you run this?
Secondly, one might wonder why an iterative solution includes a
recursive call.
In general, since it seems clear this is a homework assignment, or at
the very least an autodidactic exercise:
Consider the different characteristics of recursive versus iterative
functions:
o In a recursive function, you find one small part of the problem to
handle, and then call the function again on a simplified (because
you've already handled part of the problem) part of the original
problem.
Hint: When using Lisp lists this usually means you do something
with the FIRST element and then process the REST.
o In an iterative function, you go through a (usually) linear data
structure and process each element in turn, deciding what to do with
it. Iterative solutions often need some additional storage that they
use to accumulate any results.
Hint: Pay attention to the order in which things get accumulated.
--
Thomas A. Russ, USC/Information Sciences Institute
Thanks a lot to everybody who posted reply to my messages!!!
I appreciate this! That really helps!
Will consider all your hints!
Now I have better idea about what Lisp really is :)
By the way, as you already noticed, my code where an iterative
solution includes a recursive call, is a really stupid thing! :) Will
try to avoid such stupid mistakes! :)
············@gmail.com writes:
> Thanks a lot to everybody who posted reply to my messages!!!
> I appreciate this! That really helps!
> Will consider all your hints!
> Now I have better idea about what Lisp really is :)
> By the way, as you already noticed, my code where an iterative
> solution includes a recursive call, is a really stupid thing! :) Will
> try to avoid such stupid mistakes! :)
This is not necessarily a stupid thing. What is stupid, is to try to
combine forms _randomly_, without implementing entirely a genetic
programming algorithm.
Here is for example, a function that is both iterative and
recursive. but not stupid (even if it could be written better with
LOOP):
(defun find-depths (target list)
"Returns a list of depths where occurences of TARGET are found in LIST"
(let ((results '()))
(dolist (item list (nreverse (mapcar (function 1+) results)))
(cond
((eql target item)
(push 0 results))
((listp item)
(setf results (nreconc (find-depths target item) results)))))))
C/USER[139]> (find-depths 'a '(a a ((a b (c a d))) a))
(1 1 3 4 1)
C/USER[140]> (find-depths 'a '(a (((a)))))
(1 4)
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Logiciels libres : nourris au code source sans farine animale."
From: Maciej Katafiasz
Subject: Re: Remove the occurences of a given element from a list.
Date:
Message-ID: <foclj5$n8n$3@news.net.uni-c.dk>
Den Tue, 05 Feb 2008 21:48:59 -0800 skrev arsen.bagyan:
> And here what I did when we need to remove all the occurences of a
> certain symbol:
> (defun remvall (obj lst)
> (if (null lst)
> nil
> (remove obj lst)))
1) REMOVE works just fine with NIL
2) REMVALL, LST and to a lesser extent OBJ are bad names. CL is neither C
nor Scheme, we have the luxury of being able to use full, descriptive
names. So REMOVE-ALL, OBJECT and LIST. Don't worry about clashes with the
function LIST, as CL is a Lisp-2 they live in separate namespaces
3) You're using non-customary indentation. CL has well-defined
indentation style, and following it is heavily recommended. The best
would be to use an editor that keeps proper indentation for you, like
Emacs.
4) (if (not something)
nil
something-else)
is a common idiom that has its own form, WHEN. Also, NULL in
(if (null list)) is redundant in CL, as an empty list is already equal to
NIL. So, combining that and 3) above, you get:
(when list
(remove obj lst))
But again, remeber about 1)
> But I also need to write this as an iterative function, using either the
> function do or dolist.
> Can you suggest me something?
I can suggest reading up on their syntax and semantics :). For example
using Peter Seibel's excellent book, Practical Common Lisp
(http://gigamonkeys.com/book/). Also, referring to DO and DOLIST as
"functions" is unfortunate, they're special forms with their own
evaluation semantics which are very much incompatible with what ordinary
functions do. Keeping the terminology straight here will help you avoid
confusion and miscommunication in the future.
Cheers,
Maciej
That is what I did for the case of removing only the first occurence:
(defun remv (obj lst)
(if (null lst)
nil
(if (eql (car lst) obj)
(cdr lst)
(cons (car lst) (remv obj (cdr lst))))))
But have no idea how to make it possible to handle the case when there
is no such an element in a list at all!
How to do this? Please advice!
············@gmail.com writes:
> That is what I did for the case of removing only the first occurence:
>
> (defun remv (obj lst)
> (if (null lst)
> nil
> (if (eql (car lst) obj)
> (cdr lst)
> (cons (car lst) (remv obj (cdr lst))))))
>
> But have no idea how to make it possible to handle the case when there
> is no such an element in a list at all!
> How to do this? Please advice!
You already do:
C/USER1[80]> (remv 1 (list 2 3 4 5))
(2 3 4 5)
--
__Pascal Bourguignon__
From: Maciej Katafiasz
Subject: Re: Remove the occurences of a given element from a list.
Date:
Message-ID: <foce3c$n8n$2@news.net.uni-c.dk>
Den Tue, 05 Feb 2008 22:58:42 -0800 skrev arsen.bagyan:
> That is what I did for the case of removing only the first occurence:
>
> (defun remv (obj lst)
> (if (null lst)
> nil
> (if (eql (car lst) obj)
> (cdr lst)
> (cons (car lst) (remv obj (cdr lst))))))
>
> But have no idea how to make it possible to handle the case when there
> is no such an element in a list at all! How to do this? Please advice!
As Pascal said, you already do. I think you now need to spend some
quality time with:
1) Paper
2) Pencil
3) Your code and some example lists
Run your algorithm by hand, see how it behaves. Then pick another example
and try to predict how it'll behave without running through all the
elements first, only by applying the high-level idea of how your
algorithm works. Then run it (again, by hand) and check that your
prediction was accurate. Then confirm with REPL. You should get a feel
for how things work after a couple of iterations. But be careful to do it
on paper first, only then confirm at the REPL, otherwise there might
something you didn't quite get that obscures your understanding. It's
really worth it to invest time in making absolutely sure you have perfect
grasp of fundamental concepts such as recursive list processing[1], as
they come up again and again, so you really don't want to find yourself
misunderstanding them later on.
Cheers,
Maciej
[1] But mind you that recursing on lists is NOT the usual way to process
them in CL. Tail-call optimisations is not mandatory, and we have
stupidly powerful iteration primitives available (hi, ITERATE), which
makes recursive removal and friends a rather bad idea. But the recursive
processing itself crops up all the time in many problems that can be
conceptually reduced to a list or tree processing, and then the ability
to do it will benefit you.
On Feb 5, 8:24 pm, ············@gmail.com wrote:
> Hey everybody!
>
> Can anybody explain me how to construct a Lisp function, which will
> remove (without modifying the list) 1) the first occurrence of a given
> element from a flat list, 2) all such occurences from the list. We
> assume that if the element is not in the list, the original list will
> be returned.
>
> At least tell me, please, which constructs should I use to build such
> a function.
>
> I am just beginning to study Lisp, so any advice regarding such
> constructs would be really helpful.
>
> Thanks.
> Arsen
Much of the functionality is already in the language. You'd probably
find member[1] and remove[2] useful.
On Feb 5, 8:40 pm, Joshua Taylor <···········@gmail.com> wrote:
> On Feb 5, 8:24 pm, ············@gmail.com wrote:
>
>
>
> > Hey everybody!
>
> > Can anybody explain me how to construct a Lisp function, which will
> > remove (without modifying the list) 1) the first occurrence of a given
> > element from a flat list, 2) all such occurences from the list. We
> > assume that if the element is not in the list, the original list will
> > be returned.
>
> > At least tell me, please, which constructs should I use to build such
> > a function.
>
> > I am just beginning to study Lisp, so any advice regarding such
> > constructs would be really helpful.
>
> > Thanks.
> > Arsen
>
> Much of the functionality is already in the language. You'd probably
> find member[1] and remove[2] useful.
Missed my footnotes:
[1] http://www.lisp.org/HyperSpec/Body/fun_membercm__ember-if-not.html
[2] http://www.lisp.org/HyperSpec/Body/fun_removecm__elete-if-not.html
Thanks for the notes!
Arsen
On 5 ÆÅ×, 19:41, Joshua Taylor <···········@gmail.com> wrote:
> On Feb 5, 8:40 pm, Joshua Taylor <···········@gmail.com> wrote:
>
>
>
> > On Feb 5, 8:24 pm, ············@gmail.com wrote:
>
> > > Hey everybody!
>
> > > Can anybody explain me how to construct a Lisp function, which will
> > > remove (without modifying the list) 1) the first occurrence of a given
> > > element from a flat list, 2) all such occurences from the list. We
> > > assume that if the element is not in the list, the original list will
> > > be returned.
>
> > > At least tell me, please, which constructs should I use to build such
> > > a function.
>
> > > I am just beginning to study Lisp, so any advice regarding such
> > > constructs would be really helpful.
>
> > > Thanks.
> > > Arsen
>
> > Much of the functionality is already in the language. You'd probably
> > find member[1] and remove[2] useful.
>
> Missed my footnotes:
> [1]http://www.lisp.org/HyperSpec/Body/fun_membercm__ember-if-not.html
> [2]http://www.lisp.org/HyperSpec/Body/fun_removecm__elete-if-not.html