summaryrefslogtreecommitdiffstats
path: root/tree.scm
diff options
context:
space:
mode:
Diffstat (limited to 'tree.scm')
-rw-r--r--tree.scm62
1 files changed, 62 insertions, 0 deletions
diff --git a/tree.scm b/tree.scm
new file mode 100644
index 0000000..f400d1b
--- /dev/null
+++ b/tree.scm
@@ -0,0 +1,62 @@
+;;"tree.scm" Implementation of COMMON LISP tree functions for Scheme
+; Copyright 1993, 1994 David Love (d.love@dl.ac.uk)
+;
+;Permission to copy this software, to redistribute it, and to use it
+;for any purpose is granted, subject to the following restrictions and
+;understandings.
+;
+;1. Any copy made of this software must include this copyright notice
+;in full.
+;
+;2. I have made no warrantee or representation that the operation of
+;this software will be error-free, and I am under no obligation to
+;provide any services, by way of maintenance, update, or otherwise.
+;
+;3. In conjunction with products arising from the use of this
+;material, there shall be no use of my name in any advertising,
+;promotional, or sales literature without prior written consent in
+;each case.
+
+;; 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))
+
+;; 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)
+ (let walk ((tree tree))
+ (cond ((equal? old tree)
+ new)
+ ((pair? tree)
+ (cons (walk (car tree))
+ (walk (cdr tree))))
+ (else tree))))
+
+;; The next 2 aren't in CL. (Names from Dybvig)
+
+(define (tree:substq new old tree)
+ (let walk ((tree tree))
+ (cond ((eq? old tree)
+ new)
+ ((pair? tree)
+ (cons (walk (car tree))
+ (walk (cdr tree))))
+ (else tree))))
+
+(define (tree:substv new old tree)
+ (let walk ((tree tree))
+ (cond ((eqv? old tree)
+ new)
+ ((pair? tree)
+ (cons (walk (car tree))
+ (walk (cdr tree))))
+ (else tree))))
+
+(define copy-tree tree:copy-tree)
+(define subst tree:subst)
+(define substq tree:substq)
+(define substv tree:substv)