Lifts — cross-axis transforms

The problem

The transforms in the previous chapter act on a single structure — a Fold or a Graph, not both. Some rewrites, however, must touch both in a coordinated manner: a change of node type that the Graph produces and the Fold consumes; a filter that drops edges and must therefore also leave the Fold structurally consistent with what remains; a per-node trace that wraps the Fold’s output and composes with whatever other transforms are already in place.

A Lift is the object that performs such cross-axis rewrites. It operates on the full triple carried by a pipeline, not on one slot in isolation, and composes with other lifts to form a chain.

Why three axes

Besides Fold<N, H, R> and Graph<N>, there’s a third slot: Grow<Seed, N> — a closure that resolves a Seed into an N. Most users never build a Grow by hand; SeedPipeline constructs one from grow: Seed → N. But because lifts compose and some pipelines carry a Grow, the trait has to account for it.

Three slots, not two. The Lift trait threads all three through composition. A lift that doesn’t care about Grow (say, a fold-wrapper) passes it unchanged. A lift that does care (the N-change lifts; SeedLift) rewrites it in concert with the other slots.

The trait

#![allow(unused)]
fn main() {
/// Domain-generic transformer over the `(treeish, fold)` pair.
///
/// A `Lift` rewrites the graph side and/or the fold side, possibly
/// changing their carrier types, and hands the result to a
/// continuation. The caller's continuation-return type `T` flows
/// through, so the chain of output types stays inferred across
/// composition (`ComposedLift<L1, L2>`).
///
/// Grow is deliberately absent from this signature. Only the Seed
/// finishing lift ([`SeedLift`](super::SeedLift)) needs a grow
/// input; it is composed internally by
/// `hylic_pipeline::PipelineExecSeed::run` and does not travel as
/// a 3-slot signature through the `Lift` trait.
///
/// See [Lifts](https://hylic.balcony.codes/concepts/lifts.html).
pub trait Lift<D, N, H, R>
where D: Domain<N> + Domain<Self::N2>,
      N: Clone + 'static, H: Clone + 'static, R: Clone + 'static,
{
    /// Output node type after the lift has been applied.
    type N2:   Clone + 'static;
    /// Output heap type after the lift has been applied.
    type MapH: Clone + 'static;
    /// Output result type after the lift has been applied.
    type MapR: Clone + 'static;

    /// Apply the lift to `(treeish, fold)` and invoke `cont` with
    /// the transformed pair.
    fn apply<T>(
        &self,
        treeish: <D as Domain<N>>::Graph<N>,
        fold:    <D as Domain<N>>::Fold<H, R>,
        cont: impl FnOnce(
            <D as Domain<Self::N2>>::Graph<Self::N2>,
            <D as Domain<Self::N2>>::Fold<Self::MapH, Self::MapR>,
        ) -> T,
    ) -> T;
}
}

Three associated output types (N2, MapH, MapR) and a single apply method. As a type-level arrow:

L : (Grow<Seed, N>, Graph<N>, Fold<N, H, R>)
  → (Grow<Seed, L::N2>, Graph<L::N2>, Fold<L::N2, L::MapH, L::MapR>)

Quick start

Most users never interact with the Lift trait directly; the pipeline sugars are the usual surface, and each sugar delegates to a library lift. A small example demonstrates what a lift changes at the value level:

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

        let t:   Treeish<u64>      = treeish(|n: &u64| if *n > 0 { vec![*n - 1] } else { vec![] });
        let fld: Fold<u64, u64, u64> = fold(|n: &u64| *n, |h: &mut u64, c: &u64| *h += c, |h: &u64| *h);

        // Wrap init to add +1 at each node.
        let wi = Shared::wrap_init_lift::<u64, u64, u64, _>(|n, orig| orig(n) + 1);
        let r:  u64 = wi.run_on(&FUSED, t, fld, &3u64);
        // Tree 3→2→1→0: 4 nodes, each +1 → 4 extra → 6 + 4 = 10.
        assert_eq!(r, 10);
    }
}

wrap_init_lift accepts a closure that intercepts every call to init. The pipeline’s R is unchanged; only the per-node init closure is wrapped. The remaining sugars follow the same pattern: select an axis, supply the transformation as a closure, obtain a new pipeline that differs only along that axis.

The Library catalogue below lists the axes touched by each library lift.

Four atoms

Every library lift is an instance of one of four types. The sugars compose these atoms without requiring any of them to be constructed by hand; this section names the parts so that they are recognisable in compiler errors and in custom-lift implementations.

IdentityLift — pass-through. Used as the seed of a lift chain when a Stage-1 pipeline transitions to Stage 2 via .lift().

#![allow(unused)]
fn main() {
/// The pass-through lift — the unit of lift composition. Leaves
/// every slot unchanged.
pub struct IdentityLift;
}

