Debian Codegraph @

lib/util/tree.scm

raw
1 ;;;
2 ;;; tree.scm - walk tree
3 ;;;
4 ;;; Written by Shiro Kawai ([email protected]) 2001
5 ;;; Public Domain.. I guess lots of Scheme programmers have already
6 ;;; written similar code.
7 ;;;
8
9 (define-module util.tree
10 (use scheme.list)
11 (export tree-fold tree-walk tree-fold-bf tree-walk-bf)
12 )
13 (select-module util.tree)
14
15 (define (tree-walk tree proc leaf? walker)
16 (define (rec node)
17 (walker (^n (if (leaf? n) (proc n) (rec n))) node))
18 (if (leaf? tree) (proc tree) (rec tree)))
19
20 (define (tree-fold tree proc knil leaf? folder)
21 (define (rec node r)
22 (folder (lambda (n knil) (if (leaf? n) (proc n knil) (rec n knil)))
23 r node))
24 (if (leaf? tree) (proc tree knil) (rec tree knil)))
25
26 (define (tree-walk-bf tree proc leaf? walker)
27 (define (rec node)
28 (let* ((branches '()))
29 (walker (^n (if (leaf? n) (proc n) (push! branches n))) node)
30 (for-each rec (reverse branches))))
31 (if (leaf? tree) (proc tree) (rec tree)))
32
33 (define (tree-fold-bf tree proc knil leaf? folder)
34 (define (rec node r)
35 (let* ((branches '())
36 (r (folder (lambda (n knil)
37 (if (leaf? n)
38 (proc n knil)
39 (begin (push! branches n) knil)))
40 r node)))
41 (fold rec r (reverse branches))))
42 (if (leaf? tree) (proc tree knil) (rec tree knil)))