summaryrefslogtreecommitdiffstats
path: root/tree.scm
diff options
context:
space:
mode:
authorBryan Newbold <bnewbold@robocracy.org>2017-02-20 00:05:29 -0800
committerBryan Newbold <bnewbold@robocracy.org>2017-02-20 00:05:29 -0800
commit8466d8cfa486fb30d1755c4261b781135083787b (patch)
treec8c12c67246f543c3cc4f64d1c07e003cb1d45ae /tree.scm
parent87b82b5822ca54228cfa6df29be3ad9d4bc47d16 (diff)
downloadslib-8466d8cfa486fb30d1755c4261b781135083787b.tar.gz
slib-8466d8cfa486fb30d1755c4261b781135083787b.zip
Import Upstream version 3a1upstream/3a1
Diffstat (limited to 'tree.scm')
-rw-r--r--tree.scm69
1 files changed, 53 insertions, 16 deletions
diff --git a/tree.scm b/tree.scm
index e9bc999..ae29a52 100644
--- a/tree.scm
+++ b/tree.scm
@@ -5,15 +5,39 @@
;; Deep copy of the tree -- new one has all new pairs. (Called
;; tree-copy in Dybvig.)
-(define (tree:copy-tree tree)
- (if (pair? tree)
- (cons (tree:copy-tree (car tree))
- (tree:copy-tree (cdr tree)))
- tree))
+
+;;@code{(require 'tree)}
+;;@ftindex tree
+;;
+;;These are operations that treat lists a representations of trees.
;; Substitute occurrences of old equal? to new in tree.
;; Similar to tree walks in SICP without the internal define.
-(define (tree:subst new old tree . equ?)
+
+;; substq and substv aren't in CL. (Names from Dybvig)
+
+;;@args new old tree
+;;@args new old tree equ?
+;;@code{subst} makes a copy of @3, substituting @1 for
+;;every subtree or leaf of @3 which is @code{equal?} to @2
+;;and returns a modified tree. The original @3 is unchanged, but
+;;may share parts with the result.
+;;
+;;@code{substq} and @code{substv} are similar, but test against @2
+;;using @code{eq?} and @code{eqv?} respectively. If @code{subst} is
+;;called with a fourth argument, @var{equ?} is the equality predicate.
+;;
+;;Examples:
+;;@lisp
+;;(substq 'tempest 'hurricane '(shakespeare wrote (the hurricane)))
+;; @result{} (shakespeare wrote (the tempest))
+;;(substq 'foo '() '(shakespeare wrote (twelfth night)))
+;; @result{} (shakespeare wrote (twelfth night . foo) . foo)
+;;(subst '(a . cons) '(old . pair)
+;; '((old . spice) ((old . shoes) old . pair) (old . pair)))
+;; @result{} ((old . spice) ((old . shoes) a . cons) (a . cons))
+;;@end lisp
+(define (subst new old tree . equ?)
(set! equ? (if (null? equ?) equal? (car equ?)))
(letrec ((walk (lambda (tree)
(cond ((equ? old tree) new)
@@ -22,16 +46,29 @@
(walk (cdr tree))))
(else tree)))))
(walk tree)))
-
-;; The next 2 aren't in CL. (Names from Dybvig)
-
-(define (tree:substq new old tree)
+(define (substq new old tree)
(tree:subst new old tree eq?))
-
-(define (tree:substv new old tree)
+(define (substv new old tree)
(tree:subst new old tree eqv?))
-(define copy-tree tree:copy-tree)
-(define subst tree:subst)
-(define substq tree:substq)
-(define substv tree:substv)
+;;@body
+;;Makes a copy of the nested list structure @1 using new pairs and
+;;returns it. All levels are copied, so that none of the pairs in the
+;;tree are @code{eq?} to the original ones -- only the leaves are.
+;;
+;;Example:
+;;@lisp
+;;(define bar '(bar))
+;;(copy-tree (list bar 'foo))
+;; @result{} ((bar) foo)
+;;(eq? bar (car (copy-tree (list bar 'foo))))
+;; @result{} #f
+;;@end lisp
+(define (copy-tree tree)
+ (if (pair? tree)
+ (cons (tree:copy-tree (car tree))
+ (tree:copy-tree (cdr tree)))
+ tree))
+
+(define tree:copy-tree copy-tree)
+(define tree:subst subst)