Could anyone help me to write the algorithm for this problem, write a
recursive function that remove all occurrences of the first elements of
the nested list.
Tri Tran <···········@netscape.net> writes:
> Could anyone help me to write the algorithm for this problem, write
> a recursive function that remove all occurrences of the first
> elements of the nested list.
What have you got so far?
-Peter
--
Peter Seibel ·····@javamonkey.com
The intellectual level needed for system design is in general
grossly underestimated. I am convinced more than ever that this
type of work is very difficult and that every effort to do it with
other than the best people is doomed to either failure or moderate
success at enormous expense. --Edsger Dijkstra
Tri Tran wrote:
> Could anyone help me to write the algorithm for this problem, write a
> recursive function that remove all occurrences of the first elements of
> the nested list.
>
That spec is a little fuzzy. If this is homework, type it in verbatim.
Include a brave attempt of your own to get the best help. The good news
is that if you do, you will get plenty of help.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Cells let us walk, talk, think, make love and realize
the bath water is cold." -- Lorraine Lee Cudmore
Tri Tran <···········@netscape.net> writes:
> Could anyone help me to write the algorithm for this problem, write a
> recursive function that remove all occurrences of the first elements
> of the nested list.
Is this homework?
marc
> Tri Tran <···········@netscape.net> writes:
>
> > Could anyone help me to write the algorithm for this
> > problem, write a recursive function that remove all
> > occurrences of the first elements of the nested list.
>
> Is this homework?
Yes it is but i just want to know how the algorithm work. I
am trying to do this but it seem doesn't work. here is my
code
(defun my-remove (L)
(cond((null L) 0 )
((eql (first L) (first (rest L))
(my-remove (first (rest L))
(t (cons (first L) (my-remove (first (rest L))))))
> marc
unknown writes:
> > Tri Tran <···········@netscape.net> writes:
> >
> > > Could anyone help me to write the algorithm for this
> > > problem, write a recursive function that remove all
> > > occurrences of the first elements of the nested list.
> >
> > Is this homework?
> Yes it is but i just want to know how the algorithm work. I
> am trying to do this but it seem doesn't work. here is my
> code
> (defun my-remove (L)
> (cond((null L) 0 )
> ((eql (first L) (first (rest L))
> (my-remove (first (rest L))
> (t (cons (first L) (my-remove (first (rest L))))))
Okay, for starters your life would be easier if you got an editor that
groks Lisp syntax a bit better. (Emacs or Vi or presumably any editor
that actually comes with a Lisp IDE.)
Because if you let a smart editor indent things, you'll probably see
that this code isn't doing what you think. Here's how your code
indents in emacs:
(defun my-remove (L)
(cond ((null L) 0 )
((eql (first L) (first (rest L))
(my-remove (first (rest L))
(t (cons (first L) (my-remove (first (rest L))))))
I assume that's not what you meant. Also, can you describe in a bit
more detail what your function is *supposed* to do--I'm not sure I
understand your original description.
Finally, 'L' is--stylistically speaking--a strange name lower case l
is bad because it can be easily confused with the numeral 1. I think
most folks would just use 'list'--after they went to all that trouble
to make Common Lisp a Lisp-2, might as well take advantage of it. (If
that last sentence didn't make any sense, don't worry about it. Just
name your variable 'list' and rest assured that you won't get any name
conflict with the function of the same name.)
-Peter
--
Peter Seibel ·····@javamonkey.com
The intellectual level needed for system design is in general
grossly underestimated. I am convinced more than ever that this
type of work is very difficult and that every effort to do it with
other than the best people is doomed to either failure or moderate
success at enormous expense. --Edsger Dijkstra
An original question is write a recursive function my-remove
(list) that remove all occurrences of the first elements of
a nested list.Example (my-remove '(a b c a (a b (e)) d))
---> (b c (b (e)) d)
I can only remove the first element of the top list but
cannot do the recursive way for the nested list. That's why
i am asking for a algorithm of this problem so that i
understand it clearly.
Thank you so much
> unknown writes:
>
> > > Tri Tran <···········@netscape.net> writes:
> > >
> > > > Could anyone help me to write the algorithm for this
> > > > problem, write a recursive function that remove all
> > > > occurrences of the first elements of the nested
> > list. >
> > > Is this homework?
> > Yes it is but i just want to know how the algorithm
> > work. I am trying to do this but it seem doesn't work.
> > here is my code
> > (defun my-remove (L)
> > (cond((null L) 0 )
> > ((eql (first L) (first (rest L))
> > (my-remove (first (rest L))
> > (t (cons (first L) (my-remove (first (rest L))))))
>
> Okay, for starters your life would be easier if you got an
> editor that groks Lisp syntax a bit better. (Emacs or Vi
> or presumably any editor that actually comes with a Lisp
> IDE.)
> Because if you let a smart editor indent things, you'll
> probably see that this code isn't doing what you think.
> Here's how your code indents in emacs:
>
> (defun my-remove (L)
> (cond ((null L) 0 )
> ((eql (first L) (first (rest L))
> (my-remove (first (rest L))
> (t (cons (first L) (my-remove
> (first (rest L))))))
> I assume that's not what you meant. Also, can you describe
> in a bit more detail what your function is *supposed* to
> do--I'm not sure I understand your original description.
>
> Finally, 'L' is--stylistically speaking--a strange name
> lower case l is bad because it can be easily confused with
> the numeral 1. I think most folks would just use
> 'list'--after they went to all that trouble to make Common
> Lisp a Lisp-2, might as well take advantage of it. (If
> that last sentence didn't make any sense, don't worry
> about it. Just name your variable 'list' and rest assured
> that you won't get any name conflict with the function of
> the same name.)
> -Peter
>
> --
> Peter Seibel
> ·····@javamonkey.com
> The intellectual level needed for system design is
> in general
> grossly underestimated. I am convinced more than ever
> that this
> type of work is very difficult and that every effort to
> do it with
> other than the best people is doomed to either failure
> or moderate
> success at enormous expense. --Edsger Dijkstra
unknown writes:
> An original question is write a recursive function my-remove
> (list) that remove all occurrences of the first elements of
> a nested list.Example (my-remove '(a b c a (a b (e)) d))
> ---> (b c (b (e)) d)
> I can only remove the first element of the top list but
> cannot do the recursive way for the nested list. That's why
> i am asking for a algorithm of this problem so that i
> understand it clearly.
Then my other post is not the right answer.
What happens when the item that is at the head of some
list is a list, for example
((a) b a (a))
should you get
(() b ())
or
( b a)
marc
ps it might be a good idea to post the problem as
it was issued to you or a url if possible.
marc
>
> Thank you so much
> > unknown writes:
> >
> > > > Tri Tran <···········@netscape.net> writes:
> > > >
> > > > > Could anyone help me to write the algorithm for this
> > > > > problem, write a recursive function that remove all
> > > > > occurrences of the first elements of the nested
> > > list. >
> > > > Is this homework?
> > > Yes it is but i just want to know how the algorithm
> > > work. I am trying to do this but it seem doesn't work.
> > > here is my code
> > > (defun my-remove (L)
> > > (cond((null L) 0 )
> > > ((eql (first L) (first (rest L))
> > > (my-remove (first (rest L))
> > > (t (cons (first L) (my-remove (first (rest L))))))
> >
> > Okay, for starters your life would be easier if you got an
> > editor that groks Lisp syntax a bit better. (Emacs or Vi
> > or presumably any editor that actually comes with a Lisp
> > IDE.)
> > Because if you let a smart editor indent things, you'll
> > probably see that this code isn't doing what you think.
> > Here's how your code indents in emacs:
> >
> > (defun my-remove (L)
> > (cond ((null L) 0 )
> > ((eql (first L) (first (rest L))
> > (my-remove (first (rest L))
> > (t (cons (first L) (my-remove
> > (first (rest L))))))
> > I assume that's not what you meant. Also, can you describe
> > in a bit more detail what your function is *supposed* to
> > do--I'm not sure I understand your original description.
> >
> > Finally, 'L' is--stylistically speaking--a strange name
> > lower case l is bad because it can be easily confused with
> > the numeral 1. I think most folks would just use
> > 'list'--after they went to all that trouble to make Common
> > Lisp a Lisp-2, might as well take advantage of it. (If
> > that last sentence didn't make any sense, don't worry
> > about it. Just name your variable 'list' and rest assured
> > that you won't get any name conflict with the function of
> > the same name.)
> > -Peter
> >
> > --
> > Peter Seibel
> > ·····@javamonkey.com
> > The intellectual level needed for system design is
> > in general
> > grossly underestimated. I am convinced more than ever
> > that this
> > type of work is very difficult and that every effort to
> > do it with
> > other than the best people is doomed to either failure
> > or moderate
> > success at enormous expense. --Edsger Dijkstra
unknown wrote:
> This is small part of the exercise so that i just post the
> problem that i didn't clear. Thank you so much and some
> question to clarify cause i am confusing about the recursive
> problem.
>
>>how to do it:
>>
>>Take the item you wish to check for and compair it to the
>>first element. If they are equal(eql will probably work
>>here also) then discard else save then process the rest
>>of the list
>>now on to nested lists
>
> 1. How can i check and compare if the first item is the one
> that i want to remove in list with all of it's occurrences.
> (delete all duplacate items)
Just so you know: there are functions called delete-duplicates and
remove-duplicates, but they do not do what you want.
How can you check if the first item is the one you want to remove? I
think you mean that as you recursively process /nested/ lists, the
first item of each nested list is /not/ "the one" to be removed. It
gets removed only if it is the same as "the one" to be removed. So the
problem is really "How do I know if this call is a top-level or nested
call." see below.
> 3. If i don't want to use any helper function is there any
> other ways to do this kind of question just using basic lisp
you or your instructor have painted you into a corner. this function
must be recursive, but the processing is not in fact recursive: it
must treat its list argument differently depending on whether the call
was nested or not. and the nested call needs to be told what to
delete, but the top-level call does not.
If my speculation so far is correct, you have defined the problem
well: how does remove-from-tree know if it has been called at the
top-level or recursively? Answer: just tell it:
(defun remove-from-tree (list top-level-p remove-this)
(if top-level-p
<special handling for top level call>
<handling for nested call>))
now you have an ugly call to make at the top-level:
(remove-from-tree '(a a (a b (c a d))) t 'does-not-apply)
That's half the solution. The second half you can try while filling in
the <handling> i left blank.
Extra credit: if "basic Lisp" includes &optional arguments you can
make this a lot simpler.
Apologies if this does not in fact address your actual question; I am
guessing quite a bit at that.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Cells let us walk, talk, think, make love and realize
the bath water is cold." -- Lorraine Lee Cudmore
* unknown wrote:
> An original question is write a recursive function my-remove
> (list) that remove all occurrences of the first elements of
> a nested list.Example (my-remove '(a b c a (a b (e)) d))
---> (b c (b (e)) d)
> I can only remove the first element of the top list but
> cannot do the recursive way for the nested list. That's why
> i am asking for a algorithm of this problem so that i
> understand it clearly.
I think the problem specification is ambiguous. Here are two possible
meanings:
Meaning 1:
my-remove of x is:
is x a list?
yes: let h be the head of x and t be the tail of it
loop for e on tail
unless e is equal to h collect my-remove of e;
no: return x.
Meaning 2:
my-remove of x is:
unless x is a list this is an error;
return my-remove-aux of the head of x and the tail of x.
my-remove-aux of r and x is:
is x a list?
yes: loop for e on x
unless e is equal to r
collect my-remove-aux of r and e;
no: return x.
--tim
> * unknown wrote:
> > An original question is write a recursive function
> > my-remove (list) that remove all occurrences of the
> > first elements of a nested list.Example (my-remove '(a b
> c a (a b (e)) d)) ---> (b c (b (e)) d)
> > I can only remove the first element of the top list but
> > cannot do the recursive way for the nested list. That's
> > why i am asking for a algorithm of this problem so that
> > i understand it clearly.
>
> I think the problem specification is ambiguous. Here are
> two possible meanings:
>
> Meaning 1:
>
> my-remove of x is:
> is x a list?
> yes: let h be the head of x and t be the tail of it
> loop for e on tail
> unless e is equal to h collect my-remove of e;
> no: return x.
>
> Meaning 2:
>
> my-remove of x is:
> unless x is a list this is an error;
> return my-remove-aux of the head of x and the tail of
> x.
> my-remove-aux of r and x is:
> is x a list?
> yes: loop for e on x
> unless e is equal to r
> collect my-remove-aux of r and e;
> no: return x.
Thank you for your advice Tim however your solution is look
like a iteration way not a recursive way and i am trying to
avoid using local variable and let, collect or other
built-in functions cause this is part of exercise and i can
only use basic lisp
>
> --tim
* unknown wrote:
> Thank you for your advice Tim however your solution is look
> like a iteration way not a recursive way and i am trying to
> avoid using local variable and let, collect or other
> built-in functions cause this is part of exercise and i can
> only use basic lisp
Complain to whoever is teaching you, because this is a stupid
restriction!
but if you want pure:
(defun my-remove (form)
;; Absurd `pure' version, takes the `remove things EQL to 1st elt from
;; every list' reading. Not tail recursive.
((lambda (o)
(funcall o o form))
(lambda (o l/a)
(if (consp l/a)
((lambda (i)
(funcall i i (first l/a) (rest l/a)))
(lambda (i e r)
(if (null r)
'()
(if (eql (first r) e)
(funcall i i e (rest r))
(cons (funcall o o (first r))
(funcall i i e (rest r)))))))
l/a))))
--tim
> * unknown wrote:
> > Thank you for your advice Tim however your solution is
> > look like a iteration way not a recursive way and i am
> > trying to avoid using local variable and let, collect or
> > other built-in functions cause this is part of exercise
> > and i can only use basic lisp
>
> Complain to whoever is teaching you, because this is a
> stupid restriction!
>
> but if you want pure:
>
> (defun my-remove (form)
> ;; Absurd `pure' version, takes the `remove things EQL
> to 1st elt from
> ;; every list' reading. Not tail recursive.
> ((lambda (o)
> (funcall o o form))
> (lambda (o l/a)
> (if (consp l/a)
> ((lambda (i)
> (funcall i i (first l/a) (rest l/a)))
> (lambda (i e r)
> (if (null r)
> '()
> (if (eql (first r) e)
> (funcall i i e (rest r))
> (cons (funcall o o (first r))
> (funcall i i e (rest r)))))))
> l/a))))
My apologies, i couldn't understand this solution, please
put more comments.Thank you
> --tim
unknown writes:
> > * unknown wrote:
> > > Thank you for your advice Tim however your solution is
> > > look like a iteration way not a recursive way and i am
> > > trying to avoid using local variable and let, collect or
> > > other built-in functions cause this is part of exercise
> > > and i can only use basic lisp
> >
> > Complain to whoever is teaching you, because this is a
> > stupid restriction!
> >
> > but if you want pure:
> >
> > (defun my-remove (form)
> > ;; Absurd `pure' version, takes the `remove things EQL
> > to 1st elt from
> > ;; every list' reading. Not tail recursive.
> > ((lambda (o)
> > (funcall o o form))
> > (lambda (o l/a)
> > (if (consp l/a)
> > ((lambda (i)
> > (funcall i i (first l/a) (rest l/a)))
> > (lambda (i e r)
> > (if (null r)
> > '()
> > (if (eql (first r) e)
> > (funcall i i e (rest r))
> > (cons (funcall o o (first r))
> > (funcall i i e (rest r)))))))
> > l/a))))
>
> My apologies, i couldn't understand this solution, please
> put more comments.Thank you
Don't worry about it too much. Tim wasn't kidding when he said in the
comment that thas is an "Absurd pure version". If you did, however,
bang your head against this you will probably have become one with the
lambda nature. For whatever *that's* worth.
Anyway, I'm not sure what you mean by "basic lisp". For instance LET
is pretty basic. If there are specific constraints on what parts of
the language you are allowed to use in the problem statement, you
should post them so we can help you within the (probably artificial)
constraints of your problem without resorting to code like Tim's. (Who
was--I'm pretty sure--joking, by the way.)
-Peter
--
Peter Seibel ·····@javamonkey.com
The intellectual level needed for system design is in general
grossly underestimated. I am convinced more than ever that this
type of work is very difficult and that every effort to do it with
other than the best people is doomed to either failure or moderate
success at enormous expense. --Edsger Dijkstra
Tim Bradshaw <···@cley.com> writes:
> * unknown wrote:
>
> > My apologies, i couldn't understand this solution, please
> > put more comments.Thank you
>
>
> Heh, I can even make it worse...
Tim! Stop frightening the nice Lisp student. Jeesh. ;-)
-Peter
--
Peter Seibel ·····@javamonkey.com
The intellectual level needed for system design is in general
grossly underestimated. I am convinced more than ever that this
type of work is very difficult and that every effort to do it with
other than the best people is doomed to either failure or moderate
success at enormous expense. --Edsger Dijkstra
* Peter Seibel wrote:
> Tim! Stop frightening the nice Lisp student. Jeesh. ;-)
Well, other than the fun of it, there was a mildly serious point: the
restrictions imposed (I presume) by the teacher are silly, in this
case and many others. So you can't use LET, well can you say:
((lambda (x) ...) y)
And how is this `better'? My code (the first version) demonstrates
that really it is not better. Does the student learn anything by this
`purity'?
I think that if the aim is to teach a course in, say, pure functional
programming, then it should be taught with a language which is
designed to support that style well, not CL. I live in Edinburgh so
I'd suggest Hope, but there are a google of these things (none with
more than 8 users).
I also kind of object to the fairly standard `silly recursive
algorithm' nature of the question. Sure, some people (mostly those
who use Hope I expect) probably thrive on these meaningless tasks, but
in general people like what they are doing to have some meaning. It's
not *hard* to find a task which teaches recursive programming but has
meaning. For instance:
Represent the directory structure of a filesystem as follows:
Directories are lists, the car of which is the name of the
directory (a string), and the cdr of which is a list of the
files and directories in the directory.
Files are strings, representing the name of the file.
There are some samples in xxxx.lisp
1. Write a program which finds all files (not directories) with a
given name, and returns a list of them.
2. Write a program which takes all files with a given name and
removes them from the structure. It should do this by making a
copy.
3. Write a program which finds the first file with a given name
and returns the path to it (specify how to give path...). It
should do the smallest amount of searching possible.
OK, I just typed this in and it could do with some improvement, but, I
mean, how hard can it be?
--tim
Tim Bradshaw <···@cley.com> writes:
> So you can't use LET, well can you say:
>
> ((lambda (x) ...) y)
>
> And how is this `better'?
Can't you see? It supports people who are standing on their head. :)
I was THRILLED when LET came along because I programmed with lambda
combinations routinely for a couple years before LET got standardized
and had started to notice (and be bugged by) the sense that all my
programs executed backwards. It was like when someone points out to
you a twitch that someone always does that you'd never noticed and
then you can never get it out of your mind and you notice it every
time they do it forever after...
The reason you want to do
(let ((x (this-happens-1st))) ; |
(let ((y (this-happens-2nd x))) ; | flow of execution
(let ((z (this-happens-3rd x y))) ; |
(this-happens-4th x y z)))) ; V
is so that you don't have to write:
((lambda (x)
((lambda (y)
((lambda (z)
(this-happens-4th x y z)) ; A
(this-happens-3rd x y))) ; |
(this-happens-2nd x))) ; | flow of execution
(this-happens-1st)) ; |
* Kent M Pitman wrote:
> Can't you see? It supports people who are standing on their head. :)
Yes. This is also like MAPx which tends to be sort-of backwards:
rather than saying
for each thing in ... do ..., ... and ...
you say
do ..., ... and ... for each thing in ...
--tim
Tim Bradshaw <···@cley.com> writes:
> * Kent M Pitman wrote:
>
> > Can't you see? It supports people who are standing on their head. :)
>
> Yes. This is also like MAPx which tends to be sort-of backwards:
For me, MAPx says: map this function over this (or these) lists.
> rather than saying
>
> for each thing in ... do ..., ... and ...
Looks like extended loop to me.
> you say
>
> do ..., ... and ... for each thing in ...
Haven't ever got the feeling I do it this way. Should be related to
person factor.
--
Janis Dzerins
If million people say a stupid thing, it's still a stupid thing.
* Janis Dzerins wrote:
> For me, MAPx says: map this function over this (or these) lists.
>> rather than saying
>>
>> for each thing in ... do ..., ... and ...
> Looks like extended loop to me.
The point is that there are two possible styles in this kind of
construct. One is operator, parameters then body and the other which
is operator, body, then parameters. MAPx is the second as is ((lambda
(x) ...) ...). Most other things are the first (DOLIST, LET,
WITH-OPEN-FILE &c &c).
--tim
Tim Bradshaw <···@cley.com> writes:
> * Peter Seibel wrote:
>
> > Tim! Stop frightening the nice Lisp student. Jeesh. ;-)
>
> Well, other than the fun of it, there was a mildly serious point:
> the restrictions imposed (I presume) by the teacher are silly, in
> this case and many others.
*I* got that that was your point. And I agree. But I suspect the OP
was probably still stressing about how to get their homework done and
might not get it. Which is *not* to say that I think you shouldn't
have posted it--I just figured I could do my bit to point out to the
OP (and any other newbie lurkers) that there *was* a joke, so they
don't get the wrong impression of Lisp. Namely, that it's a Scheme.
;-)
-Peter
--
Peter Seibel ·····@javamonkey.com
The intellectual level needed for system design is in general
grossly underestimated. I am convinced more than ever that this
type of work is very difficult and that every effort to do it with
other than the best people is doomed to either failure or moderate
success at enormous expense. --Edsger Dijkstra
* Coby Beck wrote:
> Tim, you should go back to sending the Black Helicopters, they are
> much more humane!
Unfortunately we don't have any available - they're all in Iraq
picking up debris from crashed alien spacecraft. (You didn't *really*
think this was about oil?)
--tim
unknown writes:
> > Tri Tran <···········@netscape.net> writes:
> >
> > > Could anyone help me to write the algorithm for this
> > > problem, write a recursive function that remove all
> > > occurrences of the first elements of the nested list.
> >
> > Is this homework?
> Yes it is but i just want to know how the algorithm work. I
> am trying to do this but it seem doesn't work. here is my
> code
> (defun my-remove (L)
> (cond((null L) 0 )
> ((eql (first L) (first (rest L))
> (my-remove (first (rest L))
> (t (cons (first L) (my-remove (first (rest L))))))
>
>
> > marc
Fair enough. In the future you should state that this is
homework right up front and what you did so far. Not only
will you get help sooner you will get better help about how
to figure it out rather then here it is.
Now on to the help:
your first mistake is that you need a wrapper function, to take the
input *and* your recursive engine function. The wrapper does all the
setup to remove special cases from the engine, something like this:
(defun wrapper (list)
" does setup work yada yada yada"
(engine (car list) (cdr list)))
now on to the engine:
Assumption: first element is an atom
so the first thing you need to do is come up with a function that will
work on a flat list(no nested lists)
(wrapper '( 1 2 3 1 2 3 1 2 3 4))
will return
(2 3 2 3 2 3 4)
how to do it:
Take the item you wish to check for and compair it to the
first element. If they are equal(eql will probably work here
also) then discard else save then process the rest of the list
now on to nested lists
(wrapper '(1 (1 2) 3 (2 (1 ))))
will return
((2) 3 ( 2 ()))
to do this add
if first element is a list pass it to engine with
item to check ...
the cons function, as you have found out is your friend. you should
not be returning 0 for your base case it is not going to work,
remember this is not C/C++ 0 is a number it is not a null pointer
address, I know it is also bad form to do this in C also. What you
want is nil to return at the end of your recursion
happy hacking
marc
ps did you realy want code to delete all duplacate items
or what you asked for? the sample code looks like an attempt
to remove all non unique items from a list
marc
This is small part of the exercise so that i just post the
problem that i didn't clear. Thank you so much and some
question to clarify cause i am confusing about the recursive
problem.
> how to do it:
>
> Take the item you wish to check for and compair it to the
> first element. If they are equal(eql will probably work
> here also) then discard else save then process the rest
> of the list
> now on to nested lists
1. How can i check and compare if the first item is the one
that i want to remove in list with all of it's occurrences.
(delete all duplacate items)
2. Assume i take the first element of the list as an input
so is it posible to compare it with the first elements of
the rest list
3. If i don't want to use any helper function is there any
other ways to do this kind of question just using basic lisp