Newbie stumped on list element manipulation.
John Jaynes
I am a student, trying to figure out how to perform a one argument
operation on individual list elements, returning a list with the same
level structure:
(ImHosed #'numberp '((1) ((a)) 3 4 (b))) -> returns ((T) ((NIL)) T
T (NIL))
I am not sure if this a suitable post for this group. Apologies if this
is not.
Moronically,
John
Erik Naggum
You should say something about what you have tried. For instance, do you
know of a function that maps over the cars of a list? Do you know of a
function that find the first non-cons car of a cons?
///
--
The United Nations before and after the leadership of Kofi Annan are two
very different organizations. The "before" United Nations did not deserve
much credit and certainly not a Nobel peace prize. The "after" United
Nations equally certainly does. I applaud the Nobel committee's choice.
Kent M Pitman
I'ts a fine post. Identifying that you are a student is good. Is this
a homework assignment? The reason I ask is that it would help to see the
exact text of the homework assignment. Your description above uses
terminology that is not very clear. For a newbie trying to learn, that's
common--it takes a while to get terms right. But if the terminology comes
straight from the instructor, then I disagree that the terms you used is a
good way of describing the problem you're showing. (In the latter case,
please share this post with the instructor and have that person email me
or join this discussion if they disagree.)
A list is an asymmetric VIEW on data made of conses. It has a set of
elements (extending out of the left half of each cons) and a backbone
(made of the right half of each cons). The elements are the things pointed
to by the left half of the backbone, regardless of whether those things
are atoms or conses. A picture may help:
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | | | | | | | / |
| * | *---->| * | *---->| * | *---->| * | *---->| * | / |
| | | | | | | | | | | | | | | | | | | / |
+--+--+-----+ +--+--+-----+ +--+--+-----+ +--+--+-----+ +--+--+-----+
| | | | |
v v v v v
(1) ((a)) 3 4 (b)
As such, the ONLY elements of the list you're giving to ImHosed are:
(a), ((a)), 3, 4, (b)
So if you're going to do something to list elements here, those are the
arguments you would give.
Another VIEW on the same data structure is a symmetric view called a tree.
In this view, the right and left hand of the tree are symmetric and you
descend until some test succeeds, which is usually (ATOM x) => true, which
is the same as (CONSP x) => false. In that view, the identical structure
((1) ((a)) 3 4 (b)) is best seen as
.
/ \
/ \
/ \
/ \
/ \
/ \
/ \
. .
/ \ / \
/ \ / \
/ \ / \
/ \ / \
A NIL . .
/ \ / \
. NIL 3 .
/ \ / \
A NIL 4 .
/ \
. NIL
/ \
B NIL
The role of the items in this tree are not elements of any list. In
this view, there are not lists. In a tree, there are only more trees
(sometimes called "branches") and "leaves", which are the terimination
condition (in this case, atoms). The data structure has not changed,
which you can kind of see by looking the right edge (which is the
backbone in the list VIEW). However, understanding which mode you are
in is critical to understanding the nature of the recursion you will
be doing.
(One hint of this, if you want to do some deep thought about this, is
that in a list view, the empty list NIL really does not appear in your
example; it is an artifact of the backbone composition of each list,
but none of your lists have NIL's in them. Yet in a tree view, the
NIL's become data because they are not serving the function of
backbone structure and they are suddenly manifest data to be
confronted. They are there in both cases, but if you walk through (we
call it "mapping over") lists, even recursively descending other lists
that are elements of a given list, you will not find any NIL's in the
list data you have supplied for your example. HOWEVER, if you descend
the identical structure you described as if it were a tree of conses,
you will find NIL's.)
It may be that this pictorial view helps you see the recursion you
need to do. If not, probably someone else will respond from here with
help on that. But, in any case, I just wanted to help you with the
terminology. Because ((1) ((a)) 3 4 (b)) is not a list of 1, a, 3, 4,
and b with a bunch of parens in the way. It is a list of containing 3
lists and 2 numbers (not in that order). Lists are recursive
structures only to the right (along the backbone) and not to the left
(into the element). The same structure can be viewed as a tree, which
is a recursive structure in both directions, car and cdr. Your tree
contains 8 "subtrees" or "branches", and terminating at 10 atoms (5
unique atoms, some duplicated, like A and NIL).
Using the right terminology, once you understand that terminology,
will keep you from getting confused. I'm sure it's daunting now. But
it's well worth taking the time with.
Kent M Pitman
> John Jaynes <fat...@aracnet.com> writes:
>
> > I am a student, trying to figure out how to perform a one argument
> > operation on individual list elements, returning a list with the same
> > level structure:
> >
> > (ImHosed #'numberp '((1) ((a)) 3 4 (b))) -> returns ((T) ((NIL)) T
> > T (NIL))
> >
> > I am not sure if this a suitable post for this group. Apologies if this
> > is not.
...
> Using the right terminology, once you understand that terminology,
> will keep you from getting confused. I'm sure it's daunting now. But
> it's well worth taking the time with.
One more thing before someone calls me on it:
The right way of restating your problem is that you want to write a
function, though probably you mean "several cooperating functions",
which takes two arguments: a function and a list. For each list
element (this phrase "for each" alerts you to an iteration or
recursion, depending on the taste of your teacher, down the backbone
of the list), you want to test if the element is an atom. If it is,
you want to call your function. Otherwise, you will view the element
as a subproblem (this suggests a recursion) of the first problem, a new
list whose elements will either be atoms or lists.
Recursive programs happen because you have recursive data. Nothing in your
original problem description suggests a recursive data pattern, and that's
what's wrong with the wording. Once you acknowledge that the elements might
be recursive instantiations of the original problem, it should be much easier
to see how to solve this. Maybe not totally easy. But easier.
Carl Shapiro
Kent M Pitman
Heh. Politely put. I hope you know the answer to your own question.
(Yes.) Sorry.
Thomas F. Burdick
> A list is an asymmetric VIEW on data made of conses. It has a set of
> elements (extending out of the left half of each cons) and a backbone
> (made of the right half of each cons). The elements are the things pointed
> to by the left half of the backbone, regardless of whether those things
> are atoms or conses. A picture may help:
Not surprisingly, there are a lot of posts to gnu.emacs.help by people
who are very confused as to how lists and conses work. Since this is
*such* a FAQ, Alex Schroeder wrote up a page on the Emacs Wiki about
list modification that would be equally helpful here:
<http://www.emacswiki.org/cgi-bin/wiki.pl?ListModification>
> +-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
> | | | | | | | | | | | | | | / |
> | * | *---->| * | *---->| * | *---->| * | *---->| * | / |
> | | | | | | | | | | | | | | | | | | | / |
> +--+--+-----+ +--+--+-----+ +--+--+-----+ +--+--+-----+ +--+--+-----+
> | | | | |
> v v v v v
>
> (1) ((a)) 3 4 (b)
The Emacs wiki page includes several pretty pictures (drawn with
Emacs, of course) :)
Jeff Sandys
>
> (ImHosed #'numberp '((1) ((a)) 3 4 (b)))
> -> returns ((T) ((NIL)) T T (NIL))
Learn about CAR, or FIRST, CDR, or REST, and CONS
(cons (car thing) (cdr thing)) -> thing
The commom idiom to explore a tree is this:
IDS(5): (defun explore-tree (tree)
(if (atom tree) tree ; do something with atoms here
(cons (explore-tree (car tree)) (explore-tree (cdr tree)))))
EXPLORE-TREE
IDS(6): (explore-tree '((1) ((a)) 3 4 (b)))
((1) ((A)) 3 4 (B))
Good luck in your Lisp class,
Jeff Sandys