Mapping over a tree of CONSes 
Author Message
 Mapping over a tree of CONSes

In connection with a posting I saw a couple of weeks ago, I decided to
see if I could compose a MAP-OVER-TREE by passing appropriate
arguments to NSUBST-IF.  When I began to get unusual results, I
expanded my investigation to SUBST-IF, NSUBLIS, SUBLIS, NSUBST, and
SUBST.  The six alternatives are attached below.  To try them out,
simply evaluate

(map-over-tree-<n> #'print '(((a)) (b (c ((d))))))

for <n> from 1 to 6.

I found two anomalies, though:

- CL implementations disagree on the order of arguments to the :TEST
function for SUBLIS and NSUBLIS.  I dealt with this via #+ in those
two cases.  CLtL2 (p. 391) and the dpANS (Sec. 17.2.1) seem to
indicate that (ITEM NODE) is the correct ordering, but it would lose
in a majority vote of the five implementations I tried.

- CL implementations vary greatly as to which tree-nodes they visit
once, and which they visit twice.  ("Visit" here is defined to be the
execution of the test function, but I presume that passing an explicit
:KEY instead of a test function would yield similar results.)

- One implementation always visits every tree-node once.

- One implementation always visits each atomic cdr twice; other
tree-nodes are visited once.

- Three implementations visit each tree-node once, except that if the
function is potentially destructive (NSUBST, NSUBST-IF, or NSUBLIS)
and the tree-node is a CONS and that tree-node is not a CONS's cdr,
then that tree-node is visited twice.

I was very surprised, because CLtL2 and the dpANS seem to indicate
that every tree-node should be visited exactly once.  Note that the
restrictions on side-effects during structure traversal (p. 179 in
CLtL2, Sec. 3.6 in the dpANS) apply only to modifications of the
structure itself, not other side-effects such as writing to a stream.

Are the book and standard this loose, or am I merely encountering
subtle bugs?

-----
(in-package :cl-user)

(defun map-over-tree-1 (func tree)
  (nsubst-if nil
             #'(lambda (node)
                 (funcall func node)
                 nil)
             tree)
  (values))

(defun map-over-tree-2 (func tree)
  (subst-if nil
            #'(lambda (node)
                (funcall func node)
                nil)
            tree)
  (values))

(defun map-over-tree-3 (func tree)
  (nsublis '((nil . nil)) tree
           :test #'(lambda #+(or lispworks cmu lisp::clisp) (node item)
                           #+(or genera allegro) (item node)
                     (declare (ignore item))
                     (funcall func node)
                     nil))
  (values))

(defun map-over-tree-4 (func tree)
  (sublis '((nil . nil)) tree
          :test #'(lambda #+(or lispworks cmu lisp::clisp) (node item)
                          #+(or genera allegro) (item node)
                    (declare (ignore item))
                    (funcall func node)
                    nil))
  (values))

(defun map-over-tree-5 (func tree)
  (nsubst nil nil tree
          :test #'(lambda (item node)
                    (declare (ignore item))
                    (funcall func node)
                    nil))
  (values))

(defun map-over-tree-6 (func tree)
  (subst nil nil tree
         :test #'(lambda (item node)
                   (declare (ignore item))
                   (funcall func node)
                   nil))
  (values))
-----

--
        Lawrence G. Mayka
        AT&T Bell Laboratories

Standard disclaimer.



Fri, 09 Aug 1996 04:44:25 GMT  
 Mapping over a tree of CONSes

Quote:
>I found two anomalies, though:

>- CL implementations disagree on the order of arguments to the :TEST
>function for SUBLIS and NSUBLIS.  I dealt with this via #+ in those
>two cases.  CLtL2 (p. 391) and the dpANS (Sec. 17.2.1) seem to
>indicate that (ITEM NODE) is the correct ordering, but it would lose
>in a majority vote of the five implementations I tried.

Looks like there is some confusion on what "satisfies the test" refers to.
One interpretation (yours and two implementations') is that the alist is
the sequence, and each node is being tested against the alist; the other is
that each key of the alist is being tested against the tree nodes.

However, the examples in the dpANS make it clear that the :KEY is only
applied to the tree nodes.  Since the result of :KEY is always the second
argument to a two-argument :TEST (except when traversing two sequences, in
which case :KEY is applied to elements of both), I agree with you that it
should be (ITEM NODE).  While the examples are not officially part of the
specification, I believe they can be used to resolve ambiguities like this.

Quote:
>- CL implementations vary greatly as to which tree-nodes they visit
>once, and which they visit twice.
...
>I was very surprised, because CLtL2 and the dpANS seem to indicate
>that every tree-node should be visited exactly once.  Note that the
>restrictions on side-effects during structure traversal (p. 179 in
>CLtL2, Sec. 3.6 in the dpANS) apply only to modifications of the
>structure itself, not other side-effects such as writing to a stream.

Where does the dpANS say that these functions only visit each node once?
Section 3.6 allows other side effects during structure traversal, but it
never says what order they'll occur in or whether they'll be repeated.
In some cases the description specifically mentions this flexibility (see
SEARCH), but I don't think the lack of such mention implies any particular
behavior; there's no place that says, "Unless otherwise specified, these
functions only call the test function once on each node."
--
Barry Margolin
System Manager, Thinking Machines Corp.




Sun, 11 Aug 1996 01:57:30 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. tree-mapping

2. of lists and conses

3. Structures vs. conses

4. map export with required maps?

5. MAP VisualSpeller and MAP First Impression Templates Update

6. Free 3D Maps/Map Maker

7. maps and meta-maps (was middleware)

8. Self-Adjusting Binary Search Trees (Splay Trees)

9. Self-Adjusting Binary Search Trees (Splay Trees)

10. TREE browse .. Ultra Tree Template - Att Marius

11. cast iron tree stand for Christmas tree

12. Alternate solution to tree -> tree problem

 

 
Powered by phpBB® Forum Software