Lightweight, Lazy Trees
(require data/lazytree) | package: lazytree |
Lightweight, general-purpose utilities for working with tree-structured data.
This module provides a means to leverage the natural hierarchical structure of nested lists (and streams) to represent and perform computations on arbitrary tree-structured data. By using it, applications can keep tree-related operations abstracted, without needing to re-implement standard tree operations for every tree-structured data type or even explicitly represent the tree at all. Additionally, this module provides utilities to conveniently translate between different tree representations, so that these utilities can be used regardless of source format, and the results of computations can be translated into any desired output format.
1 Schema
(data child ...)
'(1 (2 (3) (4)) (5 (6)))
Trees of this schema may be translated to any format (such as the original source format) by using the export-tree interface. As make-tree likewise enables converting any input tree representation to this schema, these two interfaces could be used in tandem to translate between two different data representations involving the tree-structured data, independently of any of the other utilities provided by this module.
2 API
procedure
(make-tree f node #:with-data dataf #:empty-pred empty-pred) → sequence? f : (-> any/c sequence?) node : any/c dataf : identity empty-pred : false.
What if my data has cycles in it? Then the data is technically a graph rather than a tree, but with some cunning you can still use these interfaces to perform tree-structured operations on it. First, you’ll need to ensure that the function f provided to make-tree excludes "visited" nodes so that such cycles are not present in the resulting tree (f would probably need to be a closure to keep track of visited nodes). Additionally, bear in mind that this derived tree wouldn’t contain all of the edges from the original data, so exporting it via export-tree would not reconstruct the original data but the derived tree representation.
> (struct taxon (name children)) > (define dog (taxon "Dog" '())) > (define cat (taxon "Cat" '())) > (define mammal (taxon "Mammal" (list dog cat))) > (export-tree list (make-tree taxon-children mammal)) (list (taxon "Mammal" (list (taxon "Dog" '()) (taxon "Cat" '()))) (list (taxon "Dog" '())) (list (taxon "Cat" '())))
> (export-tree list (make-tree taxon-children mammal #:with-data taxon-name)) '("Mammal" ("Dog") ("Cat"))
procedure
(tree-traverse t [ #:order order #:converse? converse?]) → sequence? t : sequence? order : (one-of/c 'pre 'post 'in 'level) = 'pre converse? : boolean? = #f
> (define t '(1 (2 (3) (4)) (5 (6)))) > (->list (tree-traverse #:order 'pre t)) '(1 2 3 4 5 6)
> (->list (tree-traverse #:converse? #t #:order 'pre t)) '(1 5 6 2 4 3)
> (->list (tree-traverse #:order 'post t)) '(3 4 2 6 5 1)
> (->list (tree-traverse #:order 'in t)) '(3 2 4 1 6 5)
> (->list (tree-traverse #:order 'level t)) '(1 2 5 3 4 6)
> (struct taxon (name children)) > (define dog (taxon "Dog" '())) > (define cat (taxon "Cat" '())) > (define mammal (taxon "Mammal" (list dog cat)))
> (define t (make-tree taxon-children mammal #:with-data taxon-name)) > (->list (tree-traverse #:order 'pre t)) '("Mammal" "Dog" "Cat")
> (->list (tree-traverse #:order 'post t)) '("Dog" "Cat" "Mammal")
> (->list (tree-traverse #:order 'in t)) '("Dog" "Mammal" "Cat")
> (->list (tree-traverse #:order 'level t)) '("Mammal" "Dog" "Cat")
> (->list (tree-traverse #:converse? #t #:order 'pre t)) '("Mammal" "Cat" "Dog")
> (define t '(1 (2 (3) (4)) (5 (6)))) > (export-tree list (tree-map sqr t)) '(1 (4 (9) (16)) (25 (36)))
> (struct taxon (name children)) > (define dog (taxon "Dog" '())) > (define cat (taxon "Cat" '())) > (define mammal (taxon "Mammal" (list dog cat))) > (define t (make-tree taxon-children mammal)) > (export-tree list (tree-map taxon-name t)) '("Mammal" ("Dog") ("Cat"))
> (struct taxon (name children)) > (define dog (taxon "Dog" '())) > (define cat (taxon "Cat" '())) > (define mammal (taxon "Mammal" (list dog cat)))
> (define t (make-tree taxon-children mammal #:with-data taxon-name))
> (export-tree list (tree-filter (lambda (v) (/= v "Dog")) t)) '("Mammal" ("Cat"))
procedure
(tree-fold f t base [ #:order order #:converse? converse? #:argument-order argument-order #:with-steps? with-steps?]) → any/c f : (-> any/c any/c any/c) t : sequence? base : any/c order : (one-of/c 'pre 'post 'in 'level) = 'pre converse? : boolean? = #f argument-order : (one-of/c 'abb 'bab) = 'abb with-steps? : boolean? = #f
> (struct taxon (name children)) > (define dog (taxon "Dog" '())) > (define cat (taxon "Cat" '())) > (define mammal (taxon "Mammal" (list dog cat)))
> (define t (make-tree taxon-children mammal #:with-data taxon-name)) > (tree-fold .. t) "CatDogMammal"
> (tree-fold #:order 'post .. t) "MammalCatDog"
procedure
(export-tree f tree #:empty-cons empty-cons) → sequence?
f : procedure? tree : sequence? empty-cons : #f
As make-tree supports any input tree representation and export-tree supports any output representation, these two interfaces could be used in tandem to translate between two different data representations involving the tree-structured data, independently of any of the other utilities provided by this module.
> (export-tree list (make-tree rest '(1 (2 (3) (4)) (5 (6))) #:with-data first)) '(1 (2 (3) (4)) (5 (6)))
> (struct taxon (name children) #:transparent) > (define dog (taxon "Dog" '())) > (define cat (taxon "Cat" '())) > (define mammal (taxon "Mammal" (list dog cat)))
> (export-tree (λ tree (taxon (first tree) (rest tree))) (make-tree taxon-children mammal #:with-data taxon-name)) (taxon "Mammal" (list (taxon "Dog" '()) (taxon "Cat" '())))
> (export-tree list (make-tree taxon-children mammal #:with-data taxon-name)) '("Mammal" ("Dog") ("Cat"))
> (struct node (data left right) #:transparent)
> (struct empty-tree () #:transparent)
> (define (node-children t) (list (node-left t) (node-right t)))
> (define tree (node 1 (node 2 (empty-tree) (node 3 (empty-tree) (empty-tree))) (empty-tree)))
> (export-tree node (make-tree node-children tree #:with-data node-data #:empty-pred empty-tree?) #:empty-cons empty-tree) (node 1 (node 2 (empty-tree) (node 3 (empty-tree) (empty-tree))) (empty-tree))
> (struct node-too (data children) #:transparent)
> (export-tree (λ tree (node-too (first tree) (rest tree))) (make-tree node-children tree #:with-data node-data #:empty-pred empty-tree?)) (node-too 1 (list (node-too 2 (list (node-too 3 '())))))