Fold: shaping the computation

A Fold<N, H, R> is defined by three phases: init, accumulate, and finalize. Each phase is a closure stored in the boxing strategy of the domain in use — Arc for Shared, Rc for Local, Box for Owned. Each phase may be transformed independently.

Named-closures-first pattern

Closures should be extracted and named before being passed to the constructor:

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

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

        // Named closures — reusable across domains.
        let init = |n: &N| n.val;
        let acc  = |h: &mut u64, c: &u64| *h += c;
        let fin  = |h: &u64| *h;

        // A free `fn` makes the visit function's full type visible at the
        // binding site; capture-free, reusable across domains.
        fn children(n: &N, cb: &mut dyn FnMut(&N)) {
            for c in &n.children { cb(c); }
        }

        let f:     Fold<N, u64, u64> = fold(init, acc, fin);
        let graph: Treeish<N>        = treeish_visit(children);
        let root = N { val: 1, children: vec![N { val: 2, children: vec![] }] };

        assert_eq!(FUSED.run(&f, &graph, &root), 3);
    }
}

This form allows closures to be reused across domains and read without nesting.

Phase transformations

Wrap individual phases without changing the fold’s types:

wrap_init — adding side effects at initialisation

#![allow(unused)]
fn main() {
    #[test]
    fn fold_wrap_init() {
        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 f:     Fold<Dir, u64, u64> = fold(
            |d: &Dir| d.size,
            |h: &mut u64, c: &u64| *h += c,
            |h: &u64| *h,
        );

        let logged: Fold<Dir, u64, u64> = f.wrap_init(
            |d: &Dir, orig: &dyn Fn(&Dir) -> u64| orig(d),
        );

        let tree = Dir { name: "r".into(), size: 10, children: vec![] };
        assert_eq!(FUSED.run(&logged, &graph, &tree), 10);
    }
}

The wrapper receives the node and the original init as a callable reference. The closure may invoke it, modify its result, add side effects, or bypass it entirely. The mechanism is available in all three domains.

Result-type transformations

Change what the fold produces:

zipmap — augmenting the result

#![allow(unused)]
fn main() {
    #[test]
    fn fold_zipmap() {
        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 with_flag: Fold<N, u64, (u64, bool)> = f.zipmap(|r: &u64| *r > 5);
        let root = N { val: 1, children: vec![
            N { val: 3, children: vec![] },
            N { val: 4, children: vec![] },
        ]};
        let (total, over_five): (u64, bool) = FUSED.run(&with_flag, &graph, &root);
        assert_eq!(total, 8);
        assert!(over_five);
    }
}

zipmap is the most common transformation: additional computed data is attached to the result without altering the fold’s core logic.

Node-type transformations

contramap — changing the input type

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

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

        let f: Fold<N, u64, u64> = fold(
            |n: &N| n.val,
            |h: &mut u64, c: &u64| *h += c,
            |h: &u64| *h,
        );

        // Change node type: String → N.
        let by_name: Fold<String, u64, u64> =
            f.contramap_n(|s: &String| N { val: s.len() as u64, children: vec![] });
        let graph: Treeish<String> =
            treeish_visit(|_: &String, _cb: &mut dyn FnMut(&String)| {});

        let result: u64 = FUSED.run(&by_name, &graph, &"hello".to_string());
        assert_eq!(result, 5);
    }
}

Only init consumes the node directly. contramap wraps init to transform the input; accumulate and finalize are left unchanged. See also Transforms and variance for the variance story that dictates the argument shape.

Composition

product — two folds, one traversal

#![allow(unused)]
fn main() {
    #[test]
    fn fold_product() {
        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 size_fold: Fold<Dir, u64, u64> = fold(
            |d: &Dir| d.size,
            |h: &mut u64, c: &u64| *h += c,
            |h: &u64| *h,
        );

        let both: Fold<Dir, (u64, usize), (u64, usize)> = size_fold.product(&depth_fold());
        let tree = Dir {
            name: "r".into(), size: 10,
            children: vec![Dir { name: "a".into(), size: 5, children: vec![] }],
        };
        let (total_size, max_depth) = FUSED.run(&both, &graph, &tree);
        assert_eq!(total_size, 15);
        assert_eq!(max_depth, 2);
    }
}

The categorical product: each fold maintains its own heap, observes its own child results, and produces its own output. One traversal yields two results; no node is visited twice.

Domain parity

All three domains support the same transformation surface:

