does anyone know of a clever list flattening routine?
that is,
(flatten '((ab) nil (a (bcd)) (df))) -> (ab a bcd df)
the cl implementations i am using don't have series, so i can't just
call (collect-append (scan list)). i'm using flatten for some pretty big
lists (50-100k) and its inefficiency blows up space requirements to the
point where its use is becoming impractical... any suggestions?
thanks
rob
In article <··················@andrew.cmu.edu> "Robert G. Malkin" <·····@andrew.cmu.edu> writes:
\\ does anyone know of a clever list flattening routine?
\\ that is,
\\ (flatten '((ab) nil (a (bcd)) (df))) -> (ab a bcd df)
\\
\\ the cl implementations i am using don't have series, so i can't just
\\ call (collect-append (scan list)). i'm using flatten for some pretty big
\\ lists (50-100k) and its inefficiency blows up space requirements to the
\\ point where its use is becoming impractical... any suggestions?
\\ thanks
\\ rob
Why not write your own function? I don't really understand what the
constraints are, perhaps I should give an example of what might work, and
you tell me what's wrong with it. I'm also trying to keep memory
constraints in mind, and this will result in an ugly function.
(defun flatten (tree &aux (output '(())) output-end)
(declare (special output-end))
(setq output-end output)
(flatten-loop tree)
(cdr output))
(defun flatten-loop (tree)
(declare (special output-end))
(mapc #'(lambda (tree-el)
(cond ((listp tree-el)
(flatten-loop tree-el))
(t (push tree-el (cdr output-end))
(setq output-end (cdr output-end)))))
tree))
Sunil
[Sunil Mishra]
| Why not write your own function? I don't really understand what the
| constraints are, perhaps I should give an example of what might work,
| and you tell me what's wrong with it. I'm also trying to keep memory
| constraints in mind, and this will result in an ugly function.
|
| (defun flatten (tree &aux (output '(())) output-end)
| (declare (special output-end))
| (setq output-end output)
| (flatten-loop tree)
| (cdr output))
|
| (defun flatten-loop (tree)
| (declare (special output-end))
| (mapc #'(lambda (tree-el)
| (cond ((listp tree-el)
| (flatten-loop tree-el))
| (t (push tree-el (cdr output-end))
| (setq output-end (cdr output-end)))))
| tree))
using a lexical variable in a closure around a `labels' form, you could do
away with the expensive special variable and the separate function.
#<Erik 3032985139133767>
--
imagine if the buyers of the first PC's with PC-DOS didn't have to upgrade.
In article <················@arcana.naggum.no> Erik Naggum <····@naggum.no> writes:
\\ | (defun flatten (tree &aux (output '(())) output-end)
\\ | (declare (special output-end))
\\ | (setq output-end output)
\\ | (flatten-loop tree)
\\ | (cdr output))
\\ |
\\ | (defun flatten-loop (tree)
\\ | (declare (special output-end))
\\ | (mapc #'(lambda (tree-el)
\\ | (cond ((listp tree-el)
\\ | (flatten-loop tree-el))
\\ | (t (push tree-el (cdr output-end))
\\ | (setq output-end (cdr output-end)))))
\\ | tree))
\\
\\ using a lexical variable in a closure around a `labels' form, you could do
\\ away with the expensive special variable and the separate function.
Yes, I did realize that, I probably should have mentioned it too, I was
just too lazy to look up CLtL2 to figure out how the labels form is
applied :-)
Sunil
In article <··················@andrew.cmu.edu>, "Robert G. Malkin"
<·····@andrew.cmu.edu> wrote:
> does anyone know of a clever list flattening routine?
> that is,
> (flatten '((ab) nil (a (bcd)) (df))) -> (ab a bcd df)
>
> the cl implementations i am using don't have series, so i can't just
> call (collect-append (scan list)). i'm using flatten for some pretty big
> lists (50-100k) and its inefficiency blows up space requirements to the
> point where its use is becoming impractical... any suggestions?
> thanks
(defun flatten (x) (flatten-helper x nil))
(defun flatten-helper (x r) ;;; 'r' is the stuff to the 'right'.
(cond ((atom x) (cons x r))
(t (flatten-helper (car x) (flatten-helper (cdr x) r)))))
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
In article <·······················@10.0.2.15>,
Henry Baker <······@netcom.com> wrote:
>(defun flatten (x) (flatten-helper x nil))
>(defun flatten-helper (x r) ;;; 'r' is the stuff to the 'right'.
> (cond ((atom x) (cons x r))
> (t (flatten-helper (car x) (flatten-helper (cdr x) r)))))
May I suggest testing your code before posting it?
--
== Seth Tisue <·······@nwu.edu> http://www.eecs.nwu.edu/~tisue/
In article <·······················@10.0.2.15> ······@netcom.com (Henry
Baker) writes:
> In article <··················@andrew.cmu.edu>, "Robert G. Malkin"
> <·····@andrew.cmu.edu> wrote:
>
> > does anyone know of a clever list flattening routine?
> > that is,
> > (flatten '((ab) nil (a (bcd)) (df))) -> (ab a bcd df)
> > [ ... ]
>
> (defun flatten (x) (flatten-helper x nil))
>
> (defun flatten-helper (x r) ;;; 'r' is the stuff to the 'right'.
> (cond ((atom x) (cons x r))
> (t (flatten-helper (car x) (flatten-helper (cdr x) r)))))
>
Could it be that you missed one obvious case in your FLATTEN-HELPER?
> (flatten '((a b)))
(A B NIL NIL)
(defun flatten-helper (x r) ;;; 'r' is the stuff to the 'right'.
(cond ((null x) r)
((atom x) (cons x r))
(t (flatten-helper (car x) (flatten-helper (cdr x) r)))))
Now:
> (flatten '((a . b) c (d e f) ((g h) (i j))))
(A B C D E F G H I J)
Stephan.
--
Stephan Kepser ······@thecube.cis.uni-muenchen.de
CIS Centrum fuer Informations- und Sprachverarbeitung
LMU Muenchen, Wagmuellerstr. 23/III, D-80538 Muenchen, Germany
Tel: +49 +89/2110666 Fax: +49 +89/2110674
In article <··········@sparcserver.lrz-muenchen.de>,
······@cis.uni-muenchen.de (Stephan Kepser) wrote:
> In article <·······················@10.0.2.15> ······@netcom.com (Henry
> Baker) writes:
> > In article <··················@andrew.cmu.edu>, "Robert G. Malkin"
> > <·····@andrew.cmu.edu> wrote:
> >
> > > does anyone know of a clever list flattening routine?
> > > that is,
> > > (flatten '((ab) nil (a (bcd)) (df))) -> (ab a bcd df)
> > > [ ... ]
> >
> > (defun flatten (x) (flatten-helper x nil))
> >
> > (defun flatten-helper (x r) ;;; 'r' is the stuff to the 'right'.
> > (cond ((atom x) (cons x r))
> > (t (flatten-helper (car x) (flatten-helper (cdr x) r)))))
> >
>
> Could it be that you missed one obvious case in your FLATTEN-HELPER?
> > (flatten '((a b)))
> (A B NIL NIL)
>
>
> (defun flatten-helper (x r) ;;; 'r' is the stuff to the 'right'.
> (cond ((null x) r)
> ((atom x) (cons x r))
> (t (flatten-helper (car x) (flatten-helper (cdr x) r)))))
>
> Now:
> > (flatten '((a . b) c (d e f) ((g h) (i j))))
> (A B C D E F G H I J)
Yes, thanks very much. (blush, blush!)
No, I didn't get a chance to test my code, because my Coral Common Lisp
bit the dust when I changed from System 6 to System 7 on my Mac.
I have a version of xlisp somewhere, but I thought I could at least give the
basic idea for this homework problem.
I use the same trick for qsorting _lists_ in some of my papers in my ftp
directory. That code, I _did_ test!
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
In article <·······················@10.0.2.15>, ······@netcom.com (Henry
Baker) wrote:
> In article <··········@sparcserver.lrz-muenchen.de>,
> ······@cis.uni-muenchen.de (Stephan Kepser) wrote:
>
> > In article <·······················@10.0.2.15> ······@netcom.com (Henry
> > Baker) writes:
> > > In article <··················@andrew.cmu.edu>, "Robert G. Malkin"
> > > <·····@andrew.cmu.edu> wrote:
> > >
> > > > does anyone know of a clever list flattening routine?
> > > > that is,
> > > > (flatten '((ab) nil (a (bcd)) (df))) -> (ab a bcd df)
> > > > [ ... ]
> > >
> > > (defun flatten (x) (flatten-helper x nil))
> > >
> > > (defun flatten-helper (x r) ;;; 'r' is the stuff to the 'right'.
> > > (cond ((atom x) (cons x r))
> > > (t (flatten-helper (car x) (flatten-helper (cdr x) r)))))
> >
> > Could it be that you missed one obvious case in your FLATTEN-HELPER?
> > > (flatten '((a b)))
> > (A B NIL NIL)
> >
> >
> > (defun flatten-helper (x r) ;;; 'r' is the stuff to the 'right'.
> > (cond ((null x) r)
> > ((atom x) (cons x r))
> > (t (flatten-helper (car x) (flatten-helper (cdr x) r)))))
> >
> > Now:
> > > (flatten '((a . b) c (d e f) ((g h) (i j))))
> > (A B C D E F G H I J)
>
> Yes, thanks very much. (blush, blush!)
>
> No, I didn't get a chance to test my code, because my Coral Common Lisp
> bit the dust when I changed from System 6 to System 7 on my Mac.
>
> I have a version of xlisp somewhere, but I thought I could at least give the
> basic idea for this homework problem.
>
> I use the same trick for qsorting _lists_ in some of my papers in my ftp
> directory. That code, I _did_ test!
I forgot to point out that my posted flatten is for _cons_ 'trees',
not for _list_ 'trees'. But the poster asked for a flattener for list trees,
so this was wrong.
This flattener is cheap on the number of conses, but does not minimize
space in the stack, even after doing proper tail recursion. If you want
a flattener which minimizes the total amount of space, then you want to
start thinking about Deutsch-Schorre-Waite.
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
In article <·······················@10.0.2.15>,
Henry Baker <······@netcom.com> wrote:
>I forgot to point out that my posted flatten is for _cons_ 'trees',
>not for _list_ 'trees'. But the poster asked for a flattener for list trees,
>so this was wrong.
How about:
(defun flatten (list)
(loop for item in list
when (atom item) collect item
else nconc (flatten item)))
Substitute "unless (listp item)" for "when (atom item)" if you prefer
to omit NILs, as the original poster specified.
--
== Seth Tisue <·······@nwu.edu> http://www.eecs.nwu.edu/~tisue/
In article <··········@gryphon.phoenix.net>,
·······@phoenix.net (dcwhite) wrote:
>In article <·······················@10.0.2.15>,
> ······@netcom.com (Henry Baker) wrote:
>>In article <··················@andrew.cmu.edu>, "Robert G. Malkin"
>><·····@andrew.cmu.edu> wrote:
>>
>>> does anyone know of a clever list flattening routine?
>>> that is,
>>> (flatten '((ab) nil (a (bcd)) (df))) -> (ab a bcd df)
>>>
>>> the cl implementations i am using don't have series, so i can't just
>>> call (collect-append (scan list)). i'm using flatten for some pretty big
>>> lists (50-100k) and its inefficiency blows up space requirements to the
>>> point where its use is becoming impractical... any suggestions?
>>> thanks
>>
>>(defun flatten (x) (flatten-helper x nil))
>>
>>(defun flatten-helper (x r) ;;; 'r' is the stuff to the 'right'.
>> (cond ((atom x) (cons x r))
>> (t (flatten-helper (car x) (flatten-helper (cdr x) r)))))
>>
>
>Most likely, recursion is causing the problem that you describe. I recommend
>the following:
>
>1) Write the list in question to a disk file (assume TEMP.TXT as the
filename)
>
>2) Write a procedure that reads the disk file one character at a time. This
> procedure should ignore parentheses. In addition, it should read
> characters from the disk and push them onto a temporary list until it sees
> a blank. When a blank is encountered, the temporary list should be packed
> and the result should be pushed onto an "atom" list.
>
>3) When you reach the end of the file, the "atom" list will contain all
> elements of the original list without all of the parentheses.
>
>The advantage of this method involves the fact that a loop construct will
>work, avoiding the full memory problem caused by recursion. I will try to
>enclose an example of a function that should come close to performing the
>functionality described above. You may have to add functionality to it to
>convert "number symbols" to numbers, as any numbers encountered by READ-CHAR
>are converted to their character equivalent before they are saved on the
>"atom" list. Let me know if this helps, and good luck.
>
>·······@phoenix.net
My apologies for leaving out the attachment. I am still fairly new to the
workings of the internet. Hopefully, it will be attached immediately below.
BEGIN -- Cut Here -- cut here
(DEFUN TEST (
ATOM-LIST CHAR LIST)
(CLEAR-INPUT)
(OPEN-INPUT-FILE 'TEMP.LSP)
(LOOP (SETQ CHAR (READ-CHAR 'TEMP.LSP 'T 'NIL))
((NULL CHAR) (CLOSE-INPUT-FILE 'TEMP.LSP))
(COND ((OR (EQUAL CHAR '\()
(EQUAL CHAR '\))))
((EQUAL CHAR (ASCII 32))
(SETQ ATOM-LIST (LIST (PACK (REVERSE ATOM-LIST))))
(COND ((EQUAL ATOM-LIST '(||)))
(T (SETQ LIST (APPEND ATOM-LIST LIST))))
(SETQ ATOM-LIST 'NIL))
(T (PUSH CHAR ATOM-LIST))))
(REVERSE LIST))
END -- Cut Here -- cut here
·······@phoenix.net
From: John Atwood
Subject: Re: clever flatten? portable series package
Date:
Message-ID: <4fj0pu$994@engr.orst.edu>
Robert G. Malkin <·····@andrew.cmu.edu> wrote:
>does anyone know of a clever list flattening routine?
>that is,
>(flatten '((ab) nil (a (bcd)) (df))) -> (ab a bcd df)
>
>the cl implementations i am using don't have series, so i can't just
>call (collect-append (scan list)). i'm using flatten for some pretty big
>lists (50-100k) and its inefficiency blows up space requirements to the
>point where its use is becoming impractical... any suggestions?
CLTL2 tells me:
Implementation note: The series functions and the theory underlying them
are described in greater detail in [52,53]. These reports also discuss the
algorithms required to transform series expressions into loops and explain
how to obtain a portable implementation.
52Waters, Richard C. Optimization of Series Expressions, Part I: User's Manual
for the Series Macro Package. AI Memo 1082. MIT Artificial Intelligence
Laboratory (Cambridge, Massachusetts, January 1989).
53Waters, Richard C. Optimization of Series Expressions, Part II: Overview of
the Theory and Implementation. AI Memo 1083. MIT Artificial Intelligence
Laboratory (Cambridge, Massachusetts, January 1989).
John
--
_________________________________________________________________
Office phone: 541-737-5583 (Batcheller 349);home: 541-757-8772
Office mail: 303 Dearborn Hall, OSU, Corvallis, OR 97331
_________________________________________________________________
Robert G. Malkin wrote:
]
] does anyone know of a clever list flattening routine?
] the cl implementations i am using don't have series, so i can't just
] call (collect-append (scan list)). i'm using flatten for some pretty
big
] lists (50-100k) and its inefficiency blows up space requirements to the
] point where its use is becoming impractical... any suggestions?
Where are these huge lists coming from? You might consider avoiding
the problem by building them flat in the first place.