Lisp meisters,
I'm sure this question has been asked a thousand times,
I've searched the archives using Google but I couldn't
find the answer so please help me.
I'm trying to get each element of a list within a list within a list...
So after a few attempts I have done
this:
(defvar *linear*)
(setf *linear* '(PP (Spec right) (P' (P across) (NP the bridge))))
(defun traverse-list (list)
(if (null list)
nil
(if (listp (car list))
(traverse-list (car list))
(progn (format t "~a~%" (car list))
(traverse-list (cdr list))))))
What I want is something like:
PP
Spec
right
P'
P
across
NP
the
bridge
but when I run
CL-USER> (traverse-list *linear*)
PP
SPEC
RIGHT
NIL
CL-USER>
I tried to think it in natural language, something
along those lines:
if the list is not null
if the first element of the list is a list
repeat the function for the first element of the list
otherwise
print the first element
repeat the function for the rest of the list
It's 3 a.m. here in Istanbul, Turkey, and I just can't
think better so I hope you can teach me how to do that
traversing stuff.
For the curious: Actully my ultimate purpose is to
convert linear linguistic notation into DOT syntax (graphviz)
so that I can produce the those beautiful tree structure for
the parsing of sentences (just a small utility but it's going
to help a few linguists out there). That means that is just
the beginning of the stuff, but I keep other questions to
the remaining posts :)
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
>I'm trying to get each element of a list within a list within a list...
You may find the following function useful.
(defun flatten (my-list)
(cond ((null my-list) nil)
((atom my-list) (list my-list))
(t (append (flatten (first my-list))
(flatten (rest my-list))))))
Given this:
'(PP (Spec right) (P' (P across) (NP the bridge)))
It would give you this:
'(PP Spec right P' P across NP the bridge)
Of course, you also want it printed... but first things first ^^
"Eric Lavigne" <············@gmail.com> writes:
>>I'm trying to get each element of a list within a list within a list...
>
> You may find the following function useful.
>
> (defun flatten (my-list)
> (cond ((null my-list) nil)
> ((atom my-list) (list my-list))
> (t (append (flatten (first my-list))
> (flatten (rest my-list))))))
>
> Given this:
> '(PP (Spec right) (P' (P across) (NP the bridge)))
> It would give you this:
> '(PP Spec right P' P across NP the bridge)
>
> Of course, you also want it printed... but first things first ^^
Hmm, yes this gives a simpler structure that I can traverse
and print. But I think I'll need more than that because
having a flat structure I'm losing the hierarchical
relationships between the elements of the list so I
must store them somewhere before I flatten the list.
Why, because I need a transformation like that:
Given the linear linguistic notation:
(PP (Spec right) (P' (P across) (NP the bridge)))
(well actually brackets are used in linguistics but
I think I can take care of it after the main stuff)
I must be converting it to:
digraph L0 {
size = "8,8";
ordering=out;
node [shape = plaintext];
n0 [label="PP"];
n1 [label="Spec"];
n2 [label="P'";]
n3 [label="(right)"];
n4 [label="P"];
n5 [label="NP"];
n6 [label="across"];
n7 [label="the bridge"];
n0 -> {n1 n2};
n1 -> n3;
n2 -> {n4 n5};
n4 -> n6;
n5 -> n7;
}
As you see above, I need two things, get each element
of the list (kind of flattening process described above)
and then printing it according to the DOT language
telling the hierarchy (and then simply compiling it
to create graphical output).
Actually, in that linguistic notation I have
a constraint, namely, every first element of a
list can be thought of a "head" and every head can
have mostly 2 elements (which can be a single word,
an atom you may think or another list with a head
and two elements, on and on...). I'm trying to
figure out what kind of data-structure would suit
my needs best, or maybe I can handle all of these
with simple list processing, I'm just a little
bit confused.
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
>I'm trying to
>figure out what kind of data-structure would suit
>my needs best, or maybe I can handle all of these
>with simple list processing, I'm just a little
>bit confused.
A function has input and output. Don't worry so much about how it gets
from one to the other.
So, given the input you presented, we produced the desired output
(flattening the list and printing the result). If this doesn't solve
the problem, it's time to think of a new question. Maybe you have a
different idea of what should be printed? Perhaps you wish to print
pairs (item : parent) like this:
PP : nil
Spec : PP
right : Spec
P' : PP
P : P'
across : P
NP : P'
the : NP
bridge : NP
Anyway, if you don't know what you want yet then no function will meet
your needs.
"Eric Lavigne" <············@gmail.com> writes:
>>I'm trying to
>>figure out what kind of data-structure would suit
>>my needs best, or maybe I can handle all of these
>>with simple list processing, I'm just a little
>>bit confused.
>
> A function has input and output. Don't worry so much about how it gets
> from one to the other.
> So, given the input you presented, we produced the desired output
> (flattening the list and printing the result). If this doesn't solve
> the problem, it's time to think of a new question. Maybe you have a
> different idea of what should be printed? Perhaps you wish to print
> pairs (item : parent) like this:
>
> PP : nil
> Spec : PP
> right : Spec
> P' : PP
> P : P'
> across : P
> NP : P'
> the : NP
> bridge : NP
>
> Anyway, if you don't know what you want yet then no function will meet
> your needs.
I know what I want, now I'm trying to say what I want in the
language of Common Lisp.
What I want is, given such a structure (which is very similar
to what linguists use):
(PP (Spec right) (P* (P across) (NP the bridge)))
convert it to this kind of structure:
n0 [label="PP"];
n1 [label="Spec"];
n2 [label="P'";]
n3 [label="(right)"];
n4 [label="P"];
n5 [label="NP"];
n6 [label="across"];
n7 [label="the bridge"];
n0 -> {n1 n2};
n1 -> n3;
n2 -> {n4 n5};
n4 -> n6;
n5 -> n7;
So actually I can write it in natural language
as:
Give me the first element of the list it is n0
n0 is HEAD and it must have two elements (max.), n1 and n2
thus print n0 -> {n1 n2} (if it has only one element n1 then n0 -> n1;)
print a newline
repeat the processe recursively for n1 and n2 if they are also lists
(and by the way store what n0, n1, n2, ... holds as words or syntactic
categories)
Actually the example above is not the best one in terms
of linguistics, a better representation (according to X-bar theory of
Government and Binding theory of Chomskian tradition) would be
(PP (Spec right) (P* (P across) (NP (N* (Spec the) (N bridge)))))
The above structure, as you can see is compatible with what
I said, every HEAD (PP, Spec, P*, P, NP, N*, Spec, N) has
2 elements at most. And I'm trying to convert it into the
DOT language for graphviz program (in order to get the graphic
output of the described directed graph).
>
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
>Give me the first element of the list it is n0
> n0 is HEAD and it must have two elements (max.), n1 and n2
> thus print n0 -> {n1 n2} (if it has only one element n1 then n0 -> n1;)
> print a newline
> repeat the processe recursively for n1 and n2 if they are also lists
> (and by the way store what n0, n1, n2, ... holds as words or syntactic
> categories)
(defstruct node
label
element1
element2)
(defvar *nodes* (make-hash-table))
(setf (gethash *nodes* 0)
(make-node :label NIL :element1 1 :element2 2))
(setf (gethash *nodes* 1)
(make-node :label "Spec" :element1 3 :element2 NIL))
I recommend converting the list to a hashtable as above. It shouldn't
be very hard to come up with a function that converts your list of
lists into a hashtable. If you have a hashtable like this, creating
your "directed graph" should be easy.
One problem I see is node 7. I don't understand why "the bridge" is one
node rather than two separate nodes.
"Eric Lavigne" <············@gmail.com> writes:
>>Give me the first element of the list it is n0
>> n0 is HEAD and it must have two elements (max.), n1 and n2
>> thus print n0 -> {n1 n2} (if it has only one element n1 then n0 -> n1;)
>> print a newline
>> repeat the processe recursively for n1 and n2 if they are also lists
>> (and by the way store what n0, n1, n2, ... holds as words or syntactic
>> categories)
>
> (defstruct node
> label
> element1
> element2)
> (defvar *nodes* (make-hash-table))
> (setf (gethash *nodes* 0)
> (make-node :label NIL :element1 1 :element2 2))
> (setf (gethash *nodes* 1)
> (make-node :label "Spec" :element1 3 :element2 NIL))
>
> I recommend converting the list to a hashtable as above. It shouldn't
Thank you very much for the suggestion.
> be very hard to come up with a function that converts your list of
> lists into a hashtable. If you have a hashtable like this, creating
> your "directed graph" should be easy.
I guess so, I'll try to write such a function.
> One problem I see is node 7. I don't understand why "the bridge" is one
> node rather than two separate nodes.
You are right to feel uncomfortable with my example, it was
a little problematic :) Well, that was convention, I mean
a linguistic one. Normally for real formalism and X-bar
theory one must write it explicitly:
[NP [Spec the] [N' [N bridge]]]
but the example I was looking at in my linguisic book [1]
used shorter form for saving space and convenience. It
assumed the reader knew what the author meant.
So I think my utility must use some notation for that situation,
for example let "the bridge" interpreted as an atom,
or something similar.
1- Haegeman, L., "Introduction to Government and Binding Theory",
Blackwell Publishers
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
"Eric Lavigne" <············@gmail.com> schrieb im Newsbeitrag
·····························@g14g2000cwa.googlegroups.com...
> >I'm trying to get each element of a list within a list within a list...
>
> You may find the following function useful.
>
> (defun flatten (my-list)
> (cond ((null my-list) nil)
> ((atom my-list) (list my-list))
> (t (append (flatten (first my-list))
> (flatten (rest my-list))))))
> ...
If we talk about recursion in Lisp, I think it is good practise to use tail
recursion if easily possible. Thus I'd suggest using
(defun flatten (x)
(labels ((rec (x acc)
(cond ((null x) acc)
((atom x) (cons x acc))
(t (rec (car x) (rec (cdr x) acc))))))
(rec x nil)))
from Paul Graham's 'On Lisp'.
Rem: This is a tail recursive version of the above function. Although not
required by the standards, most Lisps resolve a tail recursion into an
iteration.
Andreas
>For the curious: Actully my ultimate purpose is to
>convert linear linguistic notation into DOT syntax (graphviz)
>so that I can produce the those beautiful tree structure for
>the parsing of sentences (just a small utility but it's going
>to help a few linguists out there). That means that is just
>the beginning of the stuff, but I keep other questions to
>the remaining posts :)
I highly recommend the book "Paradigms of Artificial Intelligence
Programming: Case Studies in Common Lisp," by Peter Norvig. Linguistics
is a recurring theme in this book, and he shows how to address various
linguistics issues in Lisp and Prolog. If you can't get a copy of the
book, you can at least take a look at some of his code examples
(downloadable source code). Here is the book's website:
http://www.norvig.com/paip.html
"Eric Lavigne" <············@gmail.com> writes:
>>For the curious: Actully my ultimate purpose is to
>>convert linear linguistic notation into DOT syntax (graphviz)
>>so that I can produce the those beautiful tree structure for
>>the parsing of sentences (just a small utility but it's going
>>to help a few linguists out there). That means that is just
>>the beginning of the stuff, but I keep other questions to
>>the remaining posts :)
>
> I highly recommend the book "Paradigms of Artificial Intelligence
> Programming: Case Studies in Common Lisp," by Peter Norvig. Linguistics
> is a recurring theme in this book, and he shows how to address various
> linguistics issues in Lisp and Prolog. If you can't get a copy of the
> book, you can at least take a look at some of his code examples
> (downloadable source code). Here is the book's website:
>
> http://www.norvig.com/paip.html
Thinking of Norvig and AI... I started to wonder if what I'm
trying to do is some kind of breadth-first traversal or what.
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Emre Sevinc <·····@bilgi.edu.tr> wrote
> I'm trying to get each element of a list within a list within a list...
(defvar *linear* '(PP (Spec right) (P1 (P across) (NP the
bridge))))
(defun traverse-list (list)
(dolist (elem list)
(if (listp elem)
(traverse-list elem)
(format t "~A~%" elem))))
Note: I changed your P' symbol to P1, since the reader misunderstands
the quote to read (P '(P across) ... (which is the cause of the
spurious QUOTE in your second listing.
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Lisp meisters,
>
> I'm sure this question has been asked a thousand times,
> I've searched the archives using Google but I couldn't
> find the answer so please help me.
>
> I'm trying to get each element of a list within a list within a list...
>
> So after a few attempts I have done
> this:
>
> (defvar *linear*)
> (setf *linear* '(PP (Spec right) (P' (P across) (NP the bridge))))
>
> (defun traverse-list (list)
> (if (null list)
> nil
> (if (listp (car list))
> (traverse-list (car list))
And what about (cdr list) when (car list) is a list?
> (progn (format t "~a~%" (car list))
> (traverse-list (cdr list))))))
Better use cond instead of (if ... (if ...)):
(defun traverse-list (list)
(cond
((null list) nil)
((atom list)
(do-something-with-atom list))
((listp (car list))
(do-something-with-list (car list))
(do-something-else-with-list (cdr list)))
(t
(do-something-with-atom (car list))
(do-something-else-with-list (cdr list)))))
--
__Pascal Bourguignon__ http://www.informatimago.com/
Wanna go outside.
Oh, no! Help! I got outside!
Let me back inside!
Pascal Bourguignon <···@informatimago.com> writes:
> Emre Sevinc <·····@bilgi.edu.tr> writes:
>
>> Lisp meisters,
>>
>> I'm sure this question has been asked a thousand times,
>> I've searched the archives using Google but I couldn't
>> find the answer so please help me.
>>
>> I'm trying to get each element of a list within a list within a list...
>>
>> So after a few attempts I have done
>> this:
>>
>> (defvar *linear*)
>> (setf *linear* '(PP (Spec right) (P' (P across) (NP the bridge))))
>>
>> (defun traverse-list (list)
>> (if (null list)
>> nil
>> (if (listp (car list))
>> (traverse-list (car list))
>
> And what about (cdr list) when (car list) is a list?
>
>> (progn (format t "~a~%" (car list))
>> (traverse-list (cdr list))))))
>
>
> Better use cond instead of (if ... (if ...)):
>
> (defun traverse-list (list)
> (cond
> ((null list) nil)
>
> ((atom list)
> (do-something-with-atom list))
>
> ((listp (car list))
> (do-something-with-list (car list))
> (do-something-else-with-list (cdr list)))
>
> (t
> (do-something-with-atom (car list))
> (do-something-else-with-list (cdr list)))))
Using your template I did the following:
(defun traverse-list (list)
(cond
((null list) nil)
((atom (car list))
(format t "~a~%" (car list))
(traverse-list (cdr list)))
((listp (car list))
(traverse-list (car list))
(traverse-list (cdr list)))
(t
(traverse-list (cdr list)))))
and making that P' into P* (thanks to other Lispers for
warning me) gave the desired result:
CL-USER> (traverse-list *linear*)
PP
SPEC
RIGHT
P*
P
ACROSS
NP
THE
BRIDGE
NIL
I also wanted to do it using "cond", thanks for that, too. Now
that I'm warming up recursive list processing
I can dive into what I really want to do. ;-)
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Using your template I did the following:
>
> (defun traverse-list (list)
> (cond
> ((null list) nil)
>
> ((atom (car list))
> (format t "~a~%" (car list))
> (traverse-list (cdr list)))
>
> ((listp (car list))
> (traverse-list (car list))
> (traverse-list (cdr list)))
>
> (t
> (traverse-list (cdr list)))))
Just a short note, but the "T" clause should never be reached. That is
because everything is either an ATOM or a CONS, so the second and third
clauses take care of all of the non-NULL list possibilities.
The case that is not handled is if the argument passed to TRAVERSE-LIST
is an atom other than NIL. In that case it will break, but that may not
be an issue for your program.
--
Thomas A. Russ, USC/Information Sciences Institute
···@sevak.isi.edu (Thomas A. Russ) writes:
> Emre Sevinc <·····@bilgi.edu.tr> writes:
>
>> Using your template I did the following:
>>
>> (defun traverse-list (list)
>> (cond
>> ((null list) nil)
>>
>> ((atom (car list))
>> (format t "~a~%" (car list))
>> (traverse-list (cdr list)))
>>
>> ((listp (car list))
>> (traverse-list (car list))
>> (traverse-list (cdr list)))
>>
>> (t
>> (traverse-list (cdr list)))))
>
> Just a short note, but the "T" clause should never be reached. That is
> because everything is either an ATOM or a CONS, so the second and third
> clauses take care of all of the non-NULL list possibilities.
>
> The case that is not handled is if the argument passed to TRAVERSE-LIST
> is an atom other than NIL. In that case it will break, but that may not
> be an issue for your program.
Actually, in my template it was (atom list), not (atom (car list)),
and the otherwise case was needed for (atom (car list)).
(defun traverse-list (list)
(cond
((null list) nil)
((atom list)
(do-something-with-atom list))
((listp (car list))
(do-something-with-list (car list))
(do-something-else-with-list (cdr list)))
(t
(do-something-with-atom (car list))
(do-something-else-with-list (cdr list)))))
That's the problem when you try to process inside the lists
needlessly, you have to test test both the list and the inside of the
list... Note however that one might want to do different things in
do-something-with-list and do-something-else-with-list, for example in
(sin x) vs. ((lambda (x) (* x x)) 2).
See my previous post for the normal way to traverse a pedestrian list.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Using your template I did the following:
>
> (defun traverse-list (list)
> (cond
> ((null list) nil)
>
> ((atom (car list))
> (format t "~a~%" (car list))
> (traverse-list (cdr list)))
>
> ((listp (car list))
> (traverse-list (car list))
> (traverse-list (cdr list)))
>
> (t
> (traverse-list (cdr list)))))
>
> and making that P' into P* (thanks to other Lispers for
> warning me) gave the desired result:
>
> CL-USER> (traverse-list *linear*)
> PP
> SPEC
> RIGHT
> P*
> P
> ACROSS
> NP
> THE
> BRIDGE
> NIL
>
> I also wanted to do it using "cond", thanks for that, too. Now
> that I'm warming up recursive list processing
> I can dive into what I really want to do. ;-)
Good.
Note that you can simplify the function:
(defun traverse-list (list)
(cond
((null list))
((atom list) (format t "~A~%" list))
(t (mapcar (function traverse-list) list))))
But now you're going to repeat the same thing again and again.
Better write a higher order function:
(defun traverse-list (list func)
(cond
((null list))
((atom list) (funcall func list))
(t (mapcar (lambda (item) (traverse-list item func)) list))))
So you can write:
(traverse-list *linear* (lambda (item) (format t "~A~%" item)))
(let ((count 0)) (traverse-list *linear* (lambda (item) (incf count))) count)
(traverse-list *linear* (lambda (item) (length (string item))))
Or even:
(defun traverse-list (list &key (before (function identity))
(process (function identity))
(after (function identity)))
(funcall before list)
(cond
((null list))
((atom list) (funcall process list))
(t (dolist (item list)
(traverse-list item :before before
:process process
:after after))))
(funcall after list))
So you can write:
[100]> (let ((indent 0))
(traverse-list (append *linear* *linear*)
:before (lambda (item) (when (consp item) (incf indent)))
:after (lambda (item) (when (consp item) (decf indent)))
:process (lambda (item)
(format t "~VA ~A~%" (* 2 indent) "" item))))
PP
SPEC
RIGHT
P*
P
ACROSS
NP
THE
BRIDGE
PP
SPEC
RIGHT
P*
P
ACROSS
NP
THE
BRIDGE
0
--
__Pascal Bourguignon__ http://www.informatimago.com/
I need a new toy.
Tail of black dog keeps good time.
Pounce! Good dog! Good dog!
Emre Sevinc <·····@bilgi.edu.tr> writes:
> (defun traverse-list (list)
> (if (null list)
> nil
> (if (listp (car list))
> (traverse-list (car list))
> (progn (format t "~a~%" (car list))
> (traverse-list (cdr list))))))
I'm not sure what you want to do. If you want to print all
atoms in a list and its nested lists, you to recurse on the CDR
in all cases (not only when the CAR is not a list):
(defun traverse-list (list)
(when list
(if (listp (car list))
(traverse-list (car list))
(format t "~a~%" (car list)))
(traverse-list (cdr list))))
Personally, I think DOLIST is more clear, here:
(defun traverse-list (list)
(dolist (l list)
(if (listp l)
(traverse-list l)
(format t "~a~%" l))))
--drkm
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Lisp meisters,
>
> I'm sure this question has been asked a thousand times,
> I've searched the archives using Google but I couldn't
> find the answer so please help me.
>
> I'm trying to get each element of a list within a list within a list...
>
> So after a few attempts I have done
> this:
>
> (defvar *linear*)
> (setf *linear* '(PP (Spec right) (P' (P across) (NP the bridge))))
>
> (defun traverse-list (list)
> (if (null list)
> nil
> (if (listp (car list))
> (traverse-list (car list))
> (progn (format t "~a~%" (car list))
> (traverse-list (cdr list))))))
>
And now, when I modify traverse-list like that:
(defun traverse-list (list)
(if (null list)
nil
(if (listp (car list))
(traverse-list (car list))
(progn (format t "~a~%" (car list))
(traverse-list (cdr list))
(traverse-list (cddr list))))))
I still get strange results, not what I want:
CL-USER> (traverse-list *linear*)
PP
SPEC
RIGHT
P
QUOTE
P
ACROSS
NP
THE
BRIDGE
BRIDGE
NIL
I'm still confused. Any tips or help are going
to be appreciated.
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
>I still get strange results, not what I want:
>
>CL-USER> (traverse-list *linear*)
>PP
>SPEC
>RIGHT
>P
>QUOTE
>P
>ACROSS
>NP
>THE
>BRIDGE
>BRIDGE
>NIL
>
>I'm still confused. Any tips or help are going
>to be appreciated.
These functions should do what you want. I haven't tested them, though.
I notice that P QUOTE appeared in your results instead of P'. I think
you need to put P' in quotes like this: "P'" to protect it from
evaluation. Lisp sees P' as two atoms: P and QUOTE. This is a problem
with the original list, not the function.
(defun traverse-list (list)
(dolist (i (flatten list))
(format t "~A " i)))
(defun flatten (my-list)
(cond ((null my-list) nil)
((atom my-list) (list my-list))
(t (append (flatten (first my-list))
(flatten (rest my-list))))))
Emre Sevinc wrote:
>
> I still get strange results, not what I want:
>
> CL-USER> (traverse-list *linear*)
> PP
> SPEC
> RIGHT
> P
> QUOTE
> P
> ACROSS
> NP
> THE
> BRIDGE
> BRIDGE
> NIL
>
>
Simply ' is short for QUOTE.
You can escape the ' in P' with a \ like so...
(defvar *linear* '(PP (Spec right) (P\' (P across) (NP the bridge))))
(defun print-atoms (list)
(map nil (lambda (element)
(etypecase element
(list (print-atoms element))
(t (format t "~A~%" element))))
list))
CL-USER 6 > (print-atoms *linear*)
PP
SPEC
RIGHT
P'
P
ACROSS
NP
THE
BRIDGE
NIL
Wade
From: Emre Sevinc
Subject: Two Steps Forward One Step Back Re: Newbie list traversal
Date:
Message-ID: <87ekb5n0f9.fsf@ileriseviye.org>
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Lisp meisters,
>
On my way to converting to DOT (graphviz) notation.
First I get my list straight:
(defvar *linear*)
;; had to use P* instead of P' because ' is treated special
;; by the lisp reader
(setf *linear* '(PP (Spec right) (P* (P across) (NP (Spec the) (N* (N bridge))))))
And then try that:
(defun convert (list)
(if (null list)
nil
(if (atom (car list))
(format t "~A -> {" (car list))
(format t "~A -> {" (caar list))))
(if (null (cadr list))
nil
(if (atom (cadr list))
(format t "~A" (cadr list))
(format t "~A" (caadr list))))
(if (null (caddr list))
nil
(format t " ~A" (caaddr list)))
(format t "};~%")
(if (cadr (list))
(convert (cadr list))
nil)
(if (caddr list)
(convert (caddr list))
nil))
In order to say:
CL-USER> (convert *linear*)
PP -> {SPEC P*};
P* -> {P NP};
NP -> {SPEC N*};
N* -> {N};
NIL
Not exactly what I want, what I really need is something
like:
(PP (SPEC RIGHT) (P* (P ACROSS) (NP (SPEC THE) (N* (N BRIDGE)))))
PP -> {SPEC P*};
SPEC -> {RIGHT}; <--- Missing from the previous output
P* -> {P NP};
P -> {ACROSS}; <--- Missing from the previous output
NP -> {SPEC N*};
SPEC -> {THE}; <--- Missing from the previous output
N* -> {N};
N -> {BRIDGE}; <--- Missing from the previous output
NIL
What am I doing wrong? (I also tried to use cond but
it brings too much semantic confusion to my poor brain
during the early hours of the morning, using if was, I hope,
easier to read, write and understand)
If I can make that "convert" function do the above
I think it is going to be simple to convert PP, Spec, N*, N,
etc. into n0, n1, n2, n3, ... and make a simple string
replace in order to get the final DOT notation:
n0 [label="PP"];
n1 [label="Spec"];
n2 [label="P'"];
n3 [label="(right)"];
n4 [label="P"];
n5 [label="NP"];
n6 [label="across"];
n7 [label="the bridge"];
n0 -> {n1 n2};
n1 -> {n3};
n2 -> {n4 n5};
n4 -> {n6};
n5 -> {n7};
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Emre Sevinc <·····@bilgi.edu.tr> writes:
> What am I doing wrong? (I also tried to use cond but
> it brings too much semantic confusion to my poor brain
> during the early hours of the morning, using if was, I hope,
> easier to read, write and understand)
A DOT file describes a graph. You start from a list.
Why don't you build a graph from your list before generating the DOT
from the graph?
--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay
From: Emre Sevinc
Subject: Re: Two Steps Forward One Step Back Re: Newbie list traversal
Date:
Message-ID: <87vf4hseez.fsf@ileriseviye.org>
Pascal Bourguignon <···@informatimago.com> writes:
> Emre Sevinc <·····@bilgi.edu.tr> writes:
>> What am I doing wrong? (I also tried to use cond but
>> it brings too much semantic confusion to my poor brain
>> during the early hours of the morning, using if was, I hope,
>> easier to read, write and understand)
>
> A DOT file describes a graph. You start from a list.
>
> Why don't you build a graph from your list before generating the DOT
> from the graph?
I'm a little bit confused and didn't understand what you
mean exactly. My purpose is, given that linguistic
notation convert it into the corresponding DOT file.
I want to do that because after I produce the corresponding
DOT file, I can run the dot command on it (which comes
with the graphviz package) and get a .png or .ps
Can you explain what you exactly meant? I start
from a list because that's how linguists write
their parse trees when they don't have much
space:
[PP [Spec right] [P' [P ... ...]]]
And then the above structure can be drawn as
a tree diagram. As far as I know graphviz is good
for that but in order to draw that tree diagram
I must first convert it to DOT notation, put
it in a .dot file and run the dot command on it,
right?
Am I doing something wrong? Did I miss something?
What do you mean by saying "build a graph
firs from the list" BEFORE generating
the DOT from the graph?
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
From: Robert Uhl
Subject: Re: Two Steps Forward One Step Back Re: Newbie list traversal
Date:
Message-ID: <m3u0k178vb.fsf@4dv.net>
Emre Sevinc <·····@bilgi.edu.tr> writes:
>
> What do you mean by saying "build a graph firs from the list" BEFORE
> generating the DOT from the graph?
I imagine what he means is taking the list which you have and then
converted it into some kind of graph structure, then converting that
structure into DOT. The advantage is first that it might be more
straightforward to implement those two operations rather than one single
one, and second that each would be more general and thus more likely to
be useful to you in the future--e.g. it's easier to extend a graph
function that a graph+DOT function.
--
Robert Uhl <http://public.xdi.org/=ruhl>
A lady came up to me on the street and pointed at my suede jacket. `You
know a cow was murdered for that jacket?' she sneered.
I replied in a psychotic tone, `I didn't know there were any witnesses.
Now I'll have to kill you too.' --Jake Johansen
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Pascal Bourguignon <···@informatimago.com> writes:
>
>> Emre Sevinc <·····@bilgi.edu.tr> writes:
>>> What am I doing wrong? (I also tried to use cond but
>>> it brings too much semantic confusion to my poor brain
>>> during the early hours of the morning, using if was, I hope,
>>> easier to read, write and understand)
>>
>> A DOT file describes a graph. You start from a list.
>>
>> Why don't you build a graph from your list before generating the DOT
>> from the graph?
>
> I'm a little bit confused and didn't understand what you
> mean exactly.
If you've read the documentation of graphviz, you should know what a
graph is. It's a couple (N,E) where N is a set of nodes, and E is a
relation on N, that is, E is a subset of N�N.
Trees are a special kind of graph: they are acyclic graphs.
Now, since you start from CONSes, you have to define how you read a
tree from this heap of CONSes. There are several way to build trees
with CONSes.
For example if you consider just binary trees with the left child in
the CAR and the right child in the CDR, each CONS being a node:
(defun node-label (node)
"Return the label of the node"
node)
(defun node-children (node)
"Return the list of children to the node."
(when (consp node)
(list (car node) (cdr node))))
In you case, it looks like you're considering LISTs to be the nodes,
the first element being the label and the rest the children:
(defun node-label (node)
"Return the label of the node"
(if (consp node)
(first node)
node))
(defun node-children (node)
"Return the list of children to the node."
(when (consp node)
(cdr node)))
To take the example of your *linear* tree:
(setf *linear*
'(PP (Spec right) (P* (P across) (NP (Spec the) (N* (N bridge))))))
;; rot13'ed to protect the innocents.
(qrsha abqrf (gerr)
"
ERGHEA: Gur yvfg bs abqrf va gur gerr.
"
(apbap (yvfg (abqr-ynory gerr)) ; gur cnerag abqr
(zncpna (shapgvba abqrf) (abqr-puvyqera gerr))))
(qrsha rqtrf (gerr)
"
ERGHEA: Gur yvfg bs rqtrf va gur gerr.
"
(apbap (zncpne (ynzoqn (puvyq) (yvfg (abqr-ynory gerr) (abqr-ynory puvyq)))
(abqr-puvyqera gerr))
(zncpna (shapgvba rqtrf) (abqr-puvyqera gerr))))
(progn
(format t "~&N = { ~{~A~^,~% ~} }~2%" (nodes *linear*))
(format t "~&E = { ~:{( ~8A , ~A ),~% ~} }~2%" (edges *linear*)))
N = { PP,
SPEC,
RIGHT,
P*,
P,
ACROSS,
NP,
SPEC,
THE,
N*,
N,
BRIDGE }
E = { ( PP , SPEC ),
( PP , P* ),
( SPEC , RIGHT ),
( P* , P ),
( P* , NP ),
( P , ACROSS ),
( NP , SPEC ),
( NP , N* ),
( SPEC , THE ),
( N* , N ),
( N , BRIDGE ),
}
If you look closely, you'll notice that the DOT file can be written
directly from N and E. (Perhaps you'll want to add some calls to
node-label).
> Can you explain what you exactly meant? I start
> from a list because that's how linguists write
> their parse trees when they don't have much
> space:
>
> [PP [Spec right] [P' [P ... ...]]]
>
> And then the above structure can be drawn as
> a tree diagram. As far as I know graphviz is good
> for that but in order to draw that tree diagram
> I must first convert it to DOT notation, put
> it in a .dot file and run the dot command on it,
> right?
>
> Am I doing something wrong?
Yes, you're looking it too closely. Back off a little and abstract.
> Did I miss something?
- The input of graphviz is a graph (Nodes, Edges), so you must first
get a graph, not a DOT file. From a graph, you can generate
trivially the DOT file.
- A tree is a graph, so there's no difficulty in obtaining the nodes
and the edges once you have a tree.
- you start from a list representation of a tree, but you need to
explicit your representation. The same list can represent various
different trees:
(a (b c) (d e)) could represent:
T1 = ( N = { (A (B C) (D E)),
A,
(B C),
B,
C,
(D E),
D,
E }
E = { ( (A (B C) (D E)) , A ),
( (A (B C) (D E)) , (B C) ),
( (A (B C) (D E)) , (D E) ),
( (B C) , B ),
( (B C) , C ),
( (D E) , D ),
( (D E) , E ),
} )
or:
T2 = ( N = { (A (B C) (D E)),
A,
((B C) (D E)),
(B C),
B,
(C),
C,
NIL,
((D E)),
(D E),
D,
(E),
E,
NIL,
NIL }
E = { ( (A (B C) (D E)) , A ),
( (A (B C) (D E)) , ((B C) (D E)) ),
( ((B C) (D E)) , (B C) ),
( ((B C) (D E)) , ((D E)) ),
( (B C) , B ),
( (B C) , (C) ),
( (C) , C ),
( (C) , NIL ),
( ((D E)) , (D E) ),
( ((D E)) , NIL ),
( (D E) , D ),
( (D E) , (E) ),
( (E) , E ),
( (E) , NIL ),
} )
or:
T3 = ( N = { A,
B,
C,
D,
E }
E = { ( A , B ),
( A , D ),
( B , C ),
( D , E ),
} )
or:
etc...
http://en.wikipedia.org/wiki/Graph_theory
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
From: Emre Sevinc
Subject: Re: Two Steps Forward One Step Back Re: Newbie list traversal
Date:
Message-ID: <87psulbhh7.fsf@ileriseviye.org>
Pascal Bourguignon <···@informatimago.com> writes:
> Emre Sevinc <·····@bilgi.edu.tr> writes:
>> Pascal Bourguignon <···@informatimago.com> writes:
>>
>>> Emre Sevinc <·····@bilgi.edu.tr> writes:
>>>> What am I doing wrong? (I also tried to use cond but
>>>> it brings too much semantic confusion to my poor brain
>>>> during the early hours of the morning, using if was, I hope,
>>>> easier to read, write and understand)
>>>
>>> A DOT file describes a graph. You start from a list.
>>>
>>> Why don't you build a graph from your list before generating the DOT
>>> from the graph?
>>
>> I'm a little bit confused and didn't understand what you
>> mean exactly.
>
>
> If you've read the documentation of graphviz, you should know what a
> graph is. It's a couple (N,E) where N is a set of nodes, and E is a
> relation on N, that is, E is a subset of N�N.
>
> Trees are a special kind of graph: they are acyclic graphs.
First of all, thanks for detailed and lengthy explanations.
I know what a graph, acyclic graph, tree, etc. is however
I was confused when graph was compared to DOT file, since
I was interested not in the header (size, style, etc.) part
of the DOT file but the core part I was not able to understand
what you exactly referred to. It is much clear now
after your explanations.
>
>
> ;; rot13'ed to protect the innocents.
>
> (qrsha abqrf (gerr)
> "
> ERGHEA: Gur yvfg bs abqrf va gur gerr.
> "
> (apbap (yvfg (abqr-ynory gerr)) ; gur cnerag abqr
> (zncpna (shapgvba abqrf) (abqr-puvyqera gerr))))
>
> (qrsha rqtrf (gerr)
> "
> ERGHEA: Gur yvfg bs rqtrf va gur gerr.
> "
> (apbap (zncpne (ynzoqn (puvyq) (yvfg (abqr-ynory gerr) (abqr-ynory puvyq)))
> (abqr-puvyqera gerr))
> (zncpna (shapgvba rqtrf) (abqr-puvyqera gerr))))
Hmm, M-x rot13-other-window was helpful but maybe I must
implement my own rot13er in CL to sharpen my string processing
skills ;-)
And, again, thanks for the code.
> N*,
> N,
> BRIDGE }
>
> E = { ( PP , SPEC ),
> ( PP , P* ),
> ( SPEC , RIGHT ),
> ( P* , P ),
> ( P* , NP ),
> ( P , ACROSS ),
> ( NP , SPEC ),
> ( NP , N* ),
> ( SPEC , THE ),
> ( N* , N ),
> ( N , BRIDGE ),
> }
>
> If you look closely, you'll notice that the DOT file can be written
> directly from N and E. (Perhaps you'll want to add some calls to
> node-label).
Yes, exactly, once I have the above representation
it is much easier to produce a DOT file for graphviz.
With all those explanations and code samples (I need
to examine them a little bit to grasp the details)
I think I can start writing the utility I wished for.
I plan to make it both an executable (which depends
on graphviz's dot command) and a web application
which is going to produce downloadable .ps files.
Happy hacking,
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Hmm, M-x rot13-other-window was helpful
W r runs the command gnus-summary-caesar-message
Caesar rotate the current article by 13.
--
Johan Bockg�rd
Emre Sevinc <·····@bilgi.edu.tr> writes:
> ;; had to use P* instead of P' because ' is treated special
> ;; by the lisp reader
> (setf *linear* '(PP (Spec right) (P* (P across) (NP (Spec the) (N* (N bridge))))))
>
> n0 [label="PP"];
> n1 [label="Spec"];
> n2 [label="P'"];
> n3 [label="(right)"];
> n4 [label="P"];
> n5 [label="NP"];
> n6 [label="across"];
> n7 [label="the bridge"];
> n0 -> {n1 n2};
> n1 -> {n3};
> n2 -> {n4 n5};
> n4 -> {n6};
> n5 -> {n7};
Also, if you're objective is to write this code, then go on; but if
you just need it working, did you search google?
http://www.google.com/search?as_q=lisp+DOT+generate
--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay