diff options
author | Hugo Hörnquist <hugo@lysator.liu.se> | 2022-06-28 16:53:09 +0200 |
---|---|---|
committer | Hugo Hörnquist <hugo@lysator.liu.se> | 2022-07-07 21:19:15 +0200 |
commit | 055dcfa3d1fcbbe46aaf32335b3269254dd66743 (patch) | |
tree | 23241bcf1f7d67aee1b787052d4759e32d26ff72 /module | |
parent | Add basic table. (diff) | |
download | calp-055dcfa3d1fcbbe46aaf32335b3269254dd66743.tar.gz calp-055dcfa3d1fcbbe46aaf32335b3269254dd66743.tar.xz |
Add tree->list, -map, and -fold.
Diffstat (limited to '')
-rw-r--r-- | module/hnh/util/table.scm | 24 |
1 files changed, 24 insertions, 0 deletions
diff --git a/module/hnh/util/table.scm b/module/hnh/util/table.scm index 3afb3a46..5835851b 100644 --- a/module/hnh/util/table.scm +++ b/module/hnh/util/table.scm @@ -48,6 +48,30 @@ (else (tree-get (right tree) k)))) +;; in-order traversal +(define (tree->list tree) + (if (tree-terminal? tree) + '() + (append (tree->list (left tree)) + (list (cons (key tree) (value tree))) + (tree->list (right tree))))) + +;; undefined order, probably pre-order +(define (tree-map f tree) + (if (tree-terminal? tree) + '() + (tree-node (key tree) + (f (key tree) (value tree)) + (tree-map f (left tree)) + (tree-map f (right tree))))) + +;; pre-order +(define (tree-fold f init tree) + (if (tree-terminal? tree) + init + (let ((a (f (key tree) (value tree) init))) + (let ((b (tree-fold f a (left tree)))) + (tree-fold f b (right tree)))))) (define (alist->tree alist) (fold (lambda (kv tree) (apply tree-put tree kv)) |