ComposedLift<L1, L2> — sequential composition. L1 runs first; L2 takes L1’s outputs as its inputs.

#![allow(unused)]
fn main() {
/// Sequential composition of two lifts. `L1` runs first; `L2`
/// takes `L1`'s outputs as its inputs. The outer lift's `apply`
/// drives this composition.
#[must_use]
pub struct ComposedLift<L1, L2> {
    pub(crate) inner: L1,
    pub(crate) outer: L2,
}
````<div class="mdbook-graphviz-output"><!-- Generated by graphviz version 2.43.0 (0) --><!-- Title: %3 Pages: 1 --><svg width="607pt" height="44pt" viewBox="0.00 0.00 607.00 44.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"><g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 40)"><title>%3</title><polygon fill="white" stroke="transparent" points="-4,4 -4,-40 603,-40 603,4 -4,4"/><!-- in --><g id="node1" class="node"><title>in</title><path fill="#e8f5e9" stroke="black" d="M59,-36C59,-36 12,-36 12,-36 6,-36 0,-30 0,-24 0,-24 0,-12 0,-12 0,-6 6,0 12,0 12,0 59,0 59,0 65,0 71,-6 71,-12 71,-12 71,-24 71,-24 71,-30 65,-36 59,-36"/><text text-anchor="middle" x="35.5" y="-15.5" font-family="monospace" font-size="10.00">(N, H, R)</text></g><!-- mid --><g id="node2" class="node"><title>mid</title><path fill="#fff3cd" stroke="black" d="M323,-36C323,-36 162,-36 162,-36 156,-36 150,-30 150,-24 150,-24 150,-12 150,-12 150,-6 156,0 162,0 162,0 323,0 323,0 329,0 335,-6 335,-12 335,-12 335,-24 335,-24 335,-30 329,-36 323,-36"/><text text-anchor="middle" x="242.5" y="-15.5" font-family="monospace" font-size="10.00">(L1::N2, L1::MapH, L1::MapR)</text></g><!-- in&#45;&gt;mid --><g id="edge1" class="edge"><title>in&#45;&gt;mid</title><path fill="none" stroke="black" d="M71.28,-18C90.35,-18 115.09,-18 139.77,-18"/><polygon fill="black" stroke="black" points="139.96,-21.5 149.96,-18 139.96,-14.5 139.96,-21.5"/><text text-anchor="middle" x="110.5" y="-20.8" font-family="sans-serif" font-size="9.00">L1::apply</text></g><!-- out --><g id="node3" class="node"><title>out</title><path fill="#e3f2fd" stroke="black" d="M587,-36C587,-36 426,-36 426,-36 420,-36 414,-30 414,-24 414,-24 414,-12 414,-12 414,-6 420,0 426,0 426,0 587,0 587,0 593,0 599,-6 599,-12 599,-12 599,-24 599,-24 599,-30 593,-36 587,-36"/><text text-anchor="middle" x="506.5" y="-15.5" font-family="monospace" font-size="10.00">(L2::N2, L2::MapH, L2::MapR)</text></g><!-- mid&#45;&gt;out --><g id="edge2" class="edge"><title>mid&#45;&gt;out</title><path fill="none" stroke="black" d="M335.13,-18C357.27,-18 381.06,-18 403.64,-18"/><polygon fill="black" stroke="black" points="403.92,-21.5 413.92,-18 403.92,-14.5 403.92,-21.5"/><text text-anchor="middle" x="374.5" y="-20.8" font-family="sans-serif" font-size="9.00">L2::apply</text></g></g></svg></div>



The type-level bound `L2: Lift<D, L1::N2, L1::MapH, L1::MapR>`
enforces the connection. A mistake here surfaces as a compile
error at the composition site.

**`ShapeLift<D, N, H, R, N2, H2, R2>`** — the universal library
lift. Stores three per-domain xforms (one per slot) and applies
them in sequence.

````rust
/// The universal library `Lift` — stores one xform per slot
/// (treeish, fold) and applies them during `apply`. Every library
/// lift except `SeedLift` is a `ShapeLift` with appropriate xforms.
#[must_use]
pub struct ShapeLift<D, N, H, R, N2, H2, R2>
where D: ShapeCapable<N> + Domain<N2>,
      N:  Clone + 'static, H:  Clone + 'static, R:  Clone + 'static,
      N2: Clone + 'static, H2: Clone + 'static, R2: Clone + 'static,
{
    pub(crate) treeish_xform: D::TreeishXform<N2>,
    pub(crate) fold_xform:    D::FoldXform<H, R, N2, H2, R2>,
}
}

