hylic

A Rust library for tree-shaped recursive computation.

hylic splits a recursive computation into three pieces you build independently: a fold that says what to compute at each node, a graph that says how a node yields its children, and an executor that drives the recursion. Each piece can be defined, transformed, and composed on its own.

The library ships with two executors. Fused is the sequential one — a callback-based recursion with no overhead beyond the fold closures themselves. Funnel is the parallel one: a work-stealing engine with three compile-time policy axes (queue topology, accumulation strategy, wake policy), all monomorphised, no runtime dispatch on strategy choice. On the 14-workload Matrix bench Funnel wins 10 rows outright against handrolled Rayon and a scoped pool, and lands within a few percent of the winner on the rest. Numbers, the interactive viewer, and the workload catalogue are on the benchmarks page. Scenarios are synthetic CPU-burn workloads, so absolute milliseconds describe shape and relative ordering rather than any specific production pipeline.

The same fold runs unchanged under either executor — the choice of FUSED versus exec(funnel::Spec::default(n)) is one expression, not one rewrite.

A first example

Consider the classical problem of computing total size on disk. The tree structure corresponds to the directory layout; the fold at each node combines the node’s own size with the results from its children; the executor drives the recursion. Each concern is expressed independently and handed to the executor at the end:

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

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

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

        let tree = Dir {
            name: "project".into(), size: 10,
            children: vec![
                Dir { name: "src".into(), size: 200, children: vec![] },
                Dir { name: "docs".into(), size: 50, children: vec![] },
            ],
        };

        // Sequential:
        let total = FUSED.run(&fold, &graph, &tree);
        assert_eq!(total, 260);

        // Parallel — same fold, same graph:
        let total = exec(funnel::Spec::default(4)).run(&fold, &graph, &tree);
        assert_eq!(total, 260);
    }
}

The tree structure need not live inside the data. A Treeish is a function from a node to its children — it can traverse a nested struct, look up indices in a flat array, or resolve references through any external mechanism:

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

        // Flat adjacency list — nodes are indices, children are looked up
        let children: Vec<Vec<usize>> = vec![
            vec![1, 2],  // node 0 → children 1, 2
            vec![],      // node 1 → leaf
            vec![],      // node 2 → leaf
        ];
        let graph = treeish_visit(move |n: &usize, cb: &mut dyn FnMut(&usize)| {
            for &c in &children[*n] { cb(&c); }
        });
        let fold = fold(|n: &usize| *n as u64, |h: &mut u64, c: &u64| *h += c, |h| h.clone());

        let total = FUSED.run(&fold, &graph, &0);
        assert_eq!(total, 3); // 0 + 1 + 2
    }
}

Architecture

User-defined closures are wrapped into composable types (Fold, Treeish), transformed independently, and handed to an executor. The executor drives a recursion where fold and graph interleave at every node:

N — the node type (a struct, an index, a key — anything)
H — the heap: per-node mutable scratch space, created by init, not shared between nodes
R — the result: produced by finalize, flows upward to the parent’s accumulate

Any fold and graph can be executed in parallel by switching to the Funnel executor — a work-stealing engine that interleaves unfold and fold without materialising the tree. Three compile-time policy axes — queue topology, accumulation strategy, wake policy — are monomorphised, so there is no runtime dispatch on strategy choice. See Benchmarks for measured results.

Transformations and lifts

Folds and graphs are independently transformable. Each combinator produces a new value — the original is unchanged (for Clone domains) or consumed (for Owned):

N, NewN — original and target node types
H — the fold’s per-node heap (unchanged by map/zipmap/contramap)
R, RNew, Extra — original, replaced, and augmented result types

All compose freely — see the Fold guide, Graph guide, and Transformations cookbook.

A lift goes further — it transforms both fold and treeish in sync into a different type domain via the Lift trait. The Explainer records the full computation trace at every node (histomorphism).

SeedPipeline handles a common case: the tree is discovered lazily from seed references rather than known upfront. The user provides a seed edge function (Edgy<N, Seed>) and a grow function (Fn(&Seed) -> N); the pipeline constructs the treeish, handles the entry transition, and runs the fold. Internally it uses a lift (SeedLift), and the SeedNode<N> row type is hidden behind sugar-time Node/EntryRoot dispatch.

Cookbook

The Cookbook contains worked examples with snapshot-tested output: expression evaluation, module resolution, configuration inheritance, filesystem summary, cycle detection, parallel execution.

Where to start

The Quick Start walks through constructing and running a fold. The recursive pattern explains the underlying decomposition.

Keyboard shortcuts

hylic

hylic

A first example

Architecture

Transformations and lifts

Cookbook

Where to start

Further reading