| 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))) |