I am a beginner in lisp, I should do a program lisp that creates a
circular list. I have to then to introduce and to eliminate item in the
list according to the FIFO policy. Someone it can help me?
I thought:
(setf x(let ((l (list '(a b c))))
(setf (cdr l) l)
l))
to introduce and to eliminate item, I don't know.
Sorry for my English,
Thanks
On Thu, Sep 02, 2004 at 05:27:27PM +0200, capitux wrote:
> I am a beginner in lisp, I should do a program lisp that creates a
> circular list. I have to then to introduce and to eliminate item in the
> list according to the FIFO policy. Someone it can help me?
>
> I thought:
>
> (setf x(let ((l (list '(a b c))))
> (setf (cdr l) l)
> l))
For a circular list, you want to set the CDR of the LAST cons to the
beginning of the list.
(setf *print-circle* t) ; toggle printing of circular structures
(let ((list (copy-list '(a b c))))
(setf (cdr (last list)) list))
==> #1=(A B C . #1#)
Three additional notes:
(1) You are not supposed to modify literal lists created by
forms such as '(a b c). I used COPY-LIST to create a fresh copy
which is safe to modify.
(2) What is X? You SETF X to something, but you didn't define it
beforehand. Do not use SETF or SETQ to introduce new variables,
use LET, LAMBDA, DEFUN, DEFVAR, DEFPARAMETER, etc...
(3) (setf x y) returns y, so you don't need to do it explicitly.
--
;;;; Matthew Danish -- user: mrd domain: cmu.edu
;;;; OpenPGP public key: C24B6010 on keyring.debian.org
Matthew Danish <·······@andrew.cmu.edu> writes:
> On Thu, Sep 02, 2004 at 05:27:27PM +0200, capitux wrote:
> > I am a beginner in lisp, I should do a program lisp that creates a
> > circular list. I have to then to introduce and to eliminate item in the
> > list according to the FIFO policy. Someone it can help me?
> >
> > I thought:
> >
> > (setf x(let ((l (list '(a b c))))
> > (setf (cdr l) l)
> > l))
>
> For a circular list, you want to set the CDR of the LAST cons to the
> beginning of the list.
>
> (setf *print-circle* t) ; toggle printing of circular structures
>
> (let ((list (copy-list '(a b c))))
> (setf (cdr (last list)) list))
>
> ==> #1=(A B C . #1#)
(defun clist-forward (clist)
(when clist (cdr clist)))
(defun clist-backward (clist)
(when clist (do ((prev clist (cdr prev)))
((eq (cdr prev) clist) prev))))
(defun clist-delete (clist)
(cond
((null clist) clist)
((eq clist (cdr clist)) nil)
(t (let ((result (clist-backward clist)))
(setf (cdr result) (cddr result))))))
(defun clist-insert (clist item)
(if clist
(setf (cdr clist) (cons item (cdr clist)))
(setf clist (cons item nil)
(cdr clist) clist)))
CL-USER> (defparameter x (clist-insert nil :a))
X
CL-USER> x
#1=(:A . #1#)
CL-USER> (clist-insert x :b)
#1=(:B :A . #1#)
CL-USER> (clist-insert x :c)
#1=(:C :B :A . #1#)
CL-USER> (clist-insert x :d)
#1=(:D :C :B :A . #1#)
CL-USER> x
#1=(:A :D :C :B . #1#)
CL-USER> (setf x (clist-forward x))
#1=(:D :C :B :A . #1#)
CL-USER> (setf x (clist-forward x))
#1=(:C :B :A :D . #1#)
CL-USER> (setf x (clist-forward x))
#1=(:B :A :D :C . #1#)
CL-USER> (setf x (clist-delete x))
#1=(:A :D :C . #1#)
CL-USER> (setf x (clist-insert x :bb))
#1=(:BB :D :C :A . #1#)
CL-USER> x
#1=(:BB :D :C :A . #1#)
CL-USER> (setf x (clist-backward x))
#1=(:A :BB :D :C . #1#)
CL-USER> (setf x (clist-backward x))
#1=(:C :A :BB :D . #1#)
CL-USER> (setf x (clist-backward x))
#1=(:D :C :A :BB . #1#)
CL-USER> (setf x (clist-backward x))
#1=(:BB :D :C :A . #1#)
CL-USER> (setf x (clist-delete x))
#1=(:D :C :A . #1#)
CL-USER> (setf x (clist-delete x))
#1=(:C :A . #1#)
CL-USER> (setf x (clist-delete x))
#1=(:A . #1#)
CL-USER> (setf x (clist-delete x))
NIL
CL-USER>
> Three additional notes:
>
> (1) You are not supposed to modify literal lists created by
> forms such as '(a b c). I used COPY-LIST to create a fresh copy
> which is safe to modify.
>
> (2) What is X? You SETF X to something, but you didn't define it
> beforehand. Do not use SETF or SETQ to introduce new variables,
> use LET, LAMBDA, DEFUN, DEFVAR, DEFPARAMETER, etc...
>
> (3) (setf x y) returns y, so you don't need to do it explicitly.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
capitux <·······@tiscali.it> writes:
>
> I am a beginner in lisp, I should do a program lisp that creates a
> circular list. I have to then to introduce and to eliminate item in the
> list according to the FIFO policy. Someone it can help me?
It isn't at all clear to me what a FIFO policy would mean for a list
that is circular. With a circular list you, by definition, have no
beginning or end of the list, so where do you decide the place in the
list to add or remove items?
I'm wondering if there is some terminologic confusion in your problem
statement and that instead of a circular list, you really mean something
like a queue -- for which FIFO makes a lot of sense.
Generally one builds circular lists when there isn't a desire to ever
exhaust the list. One cute example is keeping track of the next day of
the week. You just keep moving down the list and getting the next day.
--
Thomas A. Russ, USC/Information Sciences Institute
Thomas A. Russ <···@sevak.isi.edu> wrote:
+---------------
| capitux <·······@tiscali.it> writes:
| > I am a beginner in lisp, I should do a program lisp that creates a
| > circular list. I have to then to introduce and to eliminate item in the
| > list according to the FIFO policy. Someone it can help me?
|
| It isn't at all clear to me what a FIFO policy would mean for a list
| that is circular. With a circular list you, by definition, have no
| beginning or end of the list, so where do you decide the place in the
| list to add or remove items?
|
| I'm wondering if there is some terminologic confusion in your problem
| statement and that instead of a circular list, you really mean something
| like a queue -- for which FIFO makes a lot of sense.
+---------------
Actually, there *is* a well-known (I'm almost tempted to say "ancient"!)
algorithm for implementing the storage for a FIFO as a circular list
with only one "pointer" into it. [IIRC, it's in Knuth's "AoCP" vol.1,
ch.2: "Data Structures".]
Homework spoiler hint for the OP: The value of the FIFO "object" should
be the cons which is the *last* item in the FIFO, not the first. This
will permit the proper enqueue & dequeue operations to be implemented
in constant time with only one "pointer" into the circular list.
[Hopefully, Thomas will find the implications of this obvious,
while still leaving some work to do for the student's homework. ;-} ;-} ]
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
···@sevak.isi.edu (Thomas A. Russ) wrote:
> It isn't at all clear to me what a FIFO policy would mean for a list
> that is circular. With a circular list you, by definition, have no
> beginning or end of the list, so where do you decide the place in the
> list to add or remove items?
there is a nice algorithm, like Rob described and I've done already
in this thread (reinventing the algorithm, because I didn't know it,
but it is really simple)
http://groups.google.de/groups?selm=ch83h4%24117%241%40newsreader2.netcologne.de
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
> I am a beginner in lisp, I should do a program lisp that creates a
> circular list. I have to then to introduce and to eliminate item in the
> list according to the FIFO policy. Someone it can help me?
>
> I thought:
>
> (setf x(let ((l (list '(a b c))))
> (setf (cdr l) l)
> l))
>
> to introduce and to eliminate item, I don't know.
>
> Sorry for my English,
I think your instructor wants you to make a queue as
described in Chapter 12 Section 3 of Graham's ANSI Common
Lisp.
The best way to learn Lisp is to play at the REPL. Try
things out, see what they do. There are two problems.
First the REPL prints a list as (a b c), which looks nice
and symmetric, but Lisp's built-in lists are singly linked
and go left to right.
(a b c) is really (a . (b . (c . nil))) underneath
so you have to insert new items on the right, and discard
old items from the left.
Second, you need to see the way structure is being shared.
Let us put four items of data in our FIFO:
* (defvar fifo-data (list 'a 'b 'c 'd))
FIFO-DATA
Next grab hold of the last cons in the list:
* (defvar fifo-handle (last fifo-data))
FIFO-HANDLE
but we haven't turned on print-circle yet, so we cannot see
what we have done.
* (list fifo-data fifo-handle)
((A B C D) (D))
which isn't showing the shared structure and could have come
from (defvar fifo-handle (list 'd))
So we turn on print-circle
* (setf *print-circle* t)
T
* (list fifo-data fifo-handle)
((A B C . #1=(D)) #1#)
and now we can see that fifo-handle is pointing to the same
cons as the end of fifo-data.
This is not showing the cons cells. I've written a
routine that print lists as lots of dotted pairs. It is
fairly complicated because it needs a helper function to
detect the structure sharing. Don't try to understand the
code, just cut and paste it into your REPL so that your can
use it.
(defun dot-dupes (tree)
(let ((duplicates (spot-duplicates tree))
(tags '()))
(labels ((show-dots(branch)
(let ((tag (position branch duplicates)))
(cond
((and tag (member tag tags)) ; 2nd and subsequent
(format t "#~A#" tag))
(tag ; 1st time
(format t "#~A=" tag)
(push tag tags)
(initial-print branch))
('not-a-duplicate
(initial-print branch)))))
(initial-print(x)
(typecase x
(atom (format t "~s" x))
(cons (format t "( ")
(show-dots (car x))
(format t " . ")
(show-dots (cdr x))
(format t " )")))))
(show-dots tree))))
(defun spot-duplicates(x)
(let ((seen-once '())
(seen-again '()))
(labels
((explore(tree)
(if (member tree seen-once)
(pushnew tree seen-again)
(progn
(push tree seen-once)
(when (consp tree)
(explore (car tree))
(explore (cdr tree)))))))
(explore x)
seen-again)))
Now you can get more detail on the data structure:
* (dot-dupes (list fifo-data fifo-handle))
( ( A . ( B . ( C . #1=( D . #0=NIL ) ) ) ) . ( #1# . #0# ) )
If that is too much detail, back off and experiment.
* (dot-dupes '(a))
( A . NIL )
NIL
* (dot-dupes '(a b))
( A . ( B . NIL ) )
NIL
* (dot-dupes '(a b c))
( A . ( B . ( C . NIL ) ) )
I have written DOT-DUPES so that it shows up the fact that
the reader goes to the trouble of checking for symbols it
has seen before and stores them uniquely.
* (dot-dupes '(a a a))
( #0=A . ( #0# . ( #0# . NIL ) ) )
This doesn't happen with strings.
* (dot-dupes '("a" "a" "a"))
( "a" . ( "a" . ( "a" . NIL ) ) )
The built-in print routines don't make this point because
they are not merely teaching aids.
Play with this stuff, for example
* (dot-dupes (let ((s1 "a")(s2 "a"))
(list s1 s1 s2 s2 s1)))
( #1="a" . ( #1# . ( #0="a" . ( #0# . ( #1# . NIL ) ) ) ) )
or
* (dot-dupes (let ((temp (cons 'a 'b)))
(cons temp temp)))
( #0=( A . B ) . #0# )
Back to FIFO's
* (dot-dupes (cons fifo-data fifo-handle))
( ( A . ( B . ( C . #0=( D . NIL ) ) ) ) . #0# )
We can remove the old data easily enough.
* (pop fifo-data)
A
* (dot-dupes (cons fifo-data fifo-handle))
( ( B . ( C . #0=( D . NIL ) ) ) . #0# )
Adding new data requires more care. If we want to add E,
then (E . NIL) has to go in place of the NIL of (D . NIL).
We access it via fifo-handle
* (setf (cdr fifo-handle) (list 'e))
(E)
* (dot-dupes (cons fifo-data fifo-handle))
( ( B . ( C . #0=( D . ( E . NIL ) ) ) ) . #0# )
But the job is only half done. FIFO-HANDLE is pointing at
the last two cons of the fifo-data. We need to move it on.
* (setf fifo-handle (cdr fifo-handle))
(E)
* (dot-dupes (cons fifo-data fifo-handle))
( ( B . ( C . ( D . #0=( E . NIL ) ) ) ) . #0# )
That leaves you with lots of code to write for your
assignment, but I think you can see what it is supposed to
be doing, and you can use DOT-DUPES to look at the details
of your data structures.
Disclaimer: I'm not that hot a programmer. Don't take my
code for dot-dupes and spot-duplicates as gospel.
Alan Crowe
Edinburgh
Scotland