I'm wondering if there is already a CL function to do (what I call) a
list explosion:
(defun explode (list)
(mapcan #'(lambda (i)
(if (listp i)
i
(list i)))
list))
=> EXPLODE
(explode '((1 2 3) 4 5 (6 7 8)))
=> (1 2 3 4 5 6 7 8)
It need not be recursive, just a single level explosion is okay (if I
need more, I'd call it more than once). What I have works fine, but if
I'm missing a function that already does this for me, it would clean up
my code a bit :)
Thanks,
Jeff M.
--
http://www.retrobyte.org
··············@gmail.com
"Jeff" <·······@gmail.com> writes:
> I'm wondering if there is already a CL function to do (what I call) a
> list explosion:
>
> (defun explode (list)
> (mapcan #'(lambda (i)
> (if (listp i)
> i
(copy-list i), since MAPCAN does an NCONC-like operation [destructive append].
> (list i)))
> list))
> => EXPLODE
>
> (explode '((1 2 3) 4 5 (6 7 8)))
This is literal data you're giving it. You're not allowed to modify it.
Interactively, your implementation is happening to let you, but in
in some implementations, usually in compiled code situations, this may
cause problems because the literals may be shared among programs.
> => (1 2 3 4 5 6 7 8)
>
> It need not be recursive, just a single level explosion is okay (if I
> need more, I'd call it more than once). What I have works fine, but if
> I'm missing a function that already does this for me, it would clean up
> my code a bit :)
What you're doing is common in classroom situations, but rarely hugely
useful in production work, so what you have is probably as concise as
you're likely to get.
Besides, except for the bug I've cited, I'm not sure what you've written
is especially ugly. To the extent that it is, it's because the merging
of the lists is unmotivated as a 'general' notion. That's why the name
'explode' is the best you can come up with, too--because it doesn't serve
any really useful abstraction.
Sometimes when doing work with sets that are represented as either
singleton non-lists or as lists of elements, this might be vaguely
useful, and then it might be vaguely like some kind of set-union
thing, but then it's not trying to eliminate duplicates, so it isn't
quite right for that.
Lists are often used as quasi-structures with no name or DEFSTRUCT,
but it makes no more sense to NCONC them than it does to nconc two
structs.
The results of several function calls are often combined by mapping
operations, but usually the results are "of a kind" and that means
usually "all lists" or "all non-lists". NCONC (and MAPCAN) is a good
function for merging such things. There are other "patterns" of using
lists, too, but mostly they just never result in this kind of thing
that happens so often in class work where teachers want people to
"flatten" or "explode" trees.
Trees usually have structure for a reason, and throwing away that structure
certainly can be done, but it just doesn't happen a lot. Which is why
there's not a function to do what you want to do.
Mind you--I'm not saying what you're doing can't or shouldn't be done.
It just seems contrived and homework-like from the degree to which you've
motivated it. "real" problems usually come with an explanation of the kinds
of data that are being manipulated, and a reason for why they sometimes occur
in lists and sometimes not, etc.
Just to clarify: if a list starts with a single-quote, don't use
functions that modify its structure, like mapcan. Most Lispers have
been burned by this at least once.
Kent M Pitman <······@nhplace.com> writes:
> "Jeff" <·······@gmail.com> writes:
>
> > I'm wondering if there is already a CL function to do (what I call) a
> > list explosion:
> >
> > (defun explode (list)
> > (mapcan #'(lambda (i)
> > (if (listp i)
> > i
>
> (copy-list i), since MAPCAN does an NCONC-like operation [destructive append].
>
> > (list i)))
> > list))
> > => EXPLODE
> >
> > (explode '((1 2 3) 4 5 (6 7 8)))
>
> This is literal data you're giving it. You're not allowed to modify it.
> Interactively, your implementation is happening to let you, but in
> in some implementations, usually in compiled code situations, this may
> cause problems because the literals may be shared among programs.
>
> > => (1 2 3 4 5 6 7 8)
> >
> > It need not be recursive, just a single level explosion is okay (if I
> > need more, I'd call it more than once). What I have works fine, but if
> > I'm missing a function that already does this for me, it would clean up
> > my code a bit :)
>
> What you're doing is common in classroom situations, but rarely hugely
> useful in production work, so what you have is probably as concise as
> you're likely to get.
>
> Besides, except for the bug I've cited, I'm not sure what you've written
> is especially ugly. To the extent that it is, it's because the merging
> of the lists is unmotivated as a 'general' notion. That's why the name
> 'explode' is the best you can come up with, too--because it doesn't serve
> any really useful abstraction.
Sure it does, "depth-first search". The meaningless name "explode"
makes me think that you're right about how the OP is thinking about
it, though. However, in case a dfs is really what he wants (maybe
he's calculating the list then iterating over it), my advice would be,
write a MAP-DFS function or a DO-DFS macro, and see if you still think
you need "explode". If so, it will be as simple as:
(defun dfs-as-list (tree)
(let ((result ()))
(do-dfs (leaf tree)
(push leaf result))
(nreverse result)))
but I suspect that once you have a way of traversing a tree without
consing up an intermediate list, you'll find that list to be
unnecessary.
···@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> Kent M Pitman <······@nhplace.com> writes:
>
> > Besides, except for the bug I've cited, I'm not sure what you've written
> > is especially ugly. To the extent that it is, it's because the merging
> > of the lists is unmotivated as a 'general' notion. That's why the name
> > 'explode' is the best you can come up with, too--because it doesn't serve
> > any really useful abstraction.
>
> Sure it does, "depth-first search". The meaningless name "explode"
> makes me think that you're right about how the OP is thinking about
> it, though. However, in case a dfs is really what he wants (maybe
> he's calculating the list then iterating over it), my advice would be,
> write a MAP-DFS function or a DO-DFS macro, and see if you still think
> you need "explode". If so, it will be as simple as: [...]
·············@yahoo.com (Martin DeMello) writes:
> I use it every so often in my ruby code (it's a standard method called
> 'flatten' there) where a function returns a list of lists, but my call
> to it is such that I know those lists will have one element each.
I don't think I'm trying to disagree with Thomas or Martin here.
I didn't mean to say it wasn't conceptually possible to construct uses
for it, and these are fine uses. It's always hard to speak generally about
ANY computational structure or situation since there's almost always SOME
counterexample, but the point I was trying to highlight is that in each of
these cases, the lists are not "just lists". Rather, they are containers
of some known kind for objects of some known kind.
For example, it helps to know if the lists and singletons are
each list designators (that is, a non-list is standing for a list
of one-element) or lists themselves (that is, a non-list is an error).
And it's useful to know whether a list is automatically a collection
(that is, a list cannot occur as an ordinary result) or whether lists
that can be collapsed are recognized only by context. It's also useful
to know whether the other objects are sets or collections or something else.
And so it ends up being kind of like EQUAL [*] where yes, you can provide
an operator that does something arbitrary and happens to work in certain
arbitrary cases. You can even provide several such (viz, EQ, EQL, EQUAL,
EQUALP, TREE-EQUAL, ...). But there being no canonical set of circumstances,
the USUAL case seems to me to be that you study the domain you really have
and write a MERGE-RETURN-VALUES or SET-UNION or something that is specific
to your needs, not general of the form "merges any list of anything subject
to no particular understanding of what those lists or list elements are".
Then again, remember that I think that EQUAL itself is also arbitrary and
not-general. Some people disagree with me. But at least I've spelled out
my reasons for believing what I do.
[*] = http://www.nhplace.com/kent/PS/EQUAL.html
Kent M Pitman <······@nhplace.com> wrote:
>
> The results of several function calls are often combined by mapping
> operations, but usually the results are "of a kind" and that means
> usually "all lists" or "all non-lists". NCONC (and MAPCAN) is a good
> function for merging such things. There are other "patterns" of using
> lists, too, but mostly they just never result in this kind of thing
> that happens so often in class work where teachers want people to
> "flatten" or "explode" trees.
I use it every so often in my ruby code (it's a standard method called
'flatten' there) where a function returns a list of lists, but my call
to it is such that I know those lists will have one element each.
martin
"Jeff" <·······@gmail.com> writes:
> I'm wondering if there is already a CL function to do (what I call) a
> list explosion:
>
> (defun explode (list)
> (mapcan #'(lambda (i)
> (if (listp i)
> i
> (list i)))
> list))
> => EXPLODE
>
> (explode '((1 2 3) 4 5 (6 7 8)))
> => (1 2 3 4 5 6 7 8)
>
> It need not be recursive, just a single level explosion is okay (if I
> need more, I'd call it more than once). What I have works fine, but if
> I'm missing a function that already does this for me, it would clean up
> my code a bit :)
Well, traditionnaly EXPLODE and IMPLODE are names used for functions
that convert a symbol into a list of one-character symbols
corresponding to the characters in the name of the first symbol, and
back.
Your function is usually called FLATTEN.
This is no standard, just what I've seen them called in old code...
The short, recursive, definition:
(defun flatten (tree)
(if (atom tree)
(list tree)
(mapcan (function flatten) tree)))
A derecursived definition:
(DEFUN FLATTEN (TREE)
"
RETURN: A list containing all the elements of the `tree'.
"
(LOOP WITH RESULT = NIL
WITH STACK = NIL
WHILE (OR TREE STACK)
DO (COND
((NULL TREE)
(SETQ TREE (POP STACK)))
((ATOM TREE)
(PUSH TREE RESULT)
(SETQ TREE (POP STACK)))
((LISTP (CAR TREE))
(PUSH (CDR TREE) STACK)
(SETQ TREE (CAR TREE)))
(T
(PUSH (CAR TREE) RESULT)
(SETQ TREE (CDR TREE))))
FINALLY (RETURN (NREVERSE RESULT))))
I used this function 7 times, in graph processing code. Not a totally
useless function...
--
__Pascal Bourguignon__ http://www.informatimago.com/
-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCS d? s++:++ a+ C+++ UL++++ P--- L+++ E+++ W++ N+++ o-- K- w---
O- M++ V PS PE++ Y++ PGP t+ 5+ X++ R !tv b+++ DI++++ D++
G e+++ h+ r-- z?
------END GEEK CODE BLOCK------
Pascal Bourguignon wrote:
> Well, traditionnaly EXPLODE and IMPLODE are names used for functions
> that convert a symbol into a list of one-character symbols
> corresponding to the characters in the name of the first symbol, and
> back.
>
Bah. I miss explode. Okay, not really, it actually went long before my
first encounter with lisp, but I think it was just the wrong
abstraction level, not intrinsically bad:
I do think there should be a standardised "SEXPLODE" function to convert
a symbol such as MAKE-ROCKET-GO-NOW into a list of smaller symbols
'(MAKE ROCKET GO NOW)
:-)
David Golden <············@oceanfree.net> wrote:
+---------------
| I do think there should be a standardised "SEXPLODE" function to
| convert a symbol such as MAKE-ROCKET-GO-NOW into a list of smaller
| symbols '(MAKE ROCKET GO NOW)
+---------------
What's so hard about that? ;-}
> (asdf:operate 'asdf:load-op :split-sequence)
...[chatter]...
> (import 'split-sequence:split-sequence)
T
> (defun sexplode (symbol)
(mapcar #'intern (split-sequence #\- (symbol-name symbol))))
SEXPLODE
> (sexplode 'make-rocket-go-now)
(MAKE ROCKET GO NOW)
>
Oh, you mean it doesn't "do the right thing" with packages?
> (make-package :foo :use nil)
#<The FOO package, 0/9 internal, 0/9 external>
> (sexplode 'foo::make-rocket-go-now)
(MAKE ROCKET GO NOW)
>
We can fix that: ;-}
> (defun sexplode (symbol &optional (package (symbol-package symbol)))
(flet ((re-intern (string)
(intern string package)))
(mapcar #'re-intern (split-sequence #\- (symbol-name symbol)))))
SEXPLODE
> (sexplode 'foo::make-rocket-go-now)
(FOO::MAKE FOO::ROCKET FOO::GO FOO::NOW)
>
and:
> (sexplode 'make-rocket-go-now :foo)
(FOO::MAKE FOO::ROCKET FOO::GO FOO::NOW)
>
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
> What's so hard about that? ;-}
>
Wasn't saying it's hard [to implement relatively inefficiently in
standard common lisp] - It's not standard though,
and it's not a highly optimised operation - e.g. you just had to go
symbol->string->sequence-split->strings->symbols.
Whereas if composite symbols were structures of more primitive symbols,
it might be possible to optimise operations on composite symbol's
structure a bit better.
I haven't quite come up with a sensible use for it other than as a
for-the-sake-of-it programming model.
Spake Jeff:
> (explode '((1 2 3) 4 5 (6 7 8)))
> => (1 2 3 4 5 6 7 8)
Dunno if this is any help, but my Haskell lecturer calls this
tree-flatten.
--
Trent Buck, Student Errant
I bought one of those camouflage shirts and put it in my closet. Now I
can't find it.
Trent Buck wrote:
> Spake Jeff:
> > (explode '((1 2 3) 4 5 (6 7 8)))
> > => (1 2 3 4 5 6 7 8)
>
> Dunno if this is any help, but my Haskell lecturer calls this
> tree-flatten.
I do like the name 'flatten'. :)
--
http://www.retrobyte.org
··············@gmail.com