Every concrete library lift is a ShapeLift with appropriate xforms. wrap_init_lift only rewrites Fold’s init phase; filter_edges_lift only rewrites Graph’s visit; n_lift rewrites all three; explainer_lift rewrites only Fold (but changes MapH and MapR to the explainer’s wrapper types).

SeedLift<D, N, Seed, H> — a finishing lift that closes a SeedPipeline by turning the (grow, seeds_from_node, fold) triple into a runnable (treeish, fold) pair rooted at an EntryRoot variant. Domain-parametric over ShapeCapable (Shared + Local impls; per-domain because the fold-construction closures’ Send+Sync discipline differs by domain). Assembled at run time inside the seed-rooted Stage2Pipeline::run(...) from the base’s grow plus the caller-supplied root_seeds and entry_heap, then composed as the first lift of the run-time chain.

#![allow(unused)]
fn main() {
/// The finishing lift that closes a `SeedPipeline`'s grow axis.
/// Composes entry-seed dispatch on top of a `(grow, seeds, fold)`
/// triple and produces a treeish over `SeedNode<N>`. Not
/// user-constructed; assembled internally by
/// `Stage2Pipeline::run` at call time.
///
/// Domain-parametric: storage of the entry-seeds graph and the
/// entry-heap thunk is per-domain via `<D as Domain<()>>::Graph<Seed>`
/// and `<D as ShapeCapable<N>>::EntryHeap<H>`. No hand-rolled
/// domain discriminator.
#[must_use]
pub struct SeedLift<D, N, Seed, H>
where D: ShapeCapable<N> + Domain<()>,
      N: 'static, Seed: 'static, H: 'static,
{
    pub(crate) grow:          <D as Domain<N>>::Grow<Seed, N>,
    pub(crate) entry_seeds:   <D as Domain<()>>::Graph<Seed>,
    pub(crate) entry_heap_fn: <D as ShapeCapable<N>>::EntryHeap<H>,
    _m: PhantomData<fn() -> (D, N, Seed, H)>,
}
}

Its N2 is SeedNode<N> — a sealed row type whose variants are library-internal; user code inspects via is_entry_root(), as_node(), map_node(f). Two inhabitants: the synthetic EntryRoot (root fan-out over entry seeds) and a resolved Node(N). SeedLift builds a Treeish<SeedNode<N>> that dispatches on variant: EntryRoot visits the entry seeds via grow, Node visits the user’s treeish.

For an N-typed view of a seed-closed .explain() result, convert the raw ExplainerResult<SeedNode<N>, H, R> to SeedExplainerResult via raw.into() — see seed explainer result.

Bare application

Any Lift is usable without a pipeline. LiftBare is a blanket trait:

#![allow(unused)]
fn main() {
/// Blanket trait extending any [`Lift`] with direct application to
/// a bare `(treeish, fold)` pair. Implemented automatically; users
/// call `.apply_bare(...)` or `.run_on(...)` without a pipeline.
pub trait LiftBare<D, N, H, R>: Lift<D, N, H, R>
where D: ShapeCapable<N> + Domain<Self::N2>,
      N: Clone + 'static, H: Clone + 'static, R: Clone + 'static,
      Self::N2:   Clone + 'static,
      Self::MapH: Clone + 'static,
      Self::MapR: Clone + 'static,
{
    /// Apply this lift to a bare (treeish, fold) pair; return the
    /// transformed pair.
    fn apply_bare(
        &self,
        treeish: <D as Domain<N>>::Graph<N>,
        fold:    <D as Domain<N>>::Fold<H, R>,
    ) -> (<D as Domain<Self::N2>>::Graph<Self::N2>,
          <D as Domain<Self::N2>>::Fold<Self::MapH, Self::MapR>)
    {
        self.apply(treeish, fold, |t, f| (t, f))
    }

    /// Apply this lift and run the result under the given executor.
    fn run_on<E>(
        &self,
        exec:    &E,
        treeish: <D as Domain<N>>::Graph<N>,
        fold:    <D as Domain<N>>::Fold<H, R>,
        root:    &Self::N2,
    ) -> Self::MapR
    where
        E: Executor<
            Self::N2, Self::MapR, D,
            <D as Domain<Self::N2>>::Graph<Self::N2>,
        >,
        <D as Domain<Self::N2>>::Graph<Self::N2>: TreeOps<Self::N2>,
    {
        let (t, f) = self.apply_bare(treeish, fold);
        exec.run(&f, &t, root)
    }
}
}

See Bare lift application in the Pipelines overview for the rationale and the panic-grow trick that lets LiftBare skip the grow slot.

Per-domain capability

Not every domain supports ShapeLift. A domain has to declare what it can store as a per-slot xform:

