clever flatten?
Sunil Mishra
\\ 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
Robert G. Malkin
Henry Baker
<rm...@andrew.cmu.edu> 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)))))
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
Seth A Tisue
Henry Baker <hba...@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 <s-t...@nwu.edu> http://www.eecs.nwu.edu/~tisue/
John Atwood
>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
_________________________________________________________________
Erik Naggum
| 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.
Stephan Kepser
Baker) writes:
> In article <Ul6vo1C00...@andrew.cmu.edu>, "Robert G. Malkin"
> <rm...@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 kep...@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
Ernest T. Rees
]
] 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.
Sunil Mishra
\\ | (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
Henry Baker
kep...@cis.uni-muenchen.de (Stephan Kepser) wrote:
> In article <hbaker-0902...@10.0.2.15> hba...@netcom.com (Henry
> Baker) writes:
> > In article <Ul6vo1C00...@andrew.cmu.edu>, "Robert G. Malkin"
> > <rm...@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!
Henry Baker
Baker) 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.
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.
Seth A Tisue
Henry Baker <hba...@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.
dcwhite
dcw...@phoenix.net (dcwhite) wrote:
>In article <hbaker-0902...@10.0.2.15>,
> hba...@netcom.com (Henry Baker) wrote:
>>In article <Ul6vo1C00...@andrew.cmu.edu>, "Robert G. Malkin"
>><rm...@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)
>>>
>>> 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?
>>
>>(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)))))
>>
>
>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.
>
>dcw...@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