At page 124 of "Common Lisp An Interactive Approach" there is an
exercise where it is requested to write the function FLATTEN that
takes a list (tree) as input and returns a list of all atoms.
It is also requested to write two versions of the function so that:
(flatten '(a () b)) ----> (A B)
and
(flatten02 '(a () b)) ----> (A NIL B)
(defun flatten (tree)
(typecase tree
(null ())
(atom (list tree))
(t (append (flatten (first tree)) (flatten (rest tree))))))
How do I write FLATTEN02 ?
B.T.W.
At page 266 of "Common Lisp A Gentle Introduction to Symbolic
Computation" there is also an excercise where you are asked to write
the function FLATTEN so that
(touretzky-flatten '((A B (R)) A)) ----> (A B R A)
But the answer to this exercise (Appendix C) is the following:
(defun touretzky-flatten (tree)
(cond ((atom tree) (list tree))
(t (append (touretzky-flatten (car tree))
(touretzky-flatten (cdr tree))))))
CL-USER 5 : 1 > (touretzky-flatten '((A B (R)) A))
(A B R NIL NIL A NIL)
On Apr 19, 2:38 am, "An[z]elmus" <·······@somewhere.org> wrote:
> (flatten '(a () b)) ----> (A B)
> (flatten02 '(a () b)) ----> (A NIL B)
> How do I write FLATTEN02 ?
As you implied in the thread title, the problem
is telling the difference between a list that
started out empty and one that wound up empty
after handling the other elements. The answer
is to stop recursing before the (nonempty) list
is empty. In other words, just test for a list
with one element, and handle that case directly.
An even simpler way is to use mapping instead of
recursion.
--Dan
------------------------------------------------
Dan Bensen
http://www.prairienet.org/~dsb/
"An[z]elmus" <·······@somewhere.org> writes:
> At page 124 of "Common Lisp An Interactive Approach" there is an
> exercise where it is requested to write the function FLATTEN that
> takes a list (tree) as input and returns a list of all atoms.
> It is also requested to write two versions of the function so that:
>
> (flatten '(a () b)) ----> (A B)
>
> and
>
> (flatten02 '(a () b)) ----> (A NIL B)
>
> (defun flatten (tree)
> (typecase tree
> (null ())
> (atom (list tree))
> (t (append (flatten (first tree)) (flatten (rest tree))))))
>
> How do I write FLATTEN02 ?
Go to your favorite REPL, and type: '() RET
What is the result?
What does that mean?
Still not sure?
Try:
(atom '())
(symbolp '())
(listp '())
(eq '() 'nil)
(atom '(a b c))
(symbolp '(a b c))
(listp '(a b c))
(eq '(a b c) 'nil)
--
__Pascal Bourguignon__ http://www.informatimago.com/
READ THIS BEFORE OPENING PACKAGE: According to certain suggested
versions of the Grand Unified Theory, the primary particles
constituting this product may decay to nothingness within the next
four hundred million years.
On Sat, 19 Apr 2008 13:51:46 +0200, Pascal Bourguignon
<···@informatimago.com> wrote:
>> (flatten02 '(a () b)) ----> (A NIL B)
>>
>>[...]
>> How do I write FLATTEN02 ?
>
>Go to your favorite REPL, and type: '() RET
>What is the result?
>What does that mean?
I think you mean thar it is not possible to write such a function, at
least not the way suggested for the exercise.
"An[z]elmus" <·······@somewhere.org> writes:
> On Sat, 19 Apr 2008 13:51:46 +0200, Pascal Bourguignon
> <···@informatimago.com> wrote:
>>> (flatten02 '(a () b)) ----> (A NIL B)
>>>
>>>[...]
>>> How do I write FLATTEN02 ?
>>
>>Go to your favorite REPL, and type: '() RET
>>What is the result?
>>What does that mean?
>
> I think you mean thar it is not possible to write such a function, at
> least not the way suggested for the exercise.
Not at all. I want you to realize something about () that would allow
you to implement flatten02 easily.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Litter box not here.
You must have moved it again.
I'll poop in the sink.
On Sat, 19 Apr 2008 18:15:01 +0200, Pascal Bourguignon
<···@informatimago.com> wrote:
>Not at all. I want you to realize something about () that would allow
>you to implement flatten02 easily.
Still I don't get it. I keep thinking that there is no difference
between () and say (rest '(something)).
I undersand that () is the same as '(), nil and 'nil and that it is of
type list, atom and symbol at the same time, but that doesn't help me
either.
From: Kent M Pitman
Subject: Re: The empty list and the end of a list
Date:
Message-ID: <ulk39r53v.fsf@nhplace.com>
"An[z]elmus" <·······@somewhere.org> writes:
> On Sat, 19 Apr 2008 18:15:01 +0200, Pascal Bourguignon
> <···@informatimago.com> wrote:
>
> >Not at all. I want you to realize something about () that would allow
> >you to implement flatten02 easily.
>
> Still I don't get it. I keep thinking that there is no difference
> between () and say (rest '(something)).
> I undersand that () is the same as '(), nil and 'nil and that it is of
> type list, atom and symbol at the same time, but that doesn't help me
> either.
Right. So what you have to do is detect (programmatically) the difference
between () at toplevel of a list and (rest '(something)) ... with some study
you'll notice that the former occurs in the car of some list while the latter
occurs only in the cdr. So if your program doesn't have some way (explicit
or implicit) to notice that distinction, a mere testing for NIL will not be
adequate to distinguish the cases. I hope this is enough to move you along
without totally trivializing the exercise.
On 19 Apr 2008 15:56:20 -0400, Kent M Pitman <······@nhplace.com>
wrote:
>> Still I don't get it. I keep thinking that there is no difference
>> between () and say (rest '(something)).
>> I undersand that () is the same as '(), nil and 'nil and that it is of
>> type list, atom and symbol at the same time, but that doesn't help me
>> either.
>
>Right. So what you have to do is detect (programmatically) the difference
>between () at toplevel of a list and (rest '(something)) ... with some study
>you'll notice that the former occurs in the car of some list while the latter
>occurs only in the cdr. So if your program doesn't have some way (explicit
>or implicit) to notice that distinction, a mere testing for NIL will not be
>adequate to distinguish the cases. I hope this is enough to move you along
>without totally trivializing the exercise.
Thank you, it is very clear, but after some still inconclusive and
confused attempts to find a solution i decided to go through Pascal's
long explanation. So tomorrow I'll have something to think about.
"An[z]elmus" <·······@somewhere.org> writes:
> On Sat, 19 Apr 2008 18:15:01 +0200, Pascal Bourguignon
> <···@informatimago.com> wrote:
>
>>Not at all. I want you to realize something about () that would allow
>>you to implement flatten02 easily.
>
> Still I don't get it. I keep thinking that there is no difference
> between () and say (rest '(something)).
> I undersand that () is the same as '(), nil and 'nil and that it is of
> type list, atom and symbol at the same time, but that doesn't help me
> either.
However, it should.
(defun flatten (tree)
(typecase tree
(null '())
(atom (list tree))
(t (append (flatten (first tree)) (flatten (rest tree))))))
(defun flatten02 (tree)
(typecase tree
(atom (list tree))
(t (append (flatten02 (first tree)) (flatten02 (rest tree))))))
(mapcar (lambda (f) (funcall f '(a () b)))
(list (function flatten) (function flatten02)))
--> ((A B) (A NIL B NIL))
Now why do we get (A NIL B NIL) instead of (A NIL B)?
That's because you made a little mistake: you're actually processing
trees of cons cells, instead of lists. (Nonwithstanding the use of
first and rest instead of car and cdr).
(defun flatten-list (list)
"Returns a list of all the elements in the LIST and its sub-lists"
(mapcan (lambda (element)
(if (atom element)
(list element)
(flatten-list element)))
list))
(mapcar (lambda (l) (flatten-list l))
'( () (nil) (a) (a b c) (a nil b nil c)
(()) ((nil)) ((a)) ((a b c)) ((a nil b nil c))
((((a b)) (c d)) (((e f) (g) ((h i))) j)) ))
--> (NIL (NIL) (A) (A B C) (A NIL B NIL C)
(NIL) (NIL) (A) (A B C) (A NIL B NIL C)
(A B C D E F G H I J))
(mapcar (lambda (f) (funcall f '(a () b)))
(list (function flatten) (function flatten02)
(function flatten-list)))
--> ((A B) (A NIL B NIL) (A NIL B))
If you want to have a purely recursive solution, you must consider
that you will have to recurse for two reasons:
1- one recursion to process each element of the list,
2- one recursion to process the sublists.
This renders the recursive solution slightly more complex than the
hybrid flatten-list above.
(defun flatten-list-rec (list)
(cond
((endp list) ; we consider NIL a list, not an atom.
'())
((atom (first list)) ; note the difference from flatten
;; but we consider a NIL element an atom...
(cons (first list)
(flatten-list-rec (rest list))))
(t
(append (flatten-list-rec (first list))
(flatten-list-rec (rest list))))))
(every (function identity)
(mapcar (lambda (l) (equal (flatten-list-rec l)
(flatten-list l)))
'( () (nil) (a) (a b c) (a nil b nil c)
(()) ((nil)) ((a)) ((a b c)) ((a nil b nil c))
((((a b)) (c d)) (((e f) (g) ((h i))) j))
((((a b)) (c d)) (((e f) (g) ((h i))) j)) )))
--> T
The main difference between flatten-list-rec and your flatten, is that
since flatten processes trees, it may have either nodes or leaves
(conses or atoms) as parameter, and must choose to treat NIL either as
a list or an element, while flatten-list-rec only takes a list as
argument. There, NIL is taken as (), an empty list. Only when NIL
appears as an element of the list (as (first list)), is it considered
as an atom. Both three recursive calls are always made on lists,
never on atoms.
--
__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.
thus spoke Pascal Bourguignon <···@informatimago.com>:
>>>Not at all. I want you to realize something about () that would allow
>>>you to implement flatten02 easily.
>> Still I don't get it. I keep thinking that there is no difference
>> between () and say (rest '(something)).
>> I undersand that () is the same as '(), nil and 'nil and that it is of
>> type list, atom and symbol at the same time, but that doesn't help me
>> either.
> However, it should.
> (defun flatten (tree)
> (typecase tree
> (null '())
> (atom (list tree))
> (t (append (flatten (first tree)) (flatten (rest tree))))))
~~~~~~ ~~~~~~~ ~~~~~~~
Not trying to nitpick on the conversation or to lecture anyone, but
that's a really bad habit to teach a newbie. Why not show how tail
consing works and use that?
--
Nawet świnka wejdzie na drzewo kiedy ją chwalą.
On Sun, 20 Apr 2008 10:42:27 +0000 (UTC), Stanis?aw Halik
<··············@tehran.lain.pl> wrote:
>> (defun flatten (tree)
>> (typecase tree
>> (null '())
>> (atom (list tree))
>> (t (append (flatten (first tree)) (flatten (rest tree))))))
> ~~~~~~ ~~~~~~~ ~~~~~~~
>
>Not trying to nitpick on the conversation or to lecture anyone, but
>that's a really bad habit to teach a newbie. Why not show how tail
>consing works and use that?
Being the newbie here, I don' t know exactly what you mean by "tail
consing". Maybe it is a synonym for "tail recursion", which I don't
understand very well too yet. But sometimes when you want to answer
some particular question about a snip of code it is a good choice to
modify the code itself just the necessary to clear the point.
"An[z]elmus" <·······@somewhere.org> writes:
> On Sun, 20 Apr 2008 10:42:27 +0000 (UTC), Stanis?aw Halik
> <··············@tehran.lain.pl> wrote:
>>> (defun flatten (tree)
>>> (typecase tree
>>> (null '())
>>> (atom (list tree))
>>> (t (append (flatten (first tree)) (flatten (rest tree))))))
>> ~~~~~~ ~~~~~~~ ~~~~~~~
>>
>>Not trying to nitpick on the conversation or to lecture anyone, but
>>that's a really bad habit to teach a newbie. Why not show how tail
>>consing works and use that?
>
> Being the newbie here, I don' t know exactly what you mean by "tail
> consing". Maybe it is a synonym for "tail recursion", which I don't
> understand very well too yet. But sometimes when you want to answer
> some particular question about a snip of code it is a good choice to
> modify the code itself just the necessary to clear the point.
Don't worry. This is an optimization question. First, make your
algorithm correct. Then, if there's a space or speed problem, think
about optimizing it.
About recursive solutions, Common Lisp doesn't mandate tail call
optimization like Scheme. However, most CL implementation do
implement tail call optimization, at least in the compiler, and at
least with high (speed or space), (or rather low debug) optimization
levels.
Nonetheless, some recursive algorithm just aren't tail recursions.
Notably, when you have more than one recursive call, all but the last
may not be tail calls. That means that stack space will be used, to
memorize the recursive frames. Moreover, flatten builds a new list,
with the call to (LIST tree), and the results of the recursive calls
are combined with APPEND which copies all but the last arguments,
which means that there will be at least a multiplicative factor of N
on the time and space complexity of the algorithm.
But as I said, if the algorithm is wrong there's no need to think
about complexities.
If the algorithm is correct, but the data is small, there's still no
need to think about complexities.
If the algorithm is correct, the data is big, but you're not in a
hurry to get the result and you have enough memory, there's still no
need to think about the complexities.
Only when the algorithm is correct, and the data is big, and you want
to get the result fast or you don't have enough memory, then you may
start to think about the complexities.
In the case of flatten, you could remove one recursion (the one that
processes the elements of the list). The other recursion couldn't be
removed, because it's essential to the problem (we're processing
recursive lists). That is, we could remove it by using an explicit
stack, which is about the same. On some systems, there is more heap
space than stack space, so if your trees are very very deep, it might
be worthwhile to switch to using a heap allocated stack instead of the
processor stack.
For an example of the first recursion removed, see my irst
flatten-list function, using MAPCAN. Contrarily to APPEND, MAPCAN
concatenates the lists returned by the function modifying them all
(but the last). Then the only space used is in O(deepth(tree)).
Alternatively, you could replace APPEND by NCONC, to avoid the copying
APPEND does, but this would still leave space complexity in
O(number_of_atom+max(deepth(tree),deepth(length(sublist)))).
--
__Pascal Bourguignon__ http://www.informatimago.com/
In deep sleep hear sound,
Cat vomit hairball somewhere.
Will find in morning.
From: Robert Maas, http://tinyurl.com/uh3t
Subject: Re: The empty list and the end of a list
Date:
Message-ID: <rem-2008apr27-004@yahoo.com>
> From: Pascal Bourguignon <····@informatimago.com>
> First, make your algorithm correct. Then, if there's a space or
> speed problem, think about optimizing it.
I agree almost completely, but there's a problem even before
correctness of algorithm, namely correctness of statement of the
original problem to solve. In another article of this thread I
pointed out that the problem statement conflates three intentions
of a data structure:
- Single-level linked list, where *every* item in CAR position at
that top level is an element, even what would otherwise be
considered a sub-list.
- Multi-level linked list, where NIL in a CAR position, at *any*
level, is an empty list, not an element, but other items in CAR
position at *any* level are elements at that level.
- CONS-tree, where CAR and CDR position are treated equally, but
only non-CONS items are ever treated as elements.
Until the original statement of the problem is clarified to say
which of those intentions of the CONS-based structure are intended,
it makes no sense to ask which two algorithms are *correct* for two
of those three interpretations.
Now if that mistake in problem statement can ever be solved, then I
mostly agree with what you say next:
> If the algorithm is correct, but the data is small, there's still no
> need to think about complexities.
> If the algorithm is correct, the data is big, but you're not in a
> hurry to get the result and you have enough memory, there's still no
> need to think about the complexities.
> Only when the algorithm is correct, and the data is big, and you want
> to get the result fast or you don't have enough memory, then you may
> start to think about the complexities.
One caveat: If you can clearly see that your algorithm is
unnecessarily order(n**2) or worse, but you're postponing fixing
that until you really need the speed, please put a comment near
that function warning future YOUs of the slow algorithm, so that if
you set this code aside for months then come back to it and try to
apply it to a large dataset you will see that comment and *expect*
it might be too slow for sufficiently large datasets. And if you
*do* have time to fix the algorithm to be efficient, while still
*correct*, might as well do that before you set aside the code. And
if you happen to think of two equally simple algorithms in the
first place, and one is obviously much faster than the other, you
might as well implement the fast version instead of the slow
version and never have to worry about speed and never have to
comment your code as deliberately slow.
As for showing newbies how to code, I say:
- First make sure the problem statment is unambiguous.
- Second make sure you have *some* way to correctly solve the
problem, but if you can think of two equally simple ways then
try to pick the fastest algorithm if you can quickly figure out
what that is, but don't fuss over speed at the expense of
distracting you from getting it correct.
- Third, it's fine for the experts to suggest faster algorihms,
after the newbie has found at least *one* way to solve the
problem correctly although slowly. It's good for the newbie to
realize the difference between a unnecessarily slow algorithm
and a reasonably fast algorithm. But only *third*, after the
more urgent matters first and second.
With experience, no longer newbie, the software programmer should
just "know" at the start of coding a new algorithm what techniques
are reasonably fast and which are unnecessarily slow. Learning to
think of reasonably efficient algorithms from the very start is one
mark of an experienced programmer. But still, even as an expert,
don't **worry** about speed when first trying to make a problem
statement correctly and then an algorithm correct for that problem.
Beyond all that, when working with large datasets hence really
*needing* to speed up the algorithm as well as make it fit
resources:
> On some systems, there is more heap space than stack space, so if
> your trees are very very deep, it might be worthwhile to switch to
> using a heap allocated stack instead of the processor stack.
Correct. But don't worry about this until and unless you actually
encounter a stack overflow, because emulating recursion by
explicitly manipulating a linked-list emulation of a stack can be
somewhat messy code in some cases.
However if you keep your trees reasonably balanced all the time,
then the depth is order(log(n)) so you'd need a tree consuming all
the RAM in the Universe before the depth would exceed even a
hundred, so stack overflow when doing recursion ought to indicate
either you are using a grossly unbalanced tree or you are using
recursion to emulate iteration, each of which has a fix simpler
than emulating a stack via linked list.
"An[z]elmus" <·······@somewhere.org> wrote in message
·······································@4ax.com...
> On Sun, 20 Apr 2008 10:42:27 +0000 (UTC), Stanis?aw Halik
> <··············@tehran.lain.pl> wrote:
>>> (defun flatten (tree)
>>> (typecase tree
>>> (null '())
>>> (atom (list tree))
>>> (t (append (flatten (first tree)) (flatten (rest tree))))))
>> ~~~~~~ ~~~~~~~ ~~~~~~~
>>
>>Not trying to nitpick on the conversation or to lecture anyone, but
>>that's a really bad habit to teach a newbie. Why not show how tail
>>consing works and use that?
>
> Being the newbie here, I don' t know exactly what you mean by "tail
> consing". Maybe it is a synonym for "tail recursion", which I don't
> understand very well too yet. But sometimes when you want to answer
> some particular question about a snip of code it is a good choice to
> modify the code itself just the necessary to clear the point.
Tail consing is adding new list elements in sequence by destructively
modifying the cdr of the last cons. It's efficient, but the code to make it
work is more complex than your append solution.
Experienced lisp programmers try to avoid append when possible because it
always allocates a fresh list. The solution above can be made more
space-efficient by replacing (append ...) with (nconc ...), which
destructively modifies the last cdr of each nconc'ed list except the last.
This is always okay in this code because it allocates fresh cons cells at
the leaves of the tree with (list ...). The original tree will not be
modified.
Still, nconc has to traverse the first nconc'ed list to find the last cdr.
The good news about this problem is you can avoid extra consing, extra list
traversal, and explicit tail-consing if you just think about the problem
differently. It's a general technique that's worth learning: Accumulate
the result tail-first in an extra parameter. Due to the tail-first order,
we want to visit tree elements cdr first:
CL-USER> (defun flatten (tree &optional result-tail)
(typecase tree
(null result-tail)
(cons (flatten (car tree)
(flatten (cdr tree) result-tail)))
(t (cons tree result-tail))))
FLATTEN
CL-USER> (flatten '(a (b c) ((d) e (f g (h)))))
(A B C D E F G H)
The "outer" recursive call to flatten is indeed tail-recursive, so it's as
efficient as a loop with most compilers.
If you see how this works, then, as an exercise, code a quicksort that uses
the same technique to avoid nconc and append, returning a sorted list
without modifying an original unsorted one.
As others have mentioned, flatten-2 is only different in that cars that are
nil must show up as nils in the result list. There are a couple of nice
ways to code this, but I'll let you figure them out.
Gene <··············@frontiernet.net> wrote:
+---------------
| Tail consing is adding new list elements in sequence by destructively
| modifying the cdr of the last cons. It's efficient, but the code to
| make it work is more complex than your append solution.
+---------------
True, but most LOOP implementations do tail-consing for the COLLECT
clause when they can, so if you can cast your task into LOOP's COLLECT
syntax the performance is often quite good. E.g., in CMUCL [I'm using
WALKER:MACROEXPAND-ALL here since plain MACROEXPAND leaves a bunch of
internal macros unexpanded]:
> (walker:macroexpand-all
'(loop for item in list
when (plus item)
collect item))
(BLOCK NIL
(LET ((ITEM NIL) (#:G1583 LIST))
(DECLARE (TYPE LIST #:G1583))
(LET* ((#:G1584 (LIST NIL)) (#:G1585 #:G1584))
(TAGBODY
ANSI-LOOP::NEXT-LOOP
(IF (ENDP #:G1583)
(PROGN
NIL
(GO ANSI-LOOP::END-LOOP))
NIL)
(SETQ ITEM (CAR #:G1583))
(SETQ #:G1583 (CDR #:G1583))
(IF (PLUS ITEM) (RPLACD #:G1585 (SETQ #:G1585 (LIST ITEM))))
(GO ANSI-LOOP::NEXT-LOOP)
ANSI-LOOP::END-LOOP
(RETURN-FROM NIL (CDR #:G1584))))))
>
Note the tail-consing in the 4th line from the bottom.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
I don't want to spoil the exercise because I think it is an
illuminating one, but I'll plunge in because compound types
provide a nice way of thinking about the issue.
Consider that
CL-USER> (subtypep t '(or cons atom))
T
T
and also
CL-USER> (subtypep 'cons '(or (cons cons cons)
(cons atom cons)
(cons cons atom)
(cons atom atom)))
T
T
Given that
CL-USER> (defun flatten (tree)
(etypecase tree
(null ())
(atom (list tree))
(cons
(append (flatten (first tree))
(flatten (rest tree))))))
FLATTEN
doesn't do quite what we want, dropping the empty lists
CL-USER> (flatten '(a () b (c () d)))
(A B C D)
let us break out the CONS into four cases, enjoying the
transgressive thrill of cutting and pasting code
CL-USER> (defun flatten (tree)
(etypecase tree
(null ())
(atom (list tree))
((cons cons cons)
(append (flatten (first tree))
(flatten (rest tree))))
((cons atom cons)
(append (flatten (first tree))
(flatten (rest tree))))
((cons cons atom)
(append (flatten (first tree))
(flatten (rest tree))))
((cons atom atom)
(append (flatten (first tree))
(flatten (rest tree))))))
FLATTEN
Now we have more fine-grained control over how the recursion
proceeds and the question is how to use it.
Alan Crowe
Edinburgh
Scotland
From: Robert Maas, http://tinyurl.com/uh3t
Subject: Re: The empty list and the end of a list
Date:
Message-ID: <rem-2008apr27-003@yahoo.com>
> From: "An[z]elmus" <·······@somewhere.org>
> I keep thinking that there is no difference between () and say
> (rest '(something)).
Your language is sloppy. You need to talk like you clearly
understand the difference between what you type in, the result of
READing that, the result of EVALuating *that*, and finally what
gets printed out. Those are four different things, first and last
are strings of text, s-expressions or reader macros for such,
and the middle two are internal structures.
Even if you conflate the print-form from the internal-form, still
you really really *must* distinguish between what goes into EVAL
and what comes out from EVAL.
() externally represents internally the NIL atom, which is
interpreted by some functions as an empty list, by some other
functions as boolean false, by some other functions as a symbol
with print-name "NIL", by some other functions as a constant
variable (as opposed to a literal constant). I'll draw that symbol
like this:
+------------------+
| symbol |
| printName: "NIL" |
+------------------+
(rest '(something))
reads in the same as if you had typed
(rest (quote (something)))
and reading either results in a rather complicated internal structure:
+---+---+ +---+---+ +------------------+
| | | | | | | symbol |
| V | >>>>>>>| V | >>>>>>| printName: "NIL" |
| V | | | V | | +------------------+
+-V-+---+ +-V-+---+ ^ ^
V V ^ ^
V +---+---+ +---+---+ ^ ^
V | | | | | | ^ ^
V | V | >>>>>>>| V | >>>>>/ ^
V | V | | | V | | ^
V +-V-+---+ +-V-+---+ ^
V V V ^
V V V ^
V V +---+---+ ^
V V | | | ^
V V | V | >>>>>>>/
V V | V | |
V V +-V-+---+
V V V
V V V
V V +------------------------+
V V | symbol |
V V | printname: "SOMETHING" |
V V +------------------------+
V V
V +--------------------+
V | symbol |
V | printname: "QUOTE" |
V | functionCell: >>>>>>>><Byte function C::SPECIAL-FORM-FUNCTION {50E55C9}>
V +--------------------+
V
V
+-------------------+
| symbol |
| printName: "REST" |
| functionCell: >>>>>>>>><Function REST {12B2831}>
+-------------------+
As you can see, those two are not even remotely the same.
But when you pass the former (the bare NIL atom) through EVAL, it
immediately evaluates to itself, by fiat that started with Lisp 1.5
or maybe even earlier.
And when you evaluate the later (that huge structure I spent a half
hour drawing), the first element of that toplevel linked-list,
namely the symbol REST, is looked up as a function name, retrieving
<Function REST {12B2831}>.
Then EVAL is recursively called on the second element of the
toplevel list, the semi-big structure containing links to symbols
QUOTE SOMETHING and NIL. It sees that the first element of *that*
linked-list is the special operator QUOTE, so it does the special
thing, namely returning the second element of that second-level
list, namely the third-level list containg links only to symbols
SOMETHING and NIL. The toplevel eval now applies that function
<Function REST {12B2831}> to that single parameter which is the
third-level list, so it takes the CDR of that list, which is the
atom NIL, which happens to be the same return value from the
trivial evaluation of the previous paragraph.
Using external notation, no diagrams, we can summarize all that:
Input: Result of EVAL:
NIL NIL
(rest (quote (something))) NIL
If that's what you meant to say, you should have expressed it more
clearly so we knew that's what you meant.
NIL and (rest (quote (something))) are *not* the same thing,
but passing each through EVAL the results are the same.
> I undersand that () is the same as '(), nil and 'nil and that it
> is of type list, atom and symbol at the same time, but that doesn't
> help me either.
I'm quite sure you are utterly confused. Here's the truth (no diagrams):
Typed: After READ: After EVAL: What prints out:
() the atom NIL the atom NIL NIL
'() the list (QUOTE NIL) the atom NIL NIL
nil the atom NIL the atom NIL NIL
'nil the list (QUOTE NIL) the atom NIL NIL
You really need to understand what goes into EVAL vs. what comes out,
and not write as if you believed that the two were the same.
You really need to understand how the read-eval-print loop works,
i.e. how read and print are convert in opposite directions between
external and internal form, and how eval works. To help you, I
suggest you start just with read and print alone, without any eval.
Copy&paste this into your Common Lisp:
(loop (format t "~&What next? ") (finish-output)
(let ((e (read)))
(format t "~S is of type ~S.~%" e (type-of e))))
then try typing stuff at it, for example:
What next? x
X is of type SYMBOL.
What next? ()
NIL is of type NULL.
What next? '()
'NIL is of type CONS.
What next? (rest '(something))
(REST '(SOMETHING)) is of type CONS.
What next? (a . (b . (c . d)))
(A B C . D) is of type CONS.
Now abort from that and copy&paste this into your Common Lisp:
(defun toString (x)
(if (consp x) (format nil "(~A . ~A)" (toString (car x)) (toString (cdr x)))
(format nil "~S" x)))
(loop (format t "~&What next? ") (finish-output)
(let ((e (read)))
(format t "~A is of type ~S.~%" (toString e) (type-of e))))
Then type the same sort of stuff into that as you did before.
I bet this will be a lot more enlightening!! For example:
What next? x
X is of type SYMBOL.
What next? ()
NIL is of type NULL.
What next? '()
(QUOTE . (NIL . NIL)) is of type CONS.
What next? (rest '(something))
(REST . ((QUOTE . ((SOMETHING . NIL) . NIL)) . NIL)) is of type CONS.
What next? (a . (b . (c . d)))
(A . (B . (C . D))) is of type CONS.
What next? (A B C D)
(A . (B . (C . (D . NIL)))) is of type CONS.
Now after you are sure you understand how READ and PRINT work
(format ... ~A ... (tostring x) ...) is a simplified version of (print x)
abort from that and try this:
(loop (format t "~&What next? ") (finish-output)
(let ((e (read)))
(format t "~A is of type ~S.~%" (toString e) (type-of e))
(format t "=> ") (finish-output)
(format t "~A~%" (toString (eval e)))))
Again type that stuff into it, but be careful:
What next? ()
NIL is of type NULL.
=> NIL
What next? '()
(QUOTE . (NIL . NIL)) is of type CONS.
=> NIL
What next? (rest '(something))
(REST . ((QUOTE . ((SOMETHING . NIL) . NIL)) . NIL)) is of type CONS.
=> NIL
What next? x
X is of type SYMBOL.
=>
Error in KERNEL::UNBOUND-SYMBOL-ERROR-HANDLER: the variable X is unbound.
Does any of that help you to *really* understand what's going on,
and how to write to show that you *do* indeed really understand it?
·················@SpamGourmet.Com (Robert Maas, http://tinyurl.com/uh3t) writes:
> [...]
> I'm quite sure you are utterly confused. Here's the truth (no diagrams):
> Typed: After READ: After EVAL: What prints out:
> () the atom NIL the atom NIL NIL
> '() the list (QUOTE NIL) the atom NIL NIL
> nil the atom NIL the atom NIL NIL
> 'nil the list (QUOTE NIL) the atom NIL NIL
Let's introduce some more confusion:
C/USER1[29]> (shadow '(nil))
T
C/USER1[30]> '()
COMMON-LISP:NIL
C/USER1[31]> 'nil
NIL
C/USER1[32]> (symbol-package 'nil)
#<PACKAGE USER1>
C/USER1[33]> (symbol-package '())
#<PACKAGE COMMON-LISP>
C/USER1[34]>
Unless you change the reader macro for #\(, "()" always reads as
CL:NIL. How "NIL" is read depends on what symbol is interned nor not
in the current package with that name.
Also, while you get the same thing when you evaluate CL:NIL and
'CL:NIL, the processes are different.
When you evaluate CL:NIL, eval fetches the value of the symbol CL:NIL,
which happens to be the symbol CL:NIL, which just happens to be the
symbol CL:NIL itself!
When you evaluate 'CL:NIL, eval doesn't do anything but returning the
CL:NIL that's in the second position of that form. Yes, it's the
symbol CL:NIL, but eval doesn't care about it.
So you're lucky, it works with CL:NIL, but of course, you wouldn't get
the same in general. Only CL:NIL, CL:T and the keywords have
automatically as value themselves. For the other symbols you would
have to set them yourself.
(defvar *a* '*a*)
(eq *a* '*a*) --> T
(defvar *b* 'hi)
(eq *b* '*b*) --> NIL
--
__Pascal Bourguignon__ http://www.informatimago.com/
Litter box not here.
You must have moved it again.
I'll poop in the sink.
From: Robert Maas, http://tinyurl.com/uh3t
Subject: Re: The empty list and the end of a list
Date:
Message-ID: <rem-2008may01-005@yahoo.com>
> From: Pascal Bourguignon <····@informatimago.com>
> Let's introduce some more confusion:
> C/USER1[29]> (shadow '(nil))
> T
> C/USER1[30]> '()
> COMMON-LISP:NIL
Aha, with COMMON-LISP:NIL no longer imported into USER package, now
when in the USER package the package name is required to identify
the symbol, so when it's printed readably (default mode in REP) the
package name is printed with it. And as for why () is identical to
COMMON-LISP:NIL, you explain that later below.
> C/USER1[31]> 'nil
> NIL
A brand new symbol with the same print-name created in the USER
package when you type it in right there.
> C/USER1[32]> (symbol-package 'nil)
> #<PACKAGE USER1>
> C/USER1[33]> (symbol-package '())
> #<PACKAGE COMMON-LISP>
Indeed, that is merely confirming the hypothesis I stated above.
(Side remark: This is how science is done, and science-mode is
common in my work with Lisp, and it's nice to see you do it too.)
> Unless you change the reader macro for #\(, "()" always reads as
> CL:NIL.
Of course you mean COMMON-LISP:NIL. Or maybe not. Doing an experiment...
(find-package "COMMON-LISP")
#<The COMMON-LISP package, 1511/2119 internal, 989/1242 external>
(find-package "CL")
#<The COMMON-LISP package, 1511/2119 internal, 989/1242 external>
so you really did mean COMMON-LISP, but CL is a nickname for it.
While we're at it:
(find-package "USER")
#<The COMMON-LISP-USER package, 0/9 internal, 0/9 external>
So when I mentionned the USER package above, I was also using a
nickname instead of the actual package name. I guess we were both
sloppy in that trivial way.
More science:
(package-nicknames (find-package "COMMON-LISP"))
("LISP" "CL")
(package-nicknames (find-package "COMMON-LISP-USER"))
("USER" "CL-USER")
Aside: You can use a string too if you're lazy:
(package-nicknames "COMMON-LISP")
("LISP" "CL")
> How "NIL" is read depends on what symbol is interned nor not in
> the current package with that name.
Yes. That's the "sound bite" for the info&evidence presented above.
<ot>"A day like today, it's not a day for soundbites: we can leave
those at home".</ot>
(I discovered that gem while searching for correct spelling: b[i|y]te.)
> Also, while you get the same thing when you evaluate CL:NIL and
> 'CL:NIL, the processes are different.
Yes, I think I covered that in my original REP-for-dummies article
to which you replied.
> When you evaluate CL:NIL, eval fetches the value of the symbol
> CL:NIL, which happens to be the symbol CL:NIL, which just happens
> to be the symbol CL:NIL itself!
Well, not exactly "just happens". It's specified the ANSI standard
that the value of COMMON-LISP:NIL must be itself, regardless of how
this is accomplished internally. (One possible implementation
technique is to put that symbol in a read-only page of RAM and trap
the exception which occurs if anybody tries to modify it.)
> When you evaluate 'CL:NIL, eval doesn't do anything but returning
> the CL:NIL that's in the second position of that form. Yes, it's
> the symbol CL:NIL, but eval doesn't care about it.
Yes, essentially correct. Actually, after the read macro for
apostrophe constructs the (QUOTE COMMON-LISP:NIL)
list-of-two-elements, next EVAL checks whether the symbol QUOTE has
a function or other interesting definition, discovers it is a
special operator (CAR of special form), and dispatches to the
appropriate handler, and *that* handler is what actually takes the
CADR of the form and returns it. Alternately with JIT (Just In
Time) compiler, EVAL per se isn't actually called, instead
JIT-compiler is called to produce a block of machine code (or JVM
bytecode in some implementations), which is basically two
instructions, one to fetch the symbol COMMON-LISP:NIL into a
register or onto the stack and one to return it from there to
caller. But the effect is *as*if* EVAL had noticed that QUOTE was a
special operator and dispatched to the specialized code for that
type of form.
You're correct, and enlightening to newbies, that EVAL (or JIT
alternative) doesn't care what it is, anything in the CADR of that
form gets immediately returned. I suppose if somebody could go into
a machine debugger and clobber that place to have an invalid
pointer, *that* would be returned without complaint, and only later
when the Print part of the REP tried to print it, *then* AHWBL.
[snipped the fine tutorial on how only CL:NIL, CL:T and the
keywords have automatically as value themselves]
Hmm, at this point I was going to say something, that would turn
out to be a horrible gaffe, that NIL/T and keywords are different
that only the former can take property lists. But I did a little
experiment and learned I was wrong, all of them can take property
lists:
(symbol-plist 'nil)
NIL
(setf (get 'nil :FOO) :BAZ)
:BAZ
(symbol-plist 'nil)
(:FOO :BAZ)
(symbol-plist 't)
NIL
(setf (get 't :A) :B)
:B
(symbol-plist 't)
(:A :B)
(symbol-plist :NIL)
NIL
(setf (get :NIL :EGG) :SALAD)
:SALAD
(symbol-plist :NIL)
(:EGG :SALAD)
That was a surprise to me. Maybe someday I'll take advantage of
that new knowledge in my application software, or not.
Anyway I thank you for posting the info about the possible effects
of shadowing COMMON-LISP:NIL, which I didn't include in my article
because I never do anything dumb like that
(shadowing **essential** symbols normally exported from
COMMON-LISP to COMMON-LISP-USER)
so I never have to deal with the consequences, so consequences of
doing something so perverse aren't at the front of my mind when I'm
explaining things to newbies.
From: Kent M Pitman
Subject: Re: The empty list and the end of a list
Date:
Message-ID: <ulk2t6vkc.fsf@nhplace.com>
·················@SpamGourmet.Com (Robert Maas, http://tinyurl.com/uh3t) writes:
> > From: Pascal Bourguignon <····@informatimago.com>
> > Let's introduce some more confusion:
> > C/USER1[29]> (shadow '(nil))
> > T
> > C/USER1[30]> '()
> > COMMON-LISP:NIL
>
> Aha, with COMMON-LISP:NIL no longer imported into USER package, now
> when in the USER package the package name is required to identify
> the symbol, so when it's printed readably (default mode in REP) the
> package name is printed with it.
I don't recommend doing this in the actual CL-USER package, since many
packages use CL-USER to get a foothold and usually expect it to have the
basic set of common lisp symbols there. But it's fine to do in personally
owned packages if you like the effects.
> Hmm, at this point I was going to say something, that would turn
> out to be a horrible gaffe, that NIL/T and keywords are different
> that only the former can take property lists.
Yes, but you're still well advised when using a shared package like keyword
to make sure the indicators you use are private to a non-public package
(that is, not CL symbols, for example). Similar restrictions are made on
the CL package.
Kent M Pitman <······@nhplace.com> writes:
> ·················@SpamGourmet.Com (Robert Maas, http://tinyurl.com/uh3t) writes:
>
>> > From: Pascal Bourguignon <····@informatimago.com>
>> > Let's introduce some more confusion:
>> > C/USER1[29]> (shadow '(nil))
>> > T
>> > C/USER1[30]> '()
>> > COMMON-LISP:NIL
>>
>> Aha, with COMMON-LISP:NIL no longer imported into USER package, now
>> when in the USER package the package name is required to identify
>> the symbol, so when it's printed readably (default mode in REP) the
>> package name is printed with it.
>
> I don't recommend doing this in the actual CL-USER package, since many
> packages use CL-USER to get a foothold and usually expect it to have the
> basic set of common lisp symbols there. But it's fine to do in personally
> owned packages if you like the effects.
Yes, that's why I've got this little MKUPACK utility function in
http://darcs.informatimago.com/public/lisp/common-lisp/interactive.lisp
>> Hmm, at this point I was going to say something, that would turn
>> out to be a horrible gaffe, that NIL/T and keywords are different
>> that only the former can take property lists.
>
> Yes, but you're still well advised when using a shared package like keyword
> to make sure the indicators you use are private to a non-public package
> (that is, not CL symbols, for example). Similar restrictions are made on
> the CL package.
--
__Pascal Bourguignon__
·················@SpamGourmet.Com (Robert Maas, http://tinyurl.com/uh3t) writes:
>> From: Pascal Bourguignon <····@informatimago.com>
>> When you evaluate CL:NIL, eval fetches the value of the symbol
>> CL:NIL, which happens to be the symbol CL:NIL, which just happens
>> to be the symbol CL:NIL itself!
>
> Well, not exactly "just happens". It's specified the ANSI standard
> that the value of COMMON-LISP:NIL must be itself, regardless of how
> this is accomplished internally. (One possible implementation
> technique is to put that symbol in a read-only page of RAM and trap
> the exception which occurs if anybody tries to modify it.)
Correct, it could be implemented differently.
> Anyway I thank you for posting the info about the possible effects
> of shadowing COMMON-LISP:NIL, which I didn't include in my article
> because I never do anything dumb like that
> (shadowing **essential** symbols normally exported from
> COMMON-LISP to COMMON-LISP-USER)
> so I never have to deal with the consequences, so consequences of
> doing something so perverse aren't at the front of my mind when I'm
> explaining things to newbies.
Well sometimes you want a really clean package, not even importing CL
symbols, to put there some alien [ "English" ;-) ] symbols that may
collide with those found in CL. For example, a package containing
keywords from the C programming language. C:DO is not CL:DO. Or
words from the English language, ENGLISH:CAR is not CL:CAR.
(defpackage "ENGLISH" (:use)) or (defpackage "C" (:use))
Shadowing is a partial cleanup.
--
__Pascal Bourguignon__
On Apr 19, 12:38=A0am, "An[z]elmus" <·······@somewhere.org> wrote:
> At page 124 of "Common Lisp An Interactive Approach" there is an
> exercise where it is requested to write the function FLATTEN that
> takes a list (tree) as input and returns a list of all atoms.
> It is also requested to write two versions of the function so that:
>
> (flatten '(a () b)) =A0----> (A B)
>
> and
>
> (flatten02 '(a () b)) =A0----> (A NIL B)
Of course, the input (A () B) list actually has two NIL-s in in it,
because it's equiavlent to the following dot notation:
(a . (nil . (b . nil))
The embedded NIL differs from the ending NIL in its syntactic
position: it is in the first position of the cons, CAR, rather than
the rest position, CDR.
Your first flatten function makes no distinction between the two. If
you give it the input (nil . nil), which is not a NULL, and not an
ATOM, but a CONS, it will jump right to the fallback case T and
recurse on FIRST and REST. So it will call (APPEND (FLATTEN NIL)
(FLATTEN NIL)), which will evaluate to (APPEND NIL NIL) which
evaluates to NIL. Both NIL-s are treated as equal citizens of the
tree.
This is the beauty of plain recursion: that the same process is
uniformly and consistently applied to substructures of the input.
> (defun flatten (tree)
> (typecase tree
> (null ())
> (atom (list tree))
> (t (append (flatten (first tree)) (flatten (rest tree))))))
>
> How do I write FLATTEN02 ?
The second flavor of this function, one which preserves the embedded
NIL atoms, rather than flattening them as if they denoted empty lists,
must differ from the first one in that its fallback case can't just
perform plain recursion on first and rest and then integrate the
results by APPEND.
Our funtion can't detect the difference between the two kinds of NIL
as an incoming object. That is to say, if the TREE argument coming
into the function is NIL, we don't know if the application program
really has an empty tree, whether we are called recursively on (FIRST
TREE), or whether we are recursively handling (REST TREE). There is no
context information to tell us what the situation is. That context
information could be added via an additional optional parameter, whose
default value is NIL:
(defun flatten-02 (tree &optional first-position-p)
(typecase tree
(null nil)
(atom (list tree))
(t (append (flatten-02 (first tree) t)
(flatten-02 (rest tree)))))
When we recurse on (FIRST TREE) we specify this parameter as T, so now
the function knows, whenever it is handling a CONS or ATOM, that it
came from the first position in a recursive call (or else the
application program knows about this additional argument and is taking
advantage of it to change the function's behavior).
The function still doesn't do whatwe want, but now it has the
information in the extra argument so that we can add logic to the
TYPECASE. What logic will that be?
Well, essentially, if FIRST-POSITION-P is true, then we can't treat
NIL as an empty list. We have to treat it as if it were any other
atom.
If we just return NIL, that NIL will disappear in the APPEND
operation above, so we must not do that:
(typecase tree
(null (if first-position-p (list nil) nil))
(atom (list tree))
...)
If we used COND instead of TYPECASE, testing the value rather than the
type, it could be expressed like this:
(cond
((and (null tree) (not first-position-p)) nil)
((atomp tree) (list tree))
(t ...))
In this version it is clear that a null is only treated as empty if it
is not in the first position. In the first/CAR position, the logic
falls through to the next case. And since NIL is a kind of ATOM
(since anything which is not a CONS is an ATOM!) it matches this
second case, and so (LIST NIL) is returned. The nice thing here is
that all atoms, including NIL when treated as an ordinary atom,
go through the same case.
> (defun touretzky-flatten (tree)
> (cond ((atom tree) (list tree))
> (t (append (touretzky-flatten (car tree))
> (touretzky-flatten (cdr tree))))))
As you can see, this is just like our COND above, but with the test
for a null tree completely removed (and no second parameter to
distinguish the situation). So any null tree is handled by the ATOM
case: in other words, all NIL-s are treated as atoms and not as empty
lists.
> CL-USER 5 : 1 > (touretzky-flatten '((A B (R)) A))
> (A B R NIL NIL A NIL)
Right, so again it helps to write this list out in fully expanded dot
notation:
(A . (B . (R . (NIL . (NIL . (A . (NIL . NIL)))))))
If you erase the dots and parentheses (except the outermost two), you
get the same text representation as what pops out of touretzky-
flatten.
All the NIL objects in the input tree are represented as items in the
output list.
Of course, the output list has its own additional NIL at the end,
which is normally invisible in the printed representation:
(A B R NIL NIL A NIL . NIL)
So if you were to call touretzky-flatten on it, you would get:
(A B R NIL NIL A NIL NIL)
touretzky-flatten is not stable in the sense of achieving a fixed
point under iteration over itself. If it's given an already flat list,
it extends it by an extra NIL.
On Mon, 21 Apr 2008 09:25:46 -0700 (PDT), Kaz Kylheku
<········@gmail.com> wrote:
> (defun flatten-02 (tree &optional first-position-p)
> (typecase tree
> (null (if first-position-p (list nil) nil))
> (atom (list tree))
> ...)
The version of FLATTEN02 you propose is very clear too, and we don't
need to change strategy, that is we still treat the list as a tree of
cons and atoms instead of a list of lists (of lists of ...).
>> CL-USER 5 : 1 > (touretzky-flatten '((A B (R)) A))
>> (A B R NIL NIL A NIL)
>
>Right, so again it helps to write this list out in fully expanded dot
>notation:
>
> (A . (B . (R . (NIL . (NIL . (A . (NIL . NIL)))))))
And the following should represent the list '((A B (R)) A) in dot
notation (is it correct?):
'((A . (B . ((R . nil) . nil))) . ( A . nil))
which shows the three otherwise invisible list-ending empty lists.
On Apr 22, 3:21 am, "An[z]elmus" <·······@somewhere.org> wrote:
> On Mon, 21 Apr 2008 09:25:46 -0700 (PDT), Kaz Kylheku
>
> <········@gmail.com> wrote:
> > (defun flatten-02 (tree &optional first-position-p)
> > (typecase tree
> > (null (if first-position-p (list nil) nil))
> > (atom (list tree))
> > ...)
>
> The version of FLATTEN02 you propose is very clear too, and we don't
> need to change strategy, that is we still treat the list as a tree of
> cons and atoms instead of a list of lists (of lists of ...).
>
> >> CL-USER 5 : 1 > (touretzky-flatten '((A B (R)) A))
> >> (A B R NIL NIL A NIL)
>
> >Right, so again it helps to write this list out in fully expanded dot
> >notation:
>
> > (A . (B . (R . (NIL . (NIL . (A . (NIL . NIL)))))))
>
> And the following should represent the list '((A B (R)) A) in dot
> notation (is it correct?):
>
> '((A . (B . ((R . nil) . nil))) . ( A . nil))
>
> which shows the three otherwise invisible list-ending empty lists.
Exactly. So it's "first" or "car" elements (left of dot) being nil
that are the interesting case for flatten-2.
Someone pointed out a very powerful capability of (typecase ) to do
the detection of this case. Modifying my earlier code, it's just:
(defun flatten (tree &optional result-tail)
(typecase tree
(null result-tail)
((cons null *) ... )
(cons (flatten (car tree)
(flatten (cdrtree) result-tail)))
(t (cons tree result-tail))))
You just need to fill in the ... to make a complete solution.
On Thu, 24 Apr 2008 07:52:46 -0700 (PDT), Gene
<············@gmail.com> wrote:
>Someone pointed out a very powerful capability of (typecase ) to do
>the detection of this case. Modifying my earlier code, it's just:
>
>(defun flatten (tree &optional result-tail)
> (typecase tree
> (null result-tail)
> ((cons null *) ... )
> (cons (flatten (car tree)
> (flatten (cdrtree) result-tail)))
> (t (cons tree result-tail))))
>
>You just need to fill in the ... to make a complete solution.
(defun flatten02 (tree &optional result-tail)
(typecase tree
(null result-tail)
((cons null *) (cons (car tree)
(flatten02 (cdr tree) result-tail)))
(cons (flatten02 (car tree)
(flatten02 (cdr tree) result-tail)))
(t (cons tree result-tail))))
... but I guessed after a few attempts. :-)
On Thu, 24 Apr 2008 07:52:46 -0700 (PDT), Gene
<············@gmail.com> wrote:
>Someone pointed out a very powerful capability of (typecase ) to do
>the detection of this case. Modifying my earlier code, it's just:
>
>(defun flatten (tree &optional result-tail)
> (typecase tree
> (null result-tail)
> ((cons null *) ... )
> (cons (flatten (car tree)
> (flatten (cdrtree) result-tail)))
> (t (cons tree result-tail))))
>
>You just need to fill in the ... to make a complete solution.
(defun flatten02 (tree &optional result-tail)
(typecase tree
(null result-tail)
((cons null *) (cons (car tree)
(flatten02 (cdr tree) result-tail)))
(cons (flatten02 (car tree)
(flatten02 (cdr tree) result-tail)))
(t (cons tree result-tail))))
... but I guessed after a few attempts. :-)
On Thu, 24 Apr 2008 12:16:02 -0700 (PDT), danb <·········@gmail.com>
wrote:
>Here's another one:
>
>(defun flatten (x)
> (cond ((atom x) (list x))
> ((not (cdr x)) (flatten (car x)))
> (...
And this show me how easy and uncomplicated it was after all.
An[z]elmus <·······@somewhere.org> wrote:
> And this show me how easy and uncomplicated it was after all.
It's possible to solve both your initial problems using pretty much the
same code.
(labels ((frob (thing test)
(if (funcall test thing)
(mapcan (lambda (item) (frob item test)) thing)
(list thing))))
(defun flatten (thing) (frob thing #'listp))
(defun flatten02 (thing) (frob thing #'consp)))
-- [mdw]
From: Robert Maas, http://tinyurl.com/uh3t
Subject: Re: The empty list and the end of a list
Date:
Message-ID: <rem-2008apr27-002@yahoo.com>
> From: "An[z]elmus" <·······@somewhere.org>
> At page 124 of "Common Lisp An Interactive Approach" there is an
> exercise where it is requested to write the function FLATTEN that
> takes a list (tree) as input and returns a list of all atoms.
IMO that book is poorly written, because for the purpose of this
exercise a list and a tree are *not* equivalent. Furthermore a
simple list and a hierarchial list are different in a subtle way.
Your test data is expressed as: (a () b)
but internally it's really (a . (nil . (b . nil)))
and dotted notation is the correct way to view it as a (binary) tree.
As a tree, it has two NILs as *elements*, each of which is an atom.
As a simple list, it has one NIL as an *element*, which is an atom.
The NIL that ends the list is part of the essential structure that
makes a proper list, not an element, so it doesn't count.
As a hierarchial list, it doesn't have any NIL at all, because the
leftmost NIL is interpreted as an empty list hierarchially lower
than the main list, *not* as an atomic element, and the rightmost
NIL is still treated as part of the essential structure, so neither
counts as an atom per that interpretation of the sloppy spec.
Thus the book is doubly wrong, conflating the concept of (binary)
tree and list, and conflating a simple list (where NIL is an
element) and a nested list (where NIL is simply an empty
lower-level list).
> It is also requested to write two versions of the function so that:
> (flatten '(a () b)) ----> (A B)
That's obviously the nested-list interpretation.
> (flatten02 '(a () b)) ----> (A NIL B)
That could be either the simple-list or binary-tree interpretation,
assuming you're supposed to remove duplicates from the set before
returning. It would require different test data to clearly tell
which interpretation was wanted. If this is TDD (test-driven
development), you could write flatten02 per *either* interpretation
and be correct. The better test data would verify your code or
force modification to satisfy the new test.
What should this return?
(flatten02 '(a x b)) ----> (A X B NIL) ;tree
(A X B) ;simple list
What should this return?
(flatten02 '(a (x y) b)) ----> (A B) ;simple list
(A X Y NIL B) ;tree, NIL at end of (x y) seen
; before NIL at end of main list
(A X Y B) ;multi-level list
Note that the last test there contradicts the earlier decision that
flatten uses multi-level list while flatten02 uses either simple
list or tree. The only way to reconcile that is to devise yet a
fourth interpretation of the structure, such as where empty lists
aren't allowed except as terminators of non-empty lists, thus NIL
in CAR position must be treated as atom rather than empty list.
If we allow that interpretation, we now have four interpretations
hence we need not two, not even three, but *four* different flatten
functions to handle all the interpretation-cases.
The author of that book, and the instructor who assigned that
problem without warning you, both need to be spanked. If you are
working independently, then *you* need to be spanked for accepting
that problem statement as unflawed and asking us for help with it.
IMO You should have started your post "I believe this problem
statement is fishy, because it conflates at least three different
intentions of the same data structure, yet asks only for two
different functions per those three intentions, which is logically
impossible. Do y'all agree it's flaky, or am I mistaken?"
P� Sun, 27 Apr 2008 09:53:25 +0200, skrev Robert Maas,
http://tinyurl.com/uh3t <·················@SpamGourmet.Com>:
I fail to see how flatten could have any meaning on anything but a nested
list.
Thus nil is () and not a element in any list. If you HAVE to have a
equivalent of nil how about the keyword :unspecific? Thus you can easily
change it to a simple list by
(mapcar (lambda (e) (if (eq e :unspesific) nil e) nlist)
and simular for the reverse case.
--------------
John Thingstad
From: Robert Maas, http://tinyurl.com/uh3t
Subject: Re: The empty list and the end of a list
Date:
Message-ID: <rem-2008may02-004@yahoo.com>
> From: "John Thingstad" <·······@online.no>
> I fail to see how flatten could have any meaning on anything but
> a nested list.
Or a tree also? You mean either a tree or a nested list, but not a
one-level list, right? Flatten of a nested dotted list turns out to
be identical to flatten of a tree. Flatten of a one-level dotted
list might be a third possible meaning, but that's a bit perverse.
Given that CAR doesn't mean automobile, nor even trailer being
pulled by a locomotive, it means left half of an ordered pair, we
can't really expect names of functions to adequately say what they
really do. But I agree you have a point in this case. Perhaps two
meanings of "flatten" are sufficient after all. On the other hand,
if identical (EQ) objects appear more than one place in the nested
list or tree where they ought to be considered elements to be
included in the flattened result, should each appear just once or
as many times as they appear? Also, assuming they appear as many times
as they appear, should they appear in the output per depth-first
or breadth-first search? Thus if given:
(a b c * e f g h * j)
| |
V V
(2 4 8) (41 43 47)
should the result be:
(a b c 2 4 8 e f g h 41 43 47 j)
or
(a b c e f g h j 2 4 8 41 43 47)
> Thus nil is () and not a element in any list.
Under the nested-list intent, I agree.
Under the tree-of-CONS-cells intent, it's less clear.
Per some/most binary tree designs, NIL is used to denote a missing leaf,
and should *not* count as an element.
But per some other binary tree designs, NIL is perfectly good as a leaf.
For example, in a binary-decoding tree, NIL might be used to
represent the escape node which is not explicitly encoded.
Or for that matter, NIL might actually represent itself! For
example, a explicit Huffman-code tree for all the constants in a
program might include the constants NIL and T.
I think maybe the book should have given BNF for each of the two
intents. For example:
<tree> ::= (<tree> . <tree>)
| <anythingExceptAConsCell>
<list> ::= <emptyList>
| (<list> . <list>)
| (<anythingExceptNilOrAConsCell> . <list>)
<emptyList> ::= NIL
Flatten is then required to return list of <anythingExceptAConsCell>
per the first BNF or <anythingExceptAConsCellOrNil> per the
second BNF.
P� Sat, 03 May 2008 07:47:04 +0200, skrev Robert Maas,
http://tinyurl.com/uh3t <·················@SpamGourmet.Com>:
>> From: "John Thingstad" <·······@online.no>
>> I fail to see how flatten could have any meaning on anything but
>> a nested list.
>
> Or a tree also? You mean either a tree or a nested list, but not a
> one-level list, right? Flatten of a nested dotted list turns out to
> be identical to flatten of a tree. Flatten of a one-level dotted
> list might be a third possible meaning, but that's a bit perverse.
>
I wrote this a while ago, but I think the thought was that you usually
make something in the structure of a tree for a reason. Like a balanced
search tree say. So in most cases 'nested list' is the abstraction you
would want to 'flatten'. Technically they are identical, but not
semantically.
--------------
John Thingstad