From: ·················@unn.unisys.com
Subject: Remove duplicates in a string
Date:
Message-ID: <859906684.16511@dejanews.com>
Hello.
I'm an absolute beginner in Lisp. I have written a function that should
remove duplicates from a list, obviously without using "delete".
Unfortunately, it doesn't work.
(defun remove-dups (inlist)
(cond ((endp inlist) inlist)
(t (
(setf fi (first inlist))
(setf re (rest inlist))
(setf r2 (member fi re))
(setf lr2 (length r2))
(setf b1 (butlast inlist lr2))
(setf newlist (append b1 (rest r2)))
(remove-dups (newlist))
(remove-dups (rest newlist))
newlist))))
It is loaded normally, but, when I try to run it, it says that newlist
is not defined.
Any ideas?
Thanks and regards,
Giovanni
-------------------==== Posted via Deja News ====-----------------------
http://www.dejanews.com/ Search, Read, Post to Usenet
From: marisal
Subject: Re: Remove duplicates in a string
Date:
Message-ID: <33416784.3FFC@wrq.com>
·················@unn.unisys.com wrote:
>
> Hello.
> I'm an absolute beginner in Lisp. I have written a function that should
> remove duplicates from a list, obviously without using "delete".
> Unfortunately, it doesn't work.
>
> (defun remove-dups (inlist)
> (cond ((endp inlist) inlist)
> (t (
> (setf fi (first inlist))
> (setf re (rest inlist))
> (setf r2 (member fi re))
> (setf lr2 (length r2))
> (setf b1 (butlast inlist lr2))
> (setf newlist (append b1 (rest r2)))
> (remove-dups (newlist))
> (remove-dups (rest newlist))
> newlist))))
>
> It is loaded normally, but, when I try to run it, it says that newlist
> is not defined.
The offending line is:
> (remove-dups (newlist))
Since you have enclosed newlist within brackets, Lisp expects to find a
_function_ called newlist, instead of a variable. Simply remove the
brackets.
Now, if you want to write 'real Lisp', I'd suggest also the following:
o declare all needed variables locally (within a 'let'), i.e. NEVER use
global variables within a function.
o Use the functions most specific to your needs. For example, if you
have a 'cond' with only two options, use an 'if' instead.
o Simplify your recursive calls. For example, in your case, this would
suffice:
(defun remove-dups (inlist)
(if (endp inlist) inlist
(adjoin (car inlist) (remove-dups (rest inlist)))))
o Don't reinvent the wheel (unless you do it for the sake of learning).
Almost always there's a function in Lisp which will do the job (in this
case, remove-duplicates).
o If you get a listing as long as yours, suspect something is wrong.
Regards.
In article <···············@dejanews.com> ·················@unn.unisys.com writes:
> Hello.
> I'm an absolute beginner in Lisp. I have written a function that should
> remove duplicates from a list, obviously without using "delete".
> Unfortunately, it doesn't work.
>
> (defun remove-dups (inlist)
> (cond ((endp inlist) inlist)
> (t (
;; ^ This parenthesis and its mate should not be here.
> (setf fi (first inlist))
> (setf re (rest inlist))
> (setf r2 (member fi re))
> (setf lr2 (length r2))
> (setf b1 (butlast inlist lr2))
> (setf newlist (append b1 (rest r2)))
> (remove-dups (newlist))
;;; ^^^^^^^^^
> (remove-dups (rest newlist))
> newlist))))
>
> It is loaded normally, but, when I try to run it, it says that newlist
> is not defined.
Well, the reference to "(newlist)" is trying to use newlist as a
function, and since it isn't defined as a function you get the undefined
function error. If you change "(newlist)" to "newlist", though, you
will get an infinite recursion error. That is because you will keep
calling the remove duplicates function on the same argument whenever it
doesn't have any duplicates in it.
There are other problems as well, one of them fatal.
First off, the use of global variables and SETF is not general Lisp
coding style. The global variables are a bad idea. SETF is more of a
stylistic issue, and they aren't really necessary.
Second, there are some parts of the code that (apparently) rely on the
global variable to pass the information between recursive calls to this
function, since otherwise the return values are not used at all. This
is a very bad idea, since it makes the code much harder to understand.
I am talking about where the return value of remove-dups is never used.
Since the communication is done only through the global variable, the
top level call returns the last value set into "newlist", which will
typically be only a single element.
Once you have a function that is acceptable to your lisp system, you can
get some insight into what it is doing by tracing the functions member
and remove dups:
(trace member remove-dups)
[If you have an aggressively inlining and tail recursion eliminating
lisp (like Macintosh Common Lisp), you may need to evaluate the form
(declaim (optimize (speed 0) (debug 3)))
to be able to actually get trace output from the recursive calls to
remove-dups and the calls to member.]
You will need to rethink the algorithm a little bit.
You should write a function with three branches to the cond:
1: The input list is empty (You already have it)
2: The first element of the input list is duplicated.
3: The first element of the input list is not duplicated.
Part of this will involve constructing the returned list.
Once you get a working algorithm, you may be interested in trying to
improve its performance. The main key to improved performance is to
keep a separate argument that collects the duplicate-free list. All of
append, member, length and butlast are expensive operations. They take
time proportional to the length of the list that they process.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu