The recursive pattern

Recursive tree computations — regardless of domain — share a single underlying structure. hylic makes that structure explicit, names its parts, and allows each part to be transformed independently.

One function

The entire computation, taken directly from the sequential executor:

#![allow(unused)]
fn main() {
fn recurse<N, H, R>(
    fold: &impl FoldOps<N, H, R>,
    graph: &impl TreeOps<N>,
    node: &N,
) -> R {
    let mut heap = fold.init(node);
    graph.visit(node, &mut |child: &N| {
        let r = recurse(fold, graph, child);
        fold.accumulate(&mut heap, &r);
    });
    fold.finalize(&heap)
}
}

At each node:

1. init — construct a heap H from the node
2. visit children — for each child, recurse and accumulate the result
3. finalize — produce the node’s result R from the heap

Every tree fold — Fibonacci, dependency resolution, filesystem aggregation, AST evaluation — is this function instantiated with different choices for init, accumulate, finalize, and child structure.

Three pieces

The function above takes three things as parameters. hylic gives each a name and a type:

Treeish — the tree structure. Given a node, visit its children:

#![allow(unused)]
fn main() {
/// A `NodeT → EdgeT*` function wrapped as a clonable Arc-backed
/// struct. When `NodeT = EdgeT` the type is typically named
/// [`crate::graph::Treeish`].
pub struct Edgy<NodeT, EdgeT> {
    impl_visit: Arc<dyn Fn(&NodeT, &mut dyn FnMut(&EdgeT)) + Send + Sync>,
}
}

Treeish<N> is an alias for Edgy<N, N> — an edge function where nodes and edges are the same type:

#![allow(unused)]
fn main() {
pub type Treeish<Node> = Edgy<Node, Node>;
}

A Treeish is constructed from a function from node to children:

#![allow(unused)]
fn main() {
    #[test]
    fn treeish_constructor() {
        use hylic::prelude::*;

        #[derive(Clone)]
        struct Dir { name: String, size: u64, children: Vec<Dir> }

        let graph: Treeish<Dir> = treeish(|d: &Dir| d.children.clone());
        let root = Dir { name: "root".into(), size: 10, children: vec![] };
        assert_eq!(graph.apply(&root).len(), 0);
    }
}

The callback-based signature Fn(&N, &mut dyn FnMut(&N)) avoids any allocation per visit. The treeish() constructor wraps a Vec-returning function into this form.

The node type N may be anything — a nested struct, an integer index into an adjacency list, a string key into a map, or a reference resolved through I/O. The structure resides in the treeish function rather than in the data.

Fold — the computation. In the Shared domain, three closures behind Arc:

#![allow(unused)]
fn main() {
pub struct Fold<N, H, R> {
    pub(crate) impl_init: Arc<dyn Fn(&N) -> H + Send + Sync>,
    pub(crate) impl_accumulate: Arc<dyn Fn(&mut H, &R) + Send + Sync>,
    pub(crate) impl_finalize: Arc<dyn Fn(&H) -> R + Send + Sync>,
}
}

Other domains use Rc (Local) or Box (Owned) — same operations, different boxing. The fold type doesn’t carry the domain; the executor does.

• init: &N → H — create per-node working state from the node
• accumulate: &mut H, &R — fold one child’s result into the heap
• finalize: &H → R — close the bracket, produce the node’s result

H and R are distinct types: H is mutable working state (the open bracket), R is the immutable result flowing to the parent (the closed bracket). See The N-H-R algebra factorization for the theoretical basis. Many folds have H = R, in which case finalize is just an identity extraction from the heap:

#![allow(unused)]
fn main() {
    #[test]
    fn identity_finalize_fold_example() {
        use hylic::prelude::*;

        #[derive(Clone)]
        struct Dir { name: String, size: u64, children: Vec<Dir> }

        let graph: Treeish<Dir>      = treeish(|d: &Dir| d.children.clone());
        let sum:   Fold<Dir, u64, u64> = fold(
            |d: &Dir| d.size,
            |heap: &mut u64, child: &u64| *heap += child,
            |h: &u64| *h,
        );

        let tree = Dir {
            name: "root".into(), size: 10,
            children: vec![
                Dir { name: "a".into(), size: 5, children: vec![] },
                Dir { name: "b".into(), size: 3, children: vec![] },
            ],
        };
        assert_eq!(FUSED.run(&sum, &graph, &tree), 18);
    }
}

Executor — the strategy. Controls HOW the recursion runs:

#![allow(unused)]
fn main() {
    #[test]
    fn exec_usage() {
        use hylic::prelude::*;

        #[derive(Clone)]
        struct N { val: u64, children: Vec<N> }

        let graph: Treeish<N> = treeish(|n: &N| n.children.clone());
        let f:     Fold<N, u64, u64> = fold(
            |n: &N| n.val,
            |h: &mut u64, c: &u64| *h += c,
            |h: &u64| *h,
        );
        let root = N { val: 1, children: vec![N { val: 2, children: vec![] }] };

        // Sequential:
        let r1: u64 = FUSED.run(&f, &graph, &root);
        // Parallel — same fold, same graph:
        let r2: u64 = exec(funnel::Spec::default(4)).run(&f, &graph, &root);
        assert_eq!(r1, r2);
    }
}

Two executors are provided:

Both implement the Executor<N, R, D, G> trait, parameterised by a domain and graph type. See Executor architecture for details.

The separation

The fold carries no knowledge of the tree; the tree carries no knowledge of the fold; the executor connects them. The domain determines how closures are stored — the fold and treeish do not record this, the executor does.

Every computation in hylic reduces to executor.run(&fold, &treeish, &root). When the tree is discovered lazily (seeds resolved on demand), SeedPipeline constructs the treeish from a seed edge function together with a grow, and delegates to executor.run internally.

The operations traits

The executor’s recursion engine doesn’t know about Arc, Rc, or Box. It takes &impl FoldOps<N, H, R> and &impl TreeOps<N> — pure operation traits:

#![allow(unused)]
fn main() {
/// The three fold operations, independent of storage.
pub trait FoldOps<N, H, R> {
    /// Construct a fresh per-node heap from a node reference.
    fn init(&self, node: &N) -> H;
    /// Fold one child result into the heap in place.
    fn accumulate(&self, heap: &mut H, result: &R);
    /// Close out the heap into the node's final result.
    fn finalize(&self, heap: &H) -> R;
}
}

#![allow(unused)]
fn main() {
/// Tree traversal operations, independent of storage.
pub trait TreeOps<N> {
    /// Visit children of `node` via callback. Zero allocation.
    fn visit(&self, node: &N, cb: &mut dyn FnMut(&N));

    /// Collect children to Vec. Default: collect via visit.
    fn apply(&self, node: &N) -> Vec<N> where N: Clone {
        let mut v = Vec::new();
        self.visit(node, &mut |child| v.push(child.clone()));
        v
    }
}
}

The standard Fold<N, H, R> and Treeish<N> implement these traits. So do local::Fold, owned::Fold, and any user-defined struct with the right methods. The executor is generic over these traits — when called with a concrete struct, the compiler inlines completely.

See Domain system for how domains connect operations to storage.