From 52ff34972c2d26ac9ad9e92dd368f16d5fc91875 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Hugo=20H=C3=B6rnquist?= Date: Tue, 23 Apr 2019 17:07:33 +0200 Subject: Add tree datatype. --- module/util/tree.scm | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) create mode 100644 module/util/tree.scm 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))))) -- cgit v1.2.3