The empty list and the end of a list - lisp

On Apr 24, 1:15 pm, "An[z]elmus" <some...@somewhere.org> wrote:
> (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. :-)

Here's another one:

(defun flatten (x)
(cond ((atom x) (list x))
((not (cdr x)) (flatten (car x)))
(t (append (flatten (car x))
(flatten (cdr x))))))

CL-USER> (flatten '(a b () (c d ()) e))
(A B NIL C D NIL E)

--Dan

------------------------------------------------
Dan Bensen
http://www.prairienet.org/~dsb/

On Thu, 24 Apr 2008 12:16:02 -0700 (PDT), danb <sogwaldan@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 <someone@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: "An[z]elmus" <some...@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?"

> From: "An[z]elmus" <some...@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?

lisp1.3.CalRobert@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.

På Sun, 27 Apr 2008 09:53:25 +0200, skrev Robert Maas,
http://tinyurl.com/uh3t <lisp1.3.CalRobert@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: Pascal Bourguignon <p...@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.

> From: Pascal Bourguignon <p...@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.