Hi, I have been lurking for a while and a few days ago I saw
a post that said "flatten is a useful function to learn
how to write", so I decided to pick up the challenge
Example:
(flatten '(a (b c) (d e)))
(A B C D E)
Here is my attempt:
(defun flatten (l)
(if (and (listp l) l)
(append (flatten (car l)) (if (cdr l) (flatten (cdr l))))
(list l)))
Now, my questions. Is it possible to avoid the double cdr call?
Also if the argument is not list the function behaves like
the list function, is that a bad thing?
--
Thomas.
"Thomas Stegen" <··········@hotmail.com> writes:
> Hi, I have been lurking for a while and a few days ago I saw
> a post that said "flatten is a useful function to learn
> how to write", so I decided to pick up the challenge
>
> Example:
>
> (flatten '(a (b c) (d e)))
> (A B C D E)
>
>
> Here is my attempt:
>
> (defun flatten (l)
> (if (and (listp l) l)
> (append (flatten (car l)) (if (cdr l) (flatten (cdr l))))
> (list l)))
>
> Now, my questions. Is it possible to avoid the double cdr call?
Certainly. (let ((tail (cdr l))) (if tail (flatten tail)))
But this is not where the efficiency loss in your function is.
Your function always bottoms out at (LIST L) which means that
it always conses new structure. You join such pieces with APPEND,
which will copy all but the last of the lists it gets as arguments.
The function NCONC will reuse rather than discarding those pieces.
There is, however, a way that you can write this function so that
you don't have to do the APPEND. It involves 2 arguments to FLATTEN.
It uses a technique similar to the way FACTORIAL can be done with 2
args. That is, instead of (* n (fact (- n 1))) at the recursion step,
you want (fact (- n 1) (* n result-so-far)) on the recursion step.
I'm trying not to give htis away, because I'm imagining this is homework.
> Also if the argument is not list the function behaves like
> the list function, is that a bad thing?
No. That's what it does inside the list, so it might as well do it
at the top, too.
By the way,
(and (listp l) l)
is the same as
(and (listp l) (not (null l)))
but since (listp l) means (or (null l) (consp l))
you can probably find a better way to write
(and (or (null l) (consp l)) (not (null l)))
"Kent M Pitman" <······@world.std.com> wrote in message
····················@shell01.TheWorld.com...
> "Thomas Stegen" <··········@hotmail.com> writes:
>
> > Hi, I have been lurking for a while and a few days ago I saw
> > a post that said "flatten is a useful function to learn
> > how to write", so I decided to pick up the challenge
> >
> > Example:
> >
> > (flatten '(a (b c) (d e)))
> > (A B C D E)
> >
> >
> > Here is my attempt:
> >
> > (defun flatten (l)
> > (if (and (listp l) l)
> > (append (flatten (car l)) (if (cdr l) (flatten (cdr l))))
> > (list l)))
> >
> > Now, my questions. Is it possible to avoid the double cdr call?
>
> Certainly. (let ((tail (cdr l))) (if tail (flatten tail)))
>
> But this is not where the efficiency loss in your function is.
> Your function always bottoms out at (LIST L) which means that
> it always conses new structure. You join such pieces with APPEND,
> which will copy all but the last of the lists it gets as arguments.
> The function NCONC will reuse rather than discarding those pieces.
I skipped forward about 150 pages in my book and checked up on
NCONC (Feel free to correct my terminology here). NCONC takes the
first list and changes the cdr of the last cons in that list
to point to the following list? APPEND, on the other hand, copies
the list and leaves the original lists unchanged.
>
> There is, however, a way that you can write this function so that
> you don't have to do the APPEND.
Well, could always change APPEND for NCONC, but I guess that
is not what you are talking about.
> It involves 2 arguments to FLATTEN.
> It uses a technique similar to the way FACTORIAL can be done with 2
> args. That is, instead of (* n (fact (- n 1))) at the recursion step,
> you want (fact (- n 1) (* n result-so-far)) on the recursion step.
> I'm trying not to give htis away, because I'm imagining this is homework.
I think I see what you are getting at. My knowledge of the standard
library (if that is what you call it) is quite limited so I am not quite
sure what to use. I'll figure it out eventually :)
And no, this isn't homework. I would be happy if it was though. As it is
we only do Java and C and I would like learning Lisp or some relative
in my studies. But unlike my fellow students I actually have an interest
in computers and computer science so I am learning it anyway :)
>
> > Also if the argument is not list the function behaves like
> > the list function, is that a bad thing?
>
> No. That's what it does inside the list, so it might as well do it
> at the top, too.
>
> By the way,
> (and (listp l) l)
> is the same as
> (and (listp l) (not (null l)))
> but since (listp l) means (or (null l) (consp l))
> you can probably find a better way to write
> (and (or (null l) (consp l)) (not (null l)))
The inverse law of logic...
(consp l)
Didn't know about that function, now I do :)
Thanks for your help.
--
Thomas.
Approaching singularity.
"Thomas Stegen" <··········@hotmail.com> writes:
> And no, this isn't homework. I would be happy if it was though. As it is
> we only do Java and C and I would like learning Lisp or some relative
> in my studies. But unlike my fellow students I actually have an interest
> in computers and computer science so I am learning it anyway :)
Ah, well, then... That means I can use optional arguments, too. Try:
(defun flatten (list &optional (list-so-far '()))
... (flatten (car list)
(let ((tail (cdr list)))
(when tail (flatten tail list-so-far)))) ...)
The trick will be that you don't then want (list l) but rather you need
to involve list-so-far with the answer.
I'll leave it to you to think more on this...
"Kent M Pitman" <······@world.std.com> wrote in message
····················@shell01.TheWorld.com...
> "Thomas Stegen" <··········@hotmail.com> writes:
[snip]
> (defun flatten (list &optional (list-so-far '()))
> ... (flatten (car list)
> (let ((tail (cdr list)))
> (when tail (flatten tail list-so-far)))) ...)
>
> The trick will be that you don't then want (list l) but rather you need
> to involve list-so-far with the answer.
>
> I'll leave it to you to think more on this...
I did, phew...
This is what I came up with:
(defun flatten2 (l &optional nl)
(if (consp l)
(flatten2 (car l)
(let ((tail (cdr l)))
(if tail (flatten2 tail nl) nl)))
(cons l nl)))
Not sure if it's better though. CONS probably copies and allocates memory?
Is this what is called tail recursion? I guess the main problem is that
I am not used to thinking in a tail recursive manner.
I note that you suggest to use WHEN where I use IF. I leave that for
another day :).
Thanks for your help, it's been educational.
--
Thomas.
Approaching singularity.
"Thomas Stegen" <··········@hotmail.com> writes:
> "Kent M Pitman" <······@world.std.com> wrote in message
> ····················@shell01.TheWorld.com...
> > "Thomas Stegen" <··········@hotmail.com> writes:
>
> [snip]
>
> > (defun flatten (list &optional (list-so-far '()))
> > ... (flatten (car list)
> > (let ((tail (cdr list)))
> > (when tail (flatten tail list-so-far)))) ...)
> >
> > The trick will be that you don't then want (list l) but rather you need
> > to involve list-so-far with the answer.
> >
> > I'll leave it to you to think more on this...
>
> I did, phew...
>
> This is what I came up with:
>
> (defun flatten2 (l &optional nl)
> (if (consp l)
> (flatten2 (car l)
> (let ((tail (cdr l)))
> (if tail (flatten2 tail nl) nl)))
> (cons l nl)))
>
> Not sure if it's better though. CONS probably copies and allocates memory?
No, cons doesn't copy. It directly creates a new cell that contains pointers
to the two arguments. Copying a pointer does not allocate new memory, so
no copying is involved; it does not recurse into the arguments of cons
copying them. The version you have now written conses the same number of
conses as are in the result, so is pretty close to optimal conswise. It
also visits each node only once, so is pretty optimal in that regard as
well.
> Is this what is called tail recursion? I guess the main problem is that
> I am not used to thinking in a tail recursive manner.
The outer of the two calls to FLATTEN2 inside the IF is in tail call
position. Some implementations may optimize this, some not. It
has no remaining things pending on the stack to do upon return, so a
compiler might remove it. Often they don't, though, for debugging reasons.
Debugging tail calls is often weird because if a bug happens, the caller
is no longer on the stack and it's hard to find out how you got there.
> I note that you suggest to use WHEN where I use IF. I leave that for
> another day :).
Well, you need the IF in this case becuase you need to return a value
there. (Mine had a bug, I think, which you seem to have fixed. Sorry,
that was accidental. Gotta watch this free advice. It's often worth
about what you pay.) I often use WHEN if there is only one
interesting arm... styles vary on this. What you wrote is fine.
I would, however, change &optional nl to &optional (nl '()) even though
it means the same thing because it gives documentation that [a] you
intend to view the nl as a list, and [b] you plan to initialize the
argument there rather than elsewhere in the body.
> Thanks for your help, it's been educational.
No problem.
Thomas Stegen wrote:
>
> "Kent M Pitman" <······@world.std.com> wrote in message
> ····················@shell01.TheWorld.com...
> > "Thomas Stegen" <··········@hotmail.com> writes:
>
> (defun flatten2 (l &optional nl)
> (if (consp l)
> (flatten2 (car l)
> (let ((tail (cdr l)))
> (if tail (flatten2 tail nl) nl)))
> (cons l nl)))
I see a problem. (flatten2 nil) returns (nil). That should be nil.
Once you fix that you can lose the bit where you worry about invoking
#'cdr twice, speaking of which I am not sure avoiding a second cdr saves
enough to justify making the code look so much hairier.
--
kenny tilton
clinisys, inc
---------------------------------------------------------------
"Harvey has overcome not only time and space but any objections."
Elwood P. Dowd
"Kenny Tilton" <·······@nyc.rr.com> wrote in message
······················@nyc.rr.com...
>
>
> Thomas Stegen wrote:
> >
> > "Kent M Pitman" <······@world.std.com> wrote in message
> > ····················@shell01.TheWorld.com...
> > > "Thomas Stegen" <··········@hotmail.com> writes:
> >
> > (defun flatten2 (l &optional nl)
> > (if (consp l)
> > (flatten2 (car l)
> > (let ((tail (cdr l)))
> > (if tail (flatten2 tail nl) nl)))
> > (cons l nl)))
>
> I see a problem. (flatten2 nil) returns (nil). That should be nil.
I have to think about this one....
>
> Once you fix that you can lose the bit where you worry about invoking
> #'cdr twice, speaking of which I am not sure avoiding a second cdr saves
> enough to justify making the code look so much hairier.
>
Speaking of which, it occurs to me that LET probably have a cost of it's
own. And I can't imagine the cost of CDR being much...
--
Thomas.
Approaching singularity.
"Thomas Stegen" <··········@hotmail.com> wrote in message news:<············@dennis.cc.strath.ac.uk>...
> > I see a problem. (flatten2 nil) returns (nil). That should be nil.
>
> I have to think about this one....
(consp nil) => nil
> Speaking of which, it occurs to me that LET probably have a cost of it's
> own. And I can't imagine the cost of CDR being much...
The let is very low cost if it costs anything at all. Don't worry
about that kind of thing for now anyway. Also, consider implementing
flatten in terms of mapcan and flatten. That leads to a more elegant
solution, if that's what you are after.
^L
"Thomas Stegen" <··········@hotmail.com> wrote in message
·················@dennis.cc.strath.ac.uk...
> "Kenny Tilton" <·······@nyc.rr.com> wrote in message
> ······················@nyc.rr.com...
> >
> >
> > Thomas Stegen wrote:
> > >
> > > "Kent M Pitman" <······@world.std.com> wrote in message
> > > ····················@shell01.TheWorld.com...
> > > > "Thomas Stegen" <··········@hotmail.com> writes:
> > >
> > > (defun flatten2 (l &optional nl)
> > > (if (consp l)
> > > (flatten2 (car l)
> > > (let ((tail (cdr l)))
> > > (if tail (flatten2 tail nl) nl)))
> > > (cons l nl)))
> >
> > I see a problem. (flatten2 nil) returns (nil). That should be nil.
>
> I have to think about this one....
>
> >
> > Once you fix that you can lose the bit where you worry about invoking
> > #'cdr twice, speaking of which I am not sure avoiding a second cdr saves
> > enough to justify making the code look so much hairier.
> >
>
> Speaking of which, it occurs to me that LET probably have a cost of it's
> own. And I can't imagine the cost of CDR being much...
I can't see the LET having much of a cost.
If the compiler has any brains at all, it will
probably open-code the call to CDR, allocate the
binding for TAIL in a register. So there would
not be any code associated with the LET.
Even with a really stupid compiler, or one that is
being forced to do no optimization, it still won't
cost much more than a MOV instruction, and perhaps
even less.
In article <············@dennis.cc.strath.ac.uk>,
Thomas Stegen <··········@hotmail.com> wrote:
>Speaking of which, it occurs to me that LET probably have a cost of it's
>own. And I can't imagine the cost of CDR being much...
LET's cost is virtually negligible. If a temporary value has to be
computed, that will take place with or without the LET. LET simply tells
the compiler to associated a name with the place where that temporary value
is stored. That's a compile-time cost, not a run-time cost.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin <······@genuity.net> writes:
> In article <············@dennis.cc.strath.ac.uk>,
> Thomas Stegen <··········@hotmail.com> wrote:
> >Speaking of which, it occurs to me that LET probably have a cost of it's
> >own. And I can't imagine the cost of CDR being much...
>
> LET's cost is virtually negligible. If a temporary value has to be
> computed, that will take place with or without the LET. LET simply tells
> the compiler to associated a name with the place where that temporary value
> is stored. That's a compile-time cost, not a run-time cost.
Yes. Though sometimes the issue isn't as simple as "does the compiler do
this or not" but it's also "does the compiler understand the programmer's
sense of priorities well enough to do the right thing".
(let ((x 3)) (+ x x)) might be constant-folded by the compiler if
the compiler realizes that the choice to bind a variable was only syntactic,
and that it would be both "just as fast" and "just as space efficient" to
turn into (+ 3 3) [and then probably to 6]. If there was a more complex
expression to be computed that is best centralized, computing it once and
saving the value might be better. There are intermediate cases, though,
like (let ((temp (foo x))) (if test (f temp) (g temp))) where g will only
be computed once on either path, and so folding it down to
(if test (f (foo x)) (g (foo x)))
is likely to be faster, but will take more space. Compilers need to be told
whether speed or space is at a premium here. If this is obscure code not
called in a loop and rarely called at all, space probably matters. In a tight
inner loop, speed may may matter. In principle, the OPTIMIZE declaration
can help you advise the compiler about how to manage this choice, optimizing
speed or space or other things. [See CLHS.] The compiler is not obliged
to use the OPTIMIZE declaration, but if it doesn't in some case you find
important, you can always send a bug report...
I remember one of the first questions I asked of people when working on
MACSYMA (my first time working on Lisp for pay) was "is PROG or LET faster".
(We used to use PROG a lot more back then because TAGBODY and BLOCK were not
separated out as separate operators.) Someone told me this important piece
of advice:
For language glue like this that should not have a cost, program as if
there is no difference in speed. Report bugs where your expectations are
not met. Never make a choice of programming construct based on a timing
you observe that you believe is either buggy or suboptimal.
In Unix, by contrast, the community grew up with each program treating every
other program it ran into as potentially broken and specially working around
each of its bugs rather than reporting them and demanding them fixed. I don't
any longer program in Unix at that level, so I don't know if it's fixed now
(hard to imagine how it could really have been) but in the early days it was
really out of control. It's a mindset thing and it bubbles up from the micro
to the macro. Each individual has the choice to either behave cynically
or not ... but if you expect the worst of people and programs, that's what
you'll probably get. Aspire to better.
"Thomas Stegen" <··········@hotmail.com> writes:
> Speaking of which, it occurs to me that LET probably have a cost of it's
> own. And I can't imagine the cost of CDR being much...
LET shouldn't have any cost. Sometimes it's beneficial, depending on
the compiler (cmucl, for example, likes lots of nested LETs). In the
case of creating a tightly scoped variable to store the result of CDR,
CMUCL produces the same code as if you'd put the calls to CDR
everywhere you wanted it (on SPARC, at least).
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Kenny Tilton <·······@nyc.rr.com> writes:
> Thomas Stegen wrote:
> >
> > "Kent M Pitman" <······@world.std.com> wrote in message
> > ····················@shell01.TheWorld.com...
> > > "Thomas Stegen" <··········@hotmail.com> writes:
> >
> > (defun flatten2 (l &optional nl)
> > (if (consp l)
> > (flatten2 (car l)
> > (let ((tail (cdr l)))
> > (if tail (flatten2 tail nl) nl)))
> > (cons l nl)))
>
> I see a problem. (flatten2 nil) returns (nil). That should be nil.
I didn't fuss over this because his original function had the same behavior.
Because of the design of Common Lisp, which in turn is due to
historical considerations, people specifying the definition of
functions like this need to determine whether they want to treat NIL
as the empty list or as the symbol NIL. The empty list interpretation
calls for () to be returned while view as a symbol calls for (NIL) to
be returned since the symbol FOO would yield (FOO).
> Once you fix that you can lose the bit where you worry about invoking
> #'cdr twice, speaking of which I am not sure avoiding a second cdr saves
> enough to justify making the code look so much hairier.
Yes, assuming that's what the original problem called for as an
interpretation.
[Incidentally, this problem is not an issue of conflating () and false
as is often quickly jumped upon by the Scheme community. It's due to
conflating the symbol NIL and (). There are three things that are
joined and its the ()/NIL join or the #f/NIL join that is generally
the problem. The so-called ()/#f problem rarely if ever manifests an
actual problem and is more often a virtue, in my experience.]
Kent M Pitman <······@world.std.com> writes:
> [Incidentally, this problem is not an issue of conflating () and false
> as is often quickly jumped upon by the Scheme community. It's due to
> conflating the symbol NIL and (). There are three things that are
> joined and its the ()/NIL join or the #f/NIL join that is generally
> the problem. The so-called ()/#f problem rarely if ever manifests an
> actual problem and is more often a virtue, in my experience.]
The Scheme community knows that (symbol? '()) is a big deal, and that
(eq? '() (= 0 1)) is not a big deal. Maybe there are some ignorant
folks, but it's not fair to blame the "Scheme community" for its most
ignorant members.
MIT Scheme has gotten on just fine for a long with with (eq? '() #f),
though it's finally changing. For a very long time, this was
officially tolerated by the RnRS.
Thomas
In article <···············@shell01.TheWorld.com>,
Kent M Pitman <······@world.std.com> wrote:
>Kenny Tilton <·······@nyc.rr.com> writes:
>
>> > > "Thomas Stegen" <··········@hotmail.com> writes:
>> >
>> > (defun flatten2 (l &optional nl)
>> > (if (consp l)
>> > (flatten2 (car l)
>> > (let ((tail (cdr l)))
>> > (if tail (flatten2 tail nl) nl)))
>> > (cons l nl)))
>>
>> I see a problem. (flatten2 nil) returns (nil). That should be nil.
>
>I didn't fuss over this because his original function had the same behavior.
>
>Because of the design of Common Lisp, which in turn is due to
>historical considerations, people specifying the definition of
>functions like this need to determine whether they want to treat NIL
>as the empty list or as the symbol NIL. The empty list interpretation
>calls for () to be returned while view as a symbol calls for (NIL) to
>be returned since the symbol FOO would yield (FOO).
>[...]
>
>[Incidentally, this problem is not an issue of conflating () and false
> as is often quickly jumped upon by the Scheme community. It's due to
> conflating the symbol NIL and (). There are three things that are
> joined and its the ()/NIL join or the #f/NIL join that is generally
> the problem. The so-called ()/#f problem rarely if ever manifests an
> actual problem and is more often a virtue, in my experience.]
For all three of nil-qua-symbol, nil-qua-empty-list,
and nil-qua-false, in a world that appropriately
distinguishes them, the call (flatten2 nil) would
continue to yield (nil). Neither two- nor three-way
deconflation can solve the problem with the code as
written, because the predicate consp (in that
world) still won't be true of any of them.
--d
····@goldshoe.gte.com (Dorai Sitaram) writes:
> For all three of nil-qua-symbol, nil-qua-empty-list,
> and nil-qua-false, in a world that appropriately
> distinguishes them, the call (flatten2 nil) would
> continue to yield (nil). Neither two- nor three-way
> deconflation can solve the problem with the code as
> written, because the predicate consp (in that
> world) still won't be true of any of them.
No, but in a world where NIL is either an empty list or a symbol, then
dealing with (FOO NIL BAR) has different answers depending on whether
you mean (FOO NIL-qua-symbol BAR) or (FOO NIL-qua-empty-list BAR).
That's why I said, look not to the output but to the input specification
to know the right answer. In one case (FOO NIL BAR) is the right answer
because a symbol was encountered, and in the other case (FOO BAR) is the
right answer because () was an empty non-terminal.
In article <···············@shell01.TheWorld.com>,
Kent M Pitman <······@world.std.com> wrote:
>····@goldshoe.gte.com (Dorai Sitaram) writes:
>
>> For all three of nil-qua-symbol, nil-qua-empty-list,
>> and nil-qua-false, in a world that appropriately
>> distinguishes them, the call (flatten2 nil) would
>> continue to yield (nil). Neither two- nor three-way
>> deconflation can solve the problem with the code as
>> written, because the predicate consp (in that
>> world) still won't be true of any of them.
>
>No, but in a world where NIL is either an empty list or a symbol, then
>dealing with (FOO NIL BAR) has different answers depending on whether
>you mean (FOO NIL-qua-symbol BAR) or (FOO NIL-qua-empty-list BAR).
>That's why I said, look not to the output but to the input specification
>to know the right answer. In one case (FOO NIL BAR) is the right answer
>because a symbol was encountered, and in the other case (FOO BAR) is the
>right answer because () was an empty non-terminal.
I remember you said conflating () and #F was not the
issue; conflating () and NIL-qua-symbol was. No
such fine distinction applies here though. Conflating
() with either creates a choice of answers.
Even in a Scheme where () == #F and neither is a
symbol, one still has to decide what the flattening of
(FOO #F BAR) should give.
--d
····@goldshoe.gte.com (Dorai Sitaram) writes:
> In article <···············@shell01.TheWorld.com>,
> Kent M Pitman <······@world.std.com> wrote:
> >····@goldshoe.gte.com (Dorai Sitaram) writes:
> >
> >> For all three of nil-qua-symbol, nil-qua-empty-list,
> >> and nil-qua-false, in a world that appropriately
> >> distinguishes them, the call (flatten2 nil) would
> >> continue to yield (nil). Neither two- nor three-way
> >> deconflation can solve the problem with the code as
> >> written, because the predicate consp (in that
> >> world) still won't be true of any of them.
> >
> >No, but in a world where NIL is either an empty list or a symbol, then
> >dealing with (FOO NIL BAR) has different answers depending on whether
> >you mean (FOO NIL-qua-symbol BAR) or (FOO NIL-qua-empty-list BAR).
> >That's why I said, look not to the output but to the input specification
> >to know the right answer. In one case (FOO NIL BAR) is the right answer
> >because a symbol was encountered, and in the other case (FOO BAR) is the
> >right answer because () was an empty non-terminal.
>
> I remember you said conflating () and #F was not the
> issue; conflating () and NIL-qua-symbol was. No
> such fine distinction applies here though. Conflating
> () with either creates a choice of answers.
>
> Even in a Scheme where () == #F and neither is a
> symbol, one still has to decide what the flattening of
> (FOO #F BAR) should give.
I don't see why. Why would false be different than true? If it's not a
list, then it's an atom. If it's an atom, it's flat like every other
atom.
Kent M Pitman <······@world.std.com> writes:
> ····@goldshoe.gte.com (Dorai Sitaram) writes:
> >
> > Even in a Scheme where () == #F and neither is a
> > symbol, one still has to decide what the flattening of
> > (FOO #F BAR) should give.
>
> I don't see why. Why would false be different than true? If it's not a
> list, then it's an atom. If it's an atom, it's flat like every other
> atom.
But if (eq? '() #f), then #f is a list, but #t is still an atom.
Thomas
·········@becket.net (Thomas Bushnell, BSG) writes:
> Kent M Pitman <······@world.std.com> writes:
>
> > ····@goldshoe.gte.com (Dorai Sitaram) writes:
> > >
> > > Even in a Scheme where () == #F and neither is a
> > > symbol, one still has to decide what the flattening of
> > > (FOO #F BAR) should give.
> >
> > I don't see why. Why would false be different than true? If it's not a
> > list, then it's an atom. If it's an atom, it's flat like every other
> > atom.
>
> But if (eq? '() #f), then #f is a list, but #t is still an atom.
Oops. Right. Just ignore me.
I was hoping to stave off this tired old debate by mentioning it, and may
have triggered it by accident instead. Well, maybe if I quietly slink off
now it will go away...
In article <···············@shell01.TheWorld.com>,
Kent M Pitman <······@world.std.com> wrote:
>····@goldshoe.gte.com (Dorai Sitaram) writes:
>
>>
>> I remember you said conflating () and #F was not the
>> issue; conflating () and NIL-qua-symbol was. No
>> such fine distinction applies here though. Conflating
>> () with either creates a choice of answers.
>>
>> Even in a Scheme where () == #F and neither is a
>> symbol, one still has to decide what the flattening of
>> (FOO #F BAR) should give.
>
>I don't see why. Why would false be different than true? If it's not a
>list, then it's an atom. If it's an atom, it's flat like every other
>atom.
I'll give the straight answer, but I can't imagine you
don't already know this, so I am puzzled by your
question. Maybe there is a catch I didn't get.
OK, the given is that false is also a list, the
empty one, so the flatten of
(FOO () BAR) aka (FOO #F BAR)
has a choice of either splicing out the ()
to produce
(FOO BAR)
or keeping the #F to produce
(FOO #F BAR)
If I picked the first choice, the objection is the one
you formulated above, ie, "Why should false be
treated any differently than true for the purposes of
flattening?"
If I picked the second, the objection morphs to
"Why should the empty list be treated differently
than any other list for the purposes of flattening?"
Immobilization results, and since you have been
bringing Aristotle up a lot lately, I wish to wax
classical for a moment and liken the predicament
to that of the Aristotelian donkey who starves to death
because he is equidistant from two equally tempting
bales of hay.
--d
"Thomas Stegen" <··········@hotmail.com> writes:
> Hi, I have been lurking for a while and a few days ago I saw
> a post that said "flatten is a useful function to learn
> how to write", so I decided to pick up the challenge
>
>
> Here is my attempt:
>
> (defun flatten (l)
> (if (and (listp l) l)
> (append (flatten (car l)) (if (cdr l) (flatten (cdr l))))
> (list l)))
Not a bad first try. Note however that APPEND is horrendously
expensive, as it copies an entire new list each time.
Try again, and think "CONS" this time. We'll give you the
"canonical" implementation after your second try. :-)
--
It would be difficult to construe Larry Wall, in article
this as a feature. <·····················@netlabs.com>