doc.txt

# join-forest: join a forest of binary trees

```_join-forest_: join a forest of binary trees

Danny Yoo (dyoo@cs.wpi.edu / dyoo@hkn.eecs.berkeley.edu)

This module provides a few functions for joining a forest of binary
trees together, preserving traversal order.

Example
-------

> (require (planet "join-forest.ss" ("dyoo" "join-forest.plt" 1)))
>
> (define (node-depth a-node)
(cond
[(pair? a-node)
[else 0]))
>
> (define (node-join node-1 node-2)
(list node-1 node-2))
>
> (define tree1 '(1 (2 3)))
> (define tree2 '((4 5) 6))
> (define tree3 '((7 8) 9))
> (define tree4 '10)
> (define tree5 '11)
> (define a-forest (list tree1 tree2 tree3 tree4 tree5))
>
> (define j1 (naive-join-forest a-forest node-join))
>
> (define j2 (simple-join-forest a-forest node-join))
>
> (define j3 (optimal-join-forest a-forest node-join node-depth))
>
> (node-depth j1)
6
> (node-depth j2)
5
> (node-depth j3)
4

API
---

> simple-join-forest: (listof X) (X X -> X) -> X

Given a nonempty list of nodes and a node-joining function, returns
the concatenation of all the nodes.  Done by splitting the forest in
half, joining both halves recursively, and then joining the
combination.

> naive-join-forest: (listof X) (X X -> X) -> X

Given a nonempty list of nodes and a node-joining function, returns
the concatenation of all the nodes.  Done by left-folding the join
function across the forest.

> optimal-join-forest: (listof X) (X X -> X) (X -> natural-number) -> X

Given a nonempty list of nodes, a node-joining function, and a
function defining the depth of a node, returns the concatenation of
all the nodes.  Done by computing an optimal join that minimizes the
total depth of the resulting concatenation.

Note: there's a built-in assumption in optimal-join-forest that:

(node-depth (node-join A B)) = (add1 (max (node-depth A) (node-depth B)))

If this is not true, then this function won't do what you want.
However, a more general optimal-joiner is defined in
find-optimal-join.ss.

find-optimal-join.ss API
------------------------

There is an auxillary module in the join-forest package called
find-optimal-join.ss that's used to implement the optimal-join-forest
function.  It uses a dynamic-programming approach, closely following
the sketch of the optimal matrix-multiplication / parenthesization
algorithm in "Introduction to Algorithms."

> join-forest/cost+: (listof X) (X X -> X) (X -> natural-number)
(natural-number natural-number -> natural-number)
-> X

Given a forest, a node-joiner, a node-cost function, and a cost+
function, returns a concatenation that minimizes cost.

> join-forest: (listof X) (X X -> X) (X -> natural-number) -> X

Given a forest, a node-joiner, a node-cost function returns a
concatenation that minimizes total cost, under the assumption that
given nodes A and B,

(node-cost (node-join A B)) = (add1 (max (node-cost A) (node-cost B)))

join-forest is defined in terms of join-forest/cost+:

(define (join-forest forest join-f depth-f)
(local [(define (cost+ c1 c2)