#![allow(unused)]
fn main() {
#[allow(missing_docs)] // associated types/methods are implementation plumbing for ShapeLift
pub trait ShapeCapable<N: 'static>: Domain<N> {
    type GrowXform<N2: 'static>: Clone + 'static;
    type TreeishXform<N2: 'static>: Clone + 'static;
    type FoldXform<H, R, N2, H2, R2>: Clone + 'static
    where H: 'static, R: 'static, N2: 'static, H2: 'static, R2: 'static;

    fn apply_grow_xform<Seed: 'static, N2: 'static>(
        t: &Self::GrowXform<N2>,
        g: <Self as Domain<N>>::Grow<Seed, N>,
    ) -> <Self as Domain<N2>>::Grow<Seed, N2>
    where Self: Domain<N2>;

    fn apply_treeish_xform<N2: 'static>(
        t: &Self::TreeishXform<N2>,
        g: <Self as Domain<N>>::Graph<N>,
    ) -> <Self as Domain<N2>>::Graph<N2>
    where Self: Domain<N2>;

    fn apply_fold_xform<H, R, N2, H2, R2>(
        t: &Self::FoldXform<H, R, N2, H2, R2>,
        f: <Self as Domain<N>>::Fold<H, R>,
    ) -> <Self as Domain<N2>>::Fold<H2, R2>
    where Self: Domain<N2>,
          H: 'static, R: 'static, N2: 'static, H2: 'static, R2: 'static;

    fn identity_grow_xform() -> Self::GrowXform<N>
    where N: Clone;

    fn identity_treeish_xform() -> Self::TreeishXform<N>
    where N: Clone;

    fn identity_fold_xform<H: 'static, R: 'static>() -> Self::FoldXform<H, R, N, H, R>;

    /// Compose a `grow: Seed → N` with a `seeds: Graph<Seed>` to
    /// produce the fused `Graph<N>` (treeish). Needed by
    /// `SeedPipeline::with_constructed` which yields a treeish over
    /// N to the executor.
    fn fuse_grow_with_seeds<Seed: 'static>(
        grow:  <Self as Domain<N>>::Grow<Seed, N>,
        seeds: <Self as Domain<N>>::Graph<Seed>,
    ) -> <Self as Domain<N>>::Graph<N>
    where Seed: Clone;

    /// Storage type for `SeedLift`'s entry-heap thunk: a
    /// `Fn() -> H` whose backing pointer matches the domain's
    /// closure-storage discipline (Arc on Shared, Rc on Local).
    /// Used in place of a hand-rolled domain discriminator enum.
    type EntryHeap<H: 'static>: Clone + 'static;
}

}

Shared and Local are ShapeCapable — each storage uses its own pointer type (Arc vs Rc) and closure bounds (Send + Sync vs none). Owned is not ShapeCapable: Box<dyn Fn> is not Clone, so xforms can’t be applied to produce a new owned fold. Owned pipelines have no Stage-2 surface.

Parallel vs sequential

Two blanket markers gate which executors a lift can feed:

• PureLift<D, N, H, R> — any Lift + Clone + 'static with Clone outputs. Sufficient for the sequential executor Fused.
• ShareableLift<D, N, H, R> — adds Send + Sync on everything. Required for the parallel Funnel executor.

You don’t implement these; the compiler picks them up via blanket impls in ops::lift::capability. If your lift (or your data) doesn’t meet the parallel bounds, calling .run(&funnel_exec, ...) is a compile error — there’s no silent fallback.

Library catalogue

Each ShapeCapable domain exposes a set of constructors that return a ShapeLift shaped for the transformation. For Shared:

Local mirrors the set (except explainer_describe_lift), with Rc storage and no Send + Sync bounds.

The last two (phases_lift, treeish_lift) are the primitives: the per-axis sugars all delegate to one of them. n_lift is the primitive for coordinated N-change; map_n_bi_lift is the bijective special case.

Appendix: why the trait takes a continuation

This section is relevant only to writing a custom Lift implementation; it explains the signature rather than the everyday use of lifts.

A direct signature would return the transformed triple from apply. The return type of such a form is (Grow<D, Seed, N2>, Graph<D, N2>, Fold<D, N2, H2, R2>), each component a domain-associated GAT and each axis an associated type of the lift. Following three chained lifts, the return type admits no nameable alias.

Continuation-passing style — “CPS” in the source and in some comments — avoids this. The caller supplies apply with a closure (the continuation cont), which apply invokes with the transformed triple. Because the continuation’s return type propagates outward, Rust’s type inference threads every intermediate through end-to-end, and no intermediate requires a nameable alias.

Consequently, every pipeline’s .run(...) reduces to a single descent through the lift chain via nested apply calls, each closing over the next. The chain is constructed at the type level, evaluated once at the value level, and the executor ultimately sees only the final (treeish, fold) pair.