Hylic: Functional recursion crate I just published. Thoughts?

code review
1

Hi all,
I just finished publishing my first crate and would love your thoughts and feedback.

The name's "hylic", because the library helps you formulate hylomorphisms. These are functions that unfold a recursive structure from an atomic value, and collapse that into a result (unfold + fold). The scope of the library is however, more practical and less theoretical in nature :slight_smile:

It's not at all written like the recursion-schemes in Haskell, or the existing recursion crate that already exists: the recursive structure Treeish<Node> is defined external to the Node data structure, allowing for flexibility, and not having to construct the full tree before computing over it.

The point of the library is, to write any recursive algorithm you previously had to define by hand, in terms of two things: Treeish and Fold. Say, Node is a file system directory; you could handle it as Path, as String -- anything. What you want is, to compute some result type Result recursively from it; effectively, you want Node → Result. You have to express your algorithm then in these Treeish and Fold terms. An example is provided in the cookbook:

  • Treeish<Node> (let's call it the graph), which morally corresponds to Node -> &[Node]. Internally it is defined as a callback-based iterator for algorithm efficiency reasons (Rust GAT / HoF typing works slightly better in continuation-passing style because of lifetimes). It's defined in terms of one closure, that defines the graph on the Node domain.
  • Fold<Node,Heap,Result>, which allows you define nonrecursively, what the catamorphism (collapse) looks like at each node. It's defined in terms of three closures: init: Node →Heap, accumulate: mut Heap × Result → Unit [*] and finalize: Heap → Result.

[*] for efficiency: could've more idiomatically expressed it as a fold over Heap, Result: Heap × Result → Heap, but since Heap vanishes at the outside of computation anyways, this fits algorithmic efficiency better.

After formulating your problem in terms of these two pieces, you get:

  • Sequential owned recursion Node → Result
  • Optimized parallel recursion Node → Result; benchmarks show quite good performance, on par with hand-rolled rayon-based performance.
  • Transformability of your Treeish and Fold closures via .map(Node1 → Node2)-style transformers, and Treeish × Fold → Treeish × Fold transformations called "Lifts" (these required quite a bit of typelevel programming to get right)

There's a lot more to be had; transformability means being able to intercept any of the graph or computation structure; e.g. memoization falls out naturally, logging becomes a transformation step that you apply or don't apply, etc.

There's a hylic-pipeline crate that allows you to use a high-fidelity fluent DSL from constructing, through transforming and lifting, to executing computation

I invented this initially because I needed a module resolver, and wanted to explore the possibilities Rust gives me, coming from Scala 3.

Let me know what you think please :slight_smile:
Disclaimer: an LLM agent helped me to polish the library surface; I did not use LLMs to write the core design and where LLMs have been used, I supervised them closely.

some more notes:

Instead of the approach that recursion crate and recursion schemes (Haskell) take, you define the treeish structure external to the data you compute over. Your data does NOT have to be in categoric tree morphism/functorial shape. I found a great Analogy by Bartosz Milewski that I discuss in one of the appendix articles of the docs -- how my library meshes with a (purely) monoidal catamorphism as sketched by Milewski: https://hylic-recursion.github.io/hylic-docs/design/milewski.html

On the boxing (Arc/Rc/Box/Id) front: I have gone to great lengths, to make the system NOT coerce you into Send + Sync bounds on your domain (as consequence of Arc-wrapped representation of your closures as e.g. rayon demands). For using parallel execution, your Node types will have to be Send + Sync however, and your Fold heap will need to be cloneable. See https://hylic-recursion.github.io/hylic-docs/concepts/domains.html

2 Likes