Shared and Local borrow &self, so the original fold is preserved; Owned consumes self, moving the original into the result. All three delegate to the same domain-independent combinator functions in fold/combinators.rs; auto-trait propagation ensures that Send + Sync flows correctly for Shared.

All domains also expose .init(), .accumulate(), and .finalize() as direct methods, in addition to the FoldOps trait implementation.

See The three domains for guidance on when to select which domain.

Working example

#![allow(unused)]
fn main() {
//! Transformations: features as standalone functions that match the contract.
//!
//! One domain, one base fold, one base graph. Each feature is a named
//! function — it IS the concern, separated and reusable. Plugging it
//! in is a single method call on the existing construct.

#[cfg(test)]
mod tests {
    use std::collections::HashMap;
    use std::sync::{Arc, Mutex};
    use hylic::prelude::*;
    use hylic::prelude::memoize_treeish_by;
    use insta::assert_snapshot;

    // ── Domain ──────────────────────────────────────────────

    #[derive(Clone, Debug)]
    struct Task {
        name: String,
        cost_ms: u64,
        deps: Vec<String>,
    }

    struct Registry(HashMap<String, Task>);

    impl Registry {
        fn new(tasks: &[(&str, u64, &[&str])]) -> Self {
            Registry(tasks.iter().map(|(name, cost, deps)| {
                (name.to_string(), Task {
                    name: name.to_string(),
                    cost_ms: *cost,
                    deps: deps.iter().map(|d| d.to_string()).collect(),
                })
            }).collect())
        }
        fn get(&self, name: &str) -> Option<&Task> { self.0.get(name) }
    }

    // ── Shared setup ────────────────────────────────────────

    fn setup() -> (Treeish<Task>, Task) {
        let reg = Registry::new(&[
            ("app",       50,  &["compile", "link"]),
            ("compile",   200, &["parse", "typecheck"]),
            ("parse",     100, &[]),
            ("typecheck", 300, &[]),
            ("link",      150, &[]),
        ]);
        let map = reg.0.clone();
        let g: Treeish<Task> = treeish(move |task: &Task| {
            task.deps.iter().filter_map(|d| map.get(d).cloned()).collect()
        });
        let root = reg.get("app").unwrap().clone();
        (g, root)
    }

    fn base_fold() -> Fold<Task, u64, u64> {
        fold(
            |t: &Task| t.cost_ms,
            |heap: &mut u64, child: &u64| *heap += child,
            |h: &u64| *h,
        )
    }

    // ── Fold phase wrappers ─────────────────────────────────
    //
    // Each is a standalone closure matching the wrap contract:
    //   wrap_init:       Fn(&N, &dyn Fn(&N) -> H) -> H
    //   wrap_accumulate: Fn(&mut H, &R, &dyn Fn(&mut H, &R))
    //   wrap_finalize:   Fn(&H, &dyn Fn(&H) -> R) -> R

    /// Hooks into init: called once per node, before children.
    /// Logs the task name, then delegates to the original init.
    fn visit_logger(sink: Arc<Mutex<Vec<String>>>)
        -> impl Fn(&Task, &dyn Fn(&Task) -> u64) -> u64
    {
        move |task: &Task, orig: &dyn Fn(&Task) -> u64| {
            sink.lock().unwrap().push(task.name.clone());
            orig(task)
        }
    }

    /// Hooks into accumulate: conditionally skips small children.
    /// By not calling orig, the child result is never folded in.
    fn skip_small_children(threshold: u64)
        -> impl Fn(&mut u64, &u64, &dyn Fn(&mut u64, &u64))
    {
        move |heap: &mut u64, child: &u64, orig: &dyn Fn(&mut u64, &u64)| {
            if *child >= threshold { orig(heap, child); }
        }
    }

    /// Hooks into finalize: clamps the result.
    fn clamp_at(max: u64)
        -> impl Fn(&u64, &dyn Fn(&u64) -> u64) -> u64
    {
        move |heap: &u64, orig: &dyn Fn(&u64) -> u64| orig(heap).min(max)
    }

    /// zipmap contract: a plain Fn(&R) -> Extra. No wrapping needed —
    /// the function itself IS the feature. zipmap calls it per node,
    /// pairing the original result with the derived value: R → (R, Extra).
    fn classify(total: &u64) -> &'static str {
        match *total {
            t if t >= 500 => "critical",
            t if t >= 200 => "heavy",
            _ => "light",
        }
    }

    // ── Graph transformations ───────────────────────────────

    fn only_costly_deps(g: &Treeish<Task>, min_cost: u64) -> Treeish<Task> {
        let inner = g.clone();
        treeish(move |task: &Task| {
            inner.at(task)
                .filter(|child: &Task| child.cost_ms >= min_cost)
                .collect_vec()
        })
    }

    // ── Tests ───────────────────────────────────────────────

    #[test]
    fn test_visit_logger() {
        let (graph, root) = setup();
        let visited = Arc::new(Mutex::new(Vec::new()));
        let fold = base_fold().wrap_init(visit_logger(visited.clone()));

        let total = FUSED.run(&fold, &graph, &root);
        let names: Vec<String> = visited.lock().unwrap().clone();
        assert_eq!(total, 800);
        assert_snapshot!("visit_logger", format!(
            "total={total}, visited: {}", names.join(" → ")
        ));
    }

    #[test]
    fn test_skip_small_children() {
        let (graph, root) = setup();
        let fold = base_fold().wrap_accumulate(skip_small_children(200));
        let total = FUSED.run(&fold, &graph, &root);
        // app(50) + compile(200+typecheck 300) = 550; parse(100) and link(150) skipped
        assert_eq!(total, 550);
        assert_snapshot!("skip_small", format!("total={total} (small children skipped)"));
    }

    #[test]
    fn test_clamp_at() {
        let (graph, root) = setup();
        let fold = base_fold().wrap_finalize(clamp_at(500));
        let total = FUSED.run(&fold, &graph, &root);
        // compile=min(600,500)=500, link=150, app=min(50+500+150,500)=500
        assert_eq!(total, 500);
        assert_snapshot!("clamp_at", format!("total={total} (clamped at 500)"));
    }

    #[test]
    fn test_classify() {
        let (graph, root) = setup();
        let (total, category) = FUSED.run(&base_fold().zipmap(classify), &graph, &root);
        assert_eq!(total, 800);
        assert_eq!(category, "critical");
        assert_snapshot!("classify", format!("total={total}, category={category}"));
    }

    #[test]
    fn test_only_costly_deps() {
        let (graph, root) = setup();
        let filtered = only_costly_deps(&graph, 150);
        let total = FUSED.run(&base_fold(), &filtered, &root);
        // parse(100) pruned: app(50)+compile(200)+typecheck(300)+link(150) = 700
        assert_eq!(total, 700);
        assert_snapshot!("only_costly", format!("total={total} (deps with cost < 150 pruned)"));
    }

    #[test]
    fn test_memoize_diamond() {
        let reg = Registry::new(&[
            ("app", 10, &["compile", "link"]),
            ("compile", 50, &["stdlib"]),
            ("link", 30, &["stdlib"]),
            ("stdlib", 200, &[]),
        ]);
        let visit_count = Arc::new(Mutex::new(0u32));
        let vc = visit_count.clone();
        let map = reg.0.clone();
        let graph = treeish(move |task: &Task| {
            *vc.lock().unwrap() += 1;
            task.deps.iter().filter_map(|d| map.get(d).cloned()).collect()
        });
        let root = reg.get("app").unwrap().clone();

        let total = FUSED.run(&base_fold(), &graph, &root);
        let raw_visits = *visit_count.lock().unwrap();

        *visit_count.lock().unwrap() = 0;
        let cached = memoize_treeish_by(&graph, |t: &Task| t.name.clone());
        let total_memo = FUSED.run(&base_fold(), &cached, &root);
        let memo_visits = *visit_count.lock().unwrap();

        assert_eq!((total, raw_visits), (490, 5));
        assert_eq!((total_memo, memo_visits), (490, 4));
        assert_snapshot!("memoize", format!(
            "raw: total={total} visits={raw_visits}, memo: total={total_memo} visits={memo_visits}"
        ));
    }

    #[test]
    fn test_composed_pipeline() {
        let (graph, root) = setup();
        let visited = Arc::new(Mutex::new(Vec::new()));
        let pipeline = base_fold()
            .wrap_init(visit_logger(visited.clone()))
            .wrap_finalize(clamp_at(500))
            .zipmap(classify);

        let (total, category) = FUSED.run(&pipeline, &graph, &root);
        let names: Vec<String> = visited.lock().unwrap().clone();
        assert_eq!(total, 500);
        assert_eq!(category, "critical");
        assert_snapshot!("composed", format!(
            "total={total} [{category}], visited: {}", names.join(" → ")
        ));
    }
}
}