Lightweight, Lazy Trees

8.1

top ← prev up next →

Lightweight, Lazy Trees

Siddhartha Kasivajhula

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

In order to use the utilities in this module, the tree-structured data must first be translated to a canonical format or schema by using the make-tree interface. This schema is simply

(data child ...)

, a stream, where each child has the same structure. A single-element stream represents a leaf node, containing only data and no children. An empty stream represents an empty tree. Any sequence with this structure is treatable as a tree for the purposes of the utilities provided here.

As an example, the list

'(1 (2 (3) (4)) (5 (6)))

is a well-formed tree, with structure that could be visualized as:

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.

Construct a tree from a node (which could be any value) and a function f that yields the next level of the hierarchy (i.e. "children" or "parents") given an input node. The function f is recursively – and lazily – applied starting from node to yield a stream exhibiting the canonical tree structure. By default, the "data" contained in the tree are the provided node objects themselves (whatever they may be). In many cases it may be more natural to use the relevant "contents" of the original tree in the data position, rather than the node itself. This may be specified providing an appropriate data accessor via #:with-data. If the input format includes sentinel values to indicate an empty tree, then a predicate to recognize these empty trees should be provided via #:empty-pred. Supplementary to the examples below, see export-tree for more thorough examples leveraging these parameters.

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.

Examples:

> (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

Traverse a tree using one of the standard traversal orders, i.e. preorder, postorder, in-order or level-order traversal. If converse? is true, then traverses right-to-left instead of left-to-right. Although these traversals are canonically defined for binary trees, trees with an arity greater than two are still supported, using trivial generalizations of the binary tree versions. For instance, an in-order traversal would visit a single child prior to visiting the parent, and then visit all of the remaining children of that parent. See here for some helpful animations of tree traversals.

Examples:

> (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")

procedure
(tree-map f t) → sequence?
f : (-> any/c any/c)
t : sequence?

Analogously to map, lazily maps each element in the tree under the function f.

Examples:

> (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"))

procedure
(tree-filter f t) → sequence?
f : (-> any/c boolean?)
t : sequence?

Analogously to filter, lazily filters each element in the tree under the function f. If a node is filtered out, none of its descendants are present in the resulting tree.

Examples:

> (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

Analogously to fold, combines elements of the tree using the function f. While normal folds have a left or right direction, the direction of a tree fold is determined by the traversal order, which is specified via order.

Examples:

> (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

Export a tree to an arbitrary output format, as specified by the output type constructor f. In constructing the output tree, f will be invoked for each node in tree with the arguments data child ... representing that node (see Schema), in order to construct the corresponding node in the output tree. Note that these arguments are provided to f directly rather than as a list. For example, if the output format is a struct type with named subtrees such as "left" and "right," f in this case would typically just be the struct type constructor. In cases where named subtrees are present and could be empty, each corresponding empty tree in the output type is constructed using empty-cons, which is expected to be a function that takes no arguments and returns an empty tree instance. If empty-cons is #f, the empty subtrees are excluded from the result.

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.

Examples:

> (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 '())))))

top ← prev up next →