(defun enumerate-nodes (nodes &optional (count 0))
"Performs left-handed depth first enumeration of nodes in a tree"
(if (listp nodes)
(let ((lhs (enumerate-nodes (cadr nodes) (1+ count))))
(list count lhs
(enumerate-nodes (caddr nodes) (1+ (get-last-number lhs)))))
count))
(defun get-last-number (list)
(if (listp list)
(get-last-number (car (last list)))
list))
> (enumerate-nodes '(a (d f h) (c d (e g h)))) => (0 (1 2 3) (4 5 (6 7 8)))
Given that any list will have exactly three members. I have been trying to
work this one out. I thought as I don't know lisp that well I should try to
avoid things like multiple-value-bind until I better understand where/how to
use it. My main source of irritation is the second function IMHO I should be
able to keep track of the count without having to calculate it every time a
call returns.
Any suggestions?
Thanks.
Charlie
"Charlie" <········@zoom.co.uk> wrote in message ····················@ID-155962.news.dfncis.de...
> (defun enumerate-nodes (nodes &optional (count 0))
> "Performs left-handed depth first enumeration of nodes in a tree"
> (if (listp nodes)
> (let ((lhs (enumerate-nodes (cadr nodes) (1+ count))))
> (list count lhs
> (enumerate-nodes (caddr nodes) (1+ (get-last-number lhs)))))
> count))
>
> (defun get-last-number (list)
> (if (listp list)
> (get-last-number (car (last list)))
> list))
>
> > (enumerate-nodes '(a (d f h) (c d (e g h)))) => (0 (1 2 3) (4 5 (6 7 8)))
>
> Given that any list will have exactly three members. I have been trying to
> work this one out. I thought as I don't know lisp that well I should try to
> avoid things like multiple-value-bind until I better understand where/how to
> use it. My main source of irritation is the second function IMHO I should be
> able to keep track of the count without having to calculate it every time a
> call returns.
> Any suggestions?
> Thanks.
> Charlie
You can do the following to number the nodes of any tree in
left-to-right depth-first order with consecutive integers starting
from a given integer, 0 by default:
(defun df-numbering (tree &optional (start 0))
(labels ((df-numbering-aux (tree)
(cond ((null tree)
nil)
((atom tree)
(prog1
start
(incf start)))
(t
(cons (df-numbering-aux (car tree))
(df-numbering-aux (cdr tree)))))))
(df-numbering-aux tree)))
Regards,
jag
Thank-you, that's perfect and I learned a couple of new keywords! (labels
and prog1)
"John Gilson" <···@acm.org> wrote in message
·························@twister.nyc.rr.com...
> You can do the following to number the nodes of any tree in
> left-to-right depth-first order with consecutive integers starting
> from a given integer, 0 by default:
>
> (defun df-numbering (tree &optional (start 0))
> (labels ((df-numbering-aux (tree)
> (cond ((null tree)
> nil)
> ((atom tree)
> (prog1
> start
> (incf start)))
> (t
> (cons (df-numbering-aux (car tree))
> (df-numbering-aux (cdr
tree)))))))
> (df-numbering-aux tree)))
>
> Regards,
> jag
>
"Charlie" <········@zoom.co.uk> wrote in message news:<···············@ID-155962.news.dfncis.de>...
> (defun enumerate-nodes (nodes &optional (count 0))
> "Performs left-handed depth first enumeration of nodes in a tree"
> (if (listp nodes)
> (let ((lhs (enumerate-nodes (cadr nodes) (1+ count))))
> (list count lhs
> (enumerate-nodes (caddr nodes) (1+ (get-last-number lhs)))))
> count))
>
> (defun get-last-number (list)
> (if (listp list)
> (get-last-number (car (last list)))
> list))
>
> > (enumerate-nodes '(a (d f h) (c d (e g h)))) => (0 (1 2 3) (4 5 (6 7 8)))
I would do this by writing a MAPTREE function, which works like MAPCAR
but recurses down nested lists. So for instance:
(maptree #'(lambda (num) (* 10 num))) '(1 2 (3 4 (5 6) 7)))
==> (10 20 (30 40 (50 60) 70))
And then:
;; substitute consecutive integers for tree items, starting from
zero.
(let* ((count -1)
(number-tree (maptree #'(lambda (item)
(declare (ignore item))
(incf count))
input-tree)))
;; okay, now you have the last value in COUNT, and the
substituted
;; tree in NUMBER-TREE.
)
Reader exercise: write MAPTREE. Or if you are smart, steal it from the
open source of some Lisp program. ;)
"Kaz Kylheku" <···@ashi.footprints.net> wrote in message
································@posting.google.com...
> I would do this by writing a MAPTREE function, which works like MAPCAR
> but recurses down nested lists.
> Reader exercise: write MAPTREE. Or if you are smart, steal it from the
> open source of some Lisp program. ;)
Like this? I'm trying to learn so I wrote it myself.
(defun maptree (func &rest lists)
(labels ((maptree-aux (lists-aux)
(print lists-aux)
(cond ((null (car lists-aux)) '())
((listp (car lists-aux))
(cons (maptree-aux (mapcar 'car lists-aux))
(maptree-aux (mapcar 'cdr lists-aux))))
(t (apply func lists-aux)))))
(maptree-aux lists)))
(let ((count -1))
(maptree #'(lambda (item)
(declare (ignore item))
(incf count))
'(a b c (d (e f (g) h i) j ) k)))
=>
(0 1 2 (3 (4 5 (6) 7 8) 9) 10)
Ah ha now I've learned every and error it just gets better and better.
I'm a little confused by (apply #'mapcar ...) rather than just (mapcar
... ) ? I tried it with the latter and it failed. I had a look at the
hyperspec for apply which suggested (mapcar #'new-fn (list* item items)) to
me (in a vague way) but that also failed.
Is (apply #'some-func 'a '(b c d)) <=> (some-func 'a 'b 'c 'd) in which case
what happens when you want to actually pass your function a list e.g. (apply
#'cons 'a '(b c d)).
<some head scratching and experimentation later>
Here's what I understand/assume so far:
1) mapcar has a &rest argument which means it will gather the &rest of its
args into a list. The (list* item items) approach doesn't work because then
mapcar only sees one list and (mapcar #'fn item items) doesn't work because
&rest becomes (list item items) not (list item (nth items 0) (nth items 1)
...).
2) Apply is needed because it separates the args out automatically allowing
&rest to collect them into a list it understands as a collection of
arguments rather than just a normal list.
3) You would use funcall in my last example: e.g. (funcall 'cons 'a '(b c
d))
Is this even nearly correct?
Cheers
Charlie.
"Coby Beck" <·····@mercury.bc.ca> wrote in message
··················@otis.netspace.net.au...
>
> One small comment: mapcar requires at least one list, yours will not
> complain if there isn't even one. That said, here's another crack at it:
>
> (defun maptree (fn tree1 &rest trees)
> (labels ((new-fn (item &rest items)
> (cond ((every #'listp (list* item items))
> (apply #'mapcar #'new-fn item items))
> ((every #'atom (list* item items))
> (apply fn item items))
> (t (error "mis-matched structure in maptree args")))))
> (apply #'mapcar #'new-fn tree1 trees)))
>
> --
> Coby Beck
> (remove #\Space "coby 101 @ bigpond . com")
"Charlie" <········@zoom.co.uk> wrote in message ····················@ID-155962.news.dfncis.de...
> "Coby Beck" <·····@mercury.bc.ca> wrote in message
> ··················@otis.netspace.net.au...
> >
> > One small comment: mapcar requires at least one list, yours will not
> > complain if there isn't even one. That said, here's another crack at it:
> >
> > (defun maptree (fn tree1 &rest trees)
> > (labels ((new-fn (item &rest items)
> > (cond ((every #'listp (list* item items))
> > (apply #'mapcar #'new-fn item items))
> > ((every #'atom (list* item items))
> > (apply fn item items))
> > (t (error "mis-matched structure in maptree args")))))
> > (apply #'mapcar #'new-fn tree1 trees)))
> >
> > --
> > Coby Beck
> > (remove #\Space "coby 101 @ bigpond . com")
>
> Ah ha now I've learned every and error it just gets better and better.
> I'm a little confused by (apply #'mapcar ...) rather than just (mapcar
> ... ) ? I tried it with the latter and it failed. I had a look at the
> hyperspec for apply which suggested (mapcar #'new-fn (list* item items)) to
> me (in a vague way) but that also failed.
No, still need apply
(apply #'mapcar #'new-fn (list* item items))
> Is (apply #'some-func 'a '(b c d)) <=> (some-func 'a 'b 'c 'd) in which case
> what happens when you want to actually pass your function a list e.g. (apply
> #'cons 'a '(b c d)).
You switch to funcall
(funcall #'cons 'a '(b c d))
> <some head scratching and experimentation later>
> Here's what I understand/assume so far:
> 1) mapcar has a &rest argument which means it will gather the &rest of its
> args into a list. The (list* item items) approach doesn't work because then
> mapcar only sees one list and (mapcar #'fn item items) doesn't work because
> &rest becomes (list item items) not (list item (nth items 0) (nth items 1)
> ...).
Yes, but what &rest does to the arguments is immaterial unless you are
writing the function. When I call (foo 3 4 5 6) it doesn't matter to me
whether it is written (defun foo (&rest args)... or (defun foo (a b c d)...
as long as foo takes 4 arguments. In this case we have
(apply mapcar #'new-fn tree-1 '(tree-2 ... tree-n))
== (mapcar #'fn tree-1 tree-2 ... tree-n)
(mapcar #'new-fn (list* tree-1 '(tree-2 ... tree-n)))
== (mapcar #'fn '(tree-1 tree-2 ... tree-n))
> 2) Apply is needed because it separates the args out automatically allowing
> &rest to collect them into a list it understands as a collection of
> arguments rather than just a normal list.
Yes, but once again talking about what &rest does just complicates things.
Here's the example w/o &rest:
(defun foo (a b c d)
(* a (+ b c d)))
==> FOO
(foo 3 4 5 6)
==> 45
(funcall #'foo 3 4 5 6)
==> 45
(apply #'foo '(3 4 5 6))
==> 45
(apply #'foo 3 '(4 5 6))
==> 45
(apply #'foo 3 4 '(5 6))
==> 45
> 3) You would use funcall in my last example: e.g. (funcall 'cons 'a '(b c
> d))
> Is this even nearly correct?
>
I assume 'cons was a typo and you meant #'cons.
I'd just write
(cons 'a '(b c d)) ;-)
But yes, that's correct. Just think of how you would call the function
ordinarily then look at what you have to pass.
Here's an old chestnut, it made my head hurt the first time I saw it :-)
(defun transpose (matrix-as-list-of-lists)
(apply #'mapcar #'list matrix-as-list-of-lists))
==> TRANSPOSE
(transpose '((1 2) (3 4) (5 6)))
==> ((1 3 5) (2 4 6))
--
Geoff
"Geoffrey Summerhayes" <·············@hotmail.com> wrote in message
························@news20.bellglobal.com...
> "Charlie" <········@zoom.co.uk> wrote in message
····················@ID-155962.news.dfncis.de...
> > <some head scratching and experimentation later>
> > Here's what I understand/assume so far:
> > 1) mapcar has a &rest argument which means it will gather the &rest of
its
> > args into a list. The (list* item items) approach doesn't work because
then
> > mapcar only sees one list and (mapcar #'fn item items) doesn't work
because
> > &rest becomes (list item items) not (list item (nth items 0) (nth items
1)
> > ...).
>
> Yes, but what &rest does to the arguments is immaterial unless you are
> writing the function. When I call (foo 3 4 5 6) it doesn't matter to me
> whether it is written (defun foo (&rest args)... or (defun foo (a b c
d)...
> as long as foo takes 4 arguments. In this case we have
I just figure that if I can understand &rest from both directions it would
be beneficial and without knowing what &rest does it's difficult to figure
out why the above examples fail.
> (defun transpose (matrix-as-list-of-lists)
> (apply #'mapcar #'list matrix-as-list-of-lists))
> ==> TRANSPOSE
>
> (transpose '((1 2) (3 4) (5 6)))
> ==> ((1 3 5) (2 4 6))
>
> --
> Geoff
>
Thank-you but after today transpose makes sense immediately. I suspect
yesterday it would have generated the same set of questions as maptree with
all the associated hair pulling.
Cheers
Charlie.
"Geoffrey Summerhayes" <·············@hotmail.com> wrote in message
························@news20.bellglobal.com...
> "Charlie" <········@zoom.co.uk> wrote in message
····················@ID-155962.news.dfncis.de...
> > 3) You would use funcall in my last example: e.g. (funcall 'cons 'a '(b
c
> > d))
> > Is this even nearly correct?
> >
> I assume 'cons was a typo and you meant #'cons.
FWIW, using 'cons or #'cons in this context is a style issue, not a
correctness issue. There has been some good discussion of this here a few
times. This thread has some of it:
http://groups.google.com/groups?threadm=arkcq0%242d5m%241%40otis.netspace.ne
t.au
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
"Charlie" <········@zoom.co.uk> wrote in message news:<···············@ID-155962.news.dfncis.de>...
> Ah ha now I've learned every and error it just gets better and better.
> I'm a little confused by (apply #'mapcar ...) rather than just (mapcar
> ... ) ? I tried it with the latter and it failed. I had a look at the
Apply is needed because the number of trees is variable. There is a
&rest parameter coming in which needs to be ``canceled out'' by apply.
> hyperspec for apply which suggested (mapcar #'new-fn (list* item items)) to
> me (in a vague way) but that also failed.
> Is (apply #'some-func 'a '(b c d)) <=> (some-func 'a 'b 'c 'd) in which case
> what happens when you want to actually pass your function a list e.g. (apply
> #'cons 'a '(b c d)).
This problem does not arise, because apply is used in situations when
you already have a list, and you want that list to be broken into
individual trailing arguments in a function call. For added
convenience, apply lets you specify some additional parameters before
the list which become leading arguments to that function.
You shouldn't abuse apply: if the list is too long, it may violate
your Lisp
system's limitation on the number of arguments.
The most common use for apply is to serve as a kind of antidote to
&rest when you need to pass down your variable arguments to a lower
function:
(defun higher-function (arg &rest args)
(apply #'lower-function 'extra 'stuff args))
> <some head scratching and experimentation later>
> Here's what I understand/assume so far:
> 1) mapcar has a &rest argument which means it will gather the &rest of its
> args into a list.
Correct, but what it does with that list is hidden in its
implementation. All you care about as the mapcar user is that it takes
a variable number of lists: at least one, but possibly more. Elements
are taken from these lists in parallel and turned into arguments for
your function. So you get a zipper effect with two lists:
(mapcar #'list '(a b c d) '(1 2 3 4))
will call (list 'a 1) then (list 'b 2) and so on, and collect the
results into a list, resulting in:
((A 1) (B 2) (C 3) (D 4))
The function has to take as many arguments as there are lists. MAPCAR
stops when the shortest of the lists runs out.
> The (list* item items) approach doesn't work because then
The LIST* function is a kind of CONS on steroids. (LIST* X Y) is
equivalent to (CONS X Y). But it lets you stick in additional cells,
so that instead of writing:
(cons 'a (cons 'b 'c))
you can write
(list* 'a 'b 'c)
Get it? The difference between list* and list is that its last
argument specifies the CDR field of the last cons cell, allowing you
to make an improper list, or to build a longer list out of a shorter
one by consing a bunch of elements at the front:
(list* 'a 'b 'c '(d e f)) ==> (A B C D E F)
Lastly, LIST* can be called with just one argument, in which case it
just produces it as its result.
Thus
(mapcar #'new-fn (list* item items))
means to take the list called ITEMS, create a new list which is like
ITEMS but additionally has ITEM at the front, and then this list
becomes just one argument to MAPCAR.
But note that:
(apply #'function (list* item items))
is the same as:
(apply #'function item items)
Because APPLY, in a way, has the LIST* functionality built in: it
effectively tacks on the individual pieces to the front of the list
and then breaks that into arguments for the function to be called.
> mapcar only sees one list and (mapcar #'fn item items) doesn't work because
> &rest becomes (list item items) not (list item (nth items 0) (nth items 1)
> ...).
> 2) Apply is needed because it separates the args out automatically allowing
> &rest to collect them into a list it understands as a collection of
> arguments rather than just a normal list.
No, the function calling mechanism already does this. You don't need
APPLY to call a variadic function. You need APPLY if you have list,
which you need to break into individual arguments for a function,
which may or may not have a &rest parameter. Often APPLY is used in
conjuction with a captured &rest list, to bounce it down to another
function.
I'm not sure why Coby used LIST* in his example; the inner function
can just be written:
(new-fn (&rest items))
I think he did this for consistency with the outer interface, which
insists on thre being at least one tree. At no point in the inner
NEW-FN is the first item needed by itself; it is always used with
LIST* or APPLY to combine it into the &REST ITEMS. So I think we can
rewrite it as:
(defun maptree (fn tree1 &rest trees)
(labels ((new-fn (&rest items)
(cond ((every #'listp items)
(apply #'mapcar #'new-fn items))
((every #'atom items)
(apply fn items))
(t (error "mis-matched structure in maptree
args")))))
(apply #'mapcar #'new-fn tree1 trees)))
The whole reason for keeping the separate tree1 and trees in the outer
function is because it provides for error checking; you are required
to pass in at least one tree. If this were not checked, then the error
would be called when calling MAPCAR which requires at least one list!
The user would get a ``mysterious'' error from MAPCAR, which she did
not call directly, and would then have to deduce that it's because an
insufficient number of arguments was passed to MAPTREE.
"Kaz Kylheku" <···@ashi.footprints.net> wrote in message
·································@posting.google.com...
> I'm not sure why Coby used LIST* in his example; the inner function
> can just be written:
>
> (new-fn (&rest items))
It probably just didn't occur to him...
> I think he did this for consistency with the outer interface, which
> insists on thre being at least one tree.
But this is what it will say in the press release! ;-)
> At no point in the inner
> NEW-FN is the first item needed by itself; it is always used with
> LIST* or APPLY to combine it into the &REST ITEMS. So I think we can
> rewrite it as:
>
> (defun maptree (fn tree1 &rest trees)
> (labels ((new-fn (&rest items)
> (cond ((every #'listp items)
> (apply #'mapcar #'new-fn items))
> ((every #'atom items)
> (apply fn items))
> (t (error "mis-matched structure in ~
maptree args")))))
> (apply #'mapcar #'new-fn tree1 trees)))
Looks good. Now I hadn't considered the way mapcar accepts list of
differing lengths. Though come to think of it, this will Just Work.
CL-USER 11 > (maptree #'+ '(1 (1 1 1)) '(1 (1 1)))
(2 (2 2))
CL-USER 12 > (maptree #'+ '(1 (1 1 1)) '(1))
(2)
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
From: Kenny Tilton
Subject: Re: There's gotta be a better way to do this
Date:
Message-ID: <3E3EA21F.3070304@nyc.rr.com>
Charlie wrote:
> Ah ha now I've learned every and error it just gets better and better.
> I'm a little confused by (apply #'mapcar ...) rather than just (mapcar
> .... ) ? I tried it with the latter and it failed. I had a look at the
> hyperspec for apply which suggested (mapcar #'new-fn (list* item items)) to
> me (in a vague way) but that also failed.
> Is (apply #'some-func 'a '(b c d)) <=> (some-func 'a 'b 'c 'd) in which case
> what happens when you want to actually pass your function a list e.g. (apply
> #'cons 'a '(b c d)).
Try: (apply #'cons 'a '((b c d)))
:)
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Cells let us walk, talk, think, make love and realize
the bath water is cold." -- Lorraine Lee Cudmore