Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Quick Start

A complete fold — definition, tree structure, sequential execution — is one prelude line and three closures:

#![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);
    }
}

fold(...) builds a Shared-domain Fold<Dir, u64, u64> from three closures: init produces a per-node heap from a &Dir, accumulate folds each child’s result into the heap, and finalize extracts the result. treeish(...) wraps a children function as a Treeish<Dir>. FUSED is the sequential executor constant — callback-based recursion, no overhead beyond the fold closures.

The Funnel executor swaps in without touching the fold or graph:

#![allow(unused)]
fn main() {
    #[test]
    fn quickstart_funnel() {
        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: "root".into(), size: 10,
            children: vec![
                Dir { name: "a".into(), size: 5, children: vec![] },
                Dir { name: "b".into(), size: 3, children: vec![] },
            ],
        };

        let total = exec(funnel::Spec::default(4)).run(&fold, &graph, &tree);
        assert_eq!(total, 18);
    }
}

Spec::default(n) picks the Robust preset over n worker threads; see Funnel policies for the alternatives.

For repeated folds, pool creation amortises in a session scope:

#![allow(unused)]
fn main() {
    #[test]
    fn quickstart_session() {
        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: "root".into(), size: 10,
            children: vec![
                Dir { name: "a".into(), size: 5, children: vec![] },
            ],
        };

        exec(funnel::Spec::default(4)).session(|s| {
            let r1 = s.run(&fold, &graph, &tree);
            let r2 = s.run(&fold, &graph, &tree);
            assert_eq!(r1, r2);
        });
    }
}

The same fold over flat data

The tree need not live inside the data. The same summation fold runs over a Vec<Vec<usize>> adjacency list, where nodes are integer indices:

#![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
    }
}

Only the node type and the Treeish change — the fold logic is identical. This separation is the foundation of hylic’s composability.

Pivoting between the two

The two formulations describe the same shape of computation in different node types. Fold::contramap_n lets you take a fold written for one and run it over the other, without rewriting any of the fold’s closures.

Going Dir-fold → flat: synthesise a minimal Dir per index — only the fields the fold actually reads need to exist. The graph is swapped on the executor’s side.

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

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

        // The Dir-fold reads d.size and nothing else.
        let dir_fold: Fold<Dir, u64, u64> = fold(
            |d: &Dir| d.size,
            |h: &mut u64, c: &u64| *h += c,
            |h: &u64| *h,
        );

        // Flat data for the same logical tree.
        let sizes: Vec<u64>      = vec![10, 200, 50];
        let adj: Vec<Vec<usize>> = vec![vec![1, 2], vec![], vec![]];

        // Pivot: contramap_n synthesises a minimal Dir from each index — only
        // the fields the fold reads need to exist. The fold's closures are
        // unchanged; the graph is the index-based one.
        let flat_fold:  Fold<usize, u64, u64> =
            dir_fold.contramap_n(move |i: &usize| Dir { size: sizes[*i], children: vec![] });
        let flat_graph: Treeish<usize> =
            treeish_visit(move |i: &usize, cb: &mut dyn FnMut(&usize)| {
                for &c in &adj[*i] { cb(&c); }
            });

        let total: u64 = FUSED.run(&flat_fold, &flat_graph, &0);
        assert_eq!(total, 260);
    }
}

The mirror direction projects each Dir to the index the flat-fold expects:

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

        #[derive(Clone)]
        struct Dir { id: usize, children: Vec<Dir> }

        // The flat-fold reads sizes[*i] from a captured array.
        let sizes: Vec<u64> = vec![10, 200, 50];
        let flat_fold: Fold<usize, u64, u64> = fold(
            move |i: &usize| sizes[*i],
            |h: &mut u64, c: &u64| *h += c,
            |h: &u64| *h,
        );

        // The same logical tree as a struct.
        let root = Dir { id: 0, children: vec![
            Dir { id: 1, children: vec![] },
            Dir { id: 2, children: vec![] },
        ]};

        // Pivot: contramap_n projects each Dir to the index the fold expects.
        // The fold's closures are unchanged; the graph walks struct children.
        let dir_fold:  Fold<Dir, u64, u64> = flat_fold.contramap_n(|d: &Dir| d.id);
        let dir_graph: Treeish<Dir>        = treeish(|d: &Dir| d.children.clone());

        let total: u64 = FUSED.run(&dir_fold, &dir_graph, &root);
        assert_eq!(total, 260);
    }
}

In both directions the original fold’s closures pass through unchanged; the only transformation is contramap_n on the input axis. The graph is chosen at the call site to match.

Further reading