circuits: traced categories and circuits

⟴ circuits

First-Class Feedback

The free traced monoidal category is the smallest thing you can add to a category to get feedback. Not a library of combinators — a single GADT and a single coinductive type, a hyperfunction no less, connected by this Galois connection ...

~ What we learned building it

⚙️ Install

(m)cabal build circuits

Compiles on MicroHS & GHC 9.10+ with base & profunctors

📡 Usage

import Circuit

-- Fibonacci via knot-tying
>>> take 5 (trace (\(fibs, ()) -> (0 : 1 : zipWith (+) fibs (drop 1 fibs), fibs)) () :: [Integer])
[0,1,1,2,3]

-- Iteration with Either
>>> let step n = if n < 3 then Left (n + 1) else Right n in trace (either step step) (0 :: Int)
3

Representations

Circuit arr t a b is the initial, inspectable encoding (a GADT with Lift, Compose, and Knot). Hyper a b is the final, coinductive encoding in which the feedback channel is structural in the type. The Trace class abstracts the tensor, giving lazy knots via (,) or iteration via Either (with the convention Left feeds back, Right exits).

Conversion is given by reify and encode (and encodeEither/runEither). The core triangle on observables is reify . encode = id.

🧭 Pitch

circuits is a rethink of how to interact with a compiler and arrange code pipelines — circuits — in ways that are intentional, clear, correct and performant.

Hyper is the same as the Kidney & Wu construction:

newtype Hyper a b = Hyper { invoke :: Hyper b a -> b }

From the paper and surrounding literature, we use the hyperfunction axioms and derive a Circuit:

data Circuit arr t a b where
  Lift    :: arr a b -> Circuit arr t a b
  Compose :: Circuit arr t b c -> Circuit arr t a b -> Circuit arr t a c
  Knot    :: arr (t a b) (t a c) -> Circuit arr t b c

This happens to be the initial traced category over a base category and naturally encodes to a Hyper. To be concrete and on the nose, it's a 2-cell bolted on to the free category. Lifting the trace over a category and abstracting the tensor came later.

Have you used your eyeballs yet and read Bartosz's latest? Original thought is a strong claim and could be awkward.

~ claude (tank mode on)

Circuit covers functions, compositional paths, and feedback loops. Hyper is an efficient final encoding where feedback dissolves into the type structure itself. The Trace class (in Circuit.Traced) abstracts the tensor, giving polymorphic loop semantics: lazy knots with (,) or iteration with Either. All braided, cartesian and cocartesian structure lives in Circuit.Monoidal.

other/ traces these ideas from the Kidney & Wu hyperfunctions paper through a narrative arc. Circuit is the initial encoding — a GADT with visible constructors, interpreted by reify. Hyper is the final encoding — a coinductive type where feedback dissolves into the structure itself. The triangle reify = lower . encode connects them.

📦 Sibling libraries

circuits-parser — Circuit (->) Either f (These a f) as a parser for a wide variety of f and a.

circuits-io — Circuit (Kleisli IO) Either as a way to engage with file I/O, sockets, servers, (a)timings & asynchronicity.

circuits-meter — circuit measurement and performance.

📖 Read

"tracing hyperfunctions" — Kidney & Wu (2026). The paper that inspired the core construction. Introduces Hyper as a self-dual object in the traced sense and the hyperfunction axioms.

other/ — the narrative arc (notation, marks-and-stacks, knot, triangle proof, tensors, Mendler case, examples). For the long version.

examples/ — cards: parsers, pipes, Elgot iteration, delimited continuations. Paste code blocks into cabal repl.

Contributing

We welcome contributions of any persuasion or fancy. New contributors should open an issue and say hi.

AI / LLM policy

LLMs and agents have been used in the development of this library, including category theory, coding, generation, refactoring, documentation and narrative.

what we prefer ⟜ all code must compile, have and pass doctests, and be reviewable. ⟜ if you open a PR, you must be able to explain what the code does and why. "my buddy Grok wrote it" is not an explanation. ⟜ do not submit code you have not read, understood, and tested.

what we do not do ⟜ ban AI tools. they are part of the workflow. ⟜ accept code that fails the same standards we apply to AI contributions.

code is code and coders are going to code.