Add tree datatype.

1 files changed, 37 insertions, 0 deletions

diff --git a/module/util/tree.scm b/module/util/tree.scm
new file mode 100644
index 00000000..103888cc
--- /dev/null
+++ b/module/util/tree.scm
@@ -0,0 +1,37 @@
+(define-module (util tree)
+  #:use-module (srfi srfi-1)
+  #:use-module (util)
+  #:export (make-tree left-subtree
+                      right-subtree
+                      length-of-longst-branch
+                      tree-map))
+
+;; Constructs a binary tree where each node's children is partitioned
+;; into a left and right branch using @var{pred?}.
+;; Has thee form @var{(node left-subtree right-subtree)}. A leaf has
+;; both it's children equal to @var{null}.
+(define (make-tree pred? lst)
+  (if (null? lst) '()
+      (let* ((head tail (partition (lambda (el) (pred? (car lst) el))
+                                   (cdr lst))))
+        (list (car lst)
+              (make-tree pred? head)
+              (make-tree pred? tail)))))
+
+(define (left-subtree tree)
+  (list-ref tree 1))
+
+(define (right-subtree tree)
+  (list-ref tree 2))
+
+;; Length includes current node, so the length of a leaf is 1.
+(define (length-of-longst-branch tree)
+  (if (null? tree)
+      0 (1+ (max (length-of-longst-branch (left-subtree tree))
+                 (length-of-longst-branch (right-subtree tree))))))
+
+(define (tree-map proc tree)
+  (if (null? tree) '()
+      (list (proc (car tree))
+            (tree-map proc (left-subtree tree))
+            (tree-map proc (right-subtree tree)))))