From 055dcfa3d1fcbbe46aaf32335b3269254dd66743 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Hugo=20H=C3=B6rnquist?= Date: Tue, 28 Jun 2022 16:53:09 +0200 Subject: Add tree->list, -map, and -fold. --- module/hnh/util/table.scm | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) 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)) -- cgit v1.2.3