Blog › ICP guides

Agda developer on retainer: dependent types, Vec A n length-indexed vectors, propositional equality, rewrite tactics, totality checking, and Agda proof assistant on monthly retainer

November 27, 2026 · ~15 min read

An Agda program implementing a proof that vector concatenation is associative — (xs ++ ys) ++ zs ≡ xs ++ (ys ++ zs) for Agda’s Vec A n type — had stalled on a persistent rewrite failure. The developer was proving this for Vec A where xs : Vec A n, ys : Vec A m, zs : Vec A k. The left side of the equality computed to Vec A (n + (m + k)) through the recursive structure of _++_, but the right side needed Vec A ((n + m) + k). Agda’s definitional equality cannot unify n + (m + k) and (n + m) + k automatically — addition on Nat is defined by recursion on the left argument, so n + (m + k) reduces definitionally but (n + m) + k does not reduce to the same normal form. The proof required an explicit rewrite using the associativity lemma for natural number addition: +-assoc : (n m k : ℕ) → (n + m) + k ≡ n + (m + k). The developer placed the rewrite +-assoc n m k after the recursive step, but the rewrite target was wrong — they rewrote the occurrence of n + (m + k) in a context where the proof goal expected (n + m) + k on the left side of the equality. The rewrite tactic substitutes equals-for-equals in the goal, changing all occurrences of the left side of the equality argument to the right side; using +-assoc n m k (which proves (n + m) + k ≡ n + (m + k)) rewrites occurrences of (n + m) + k to n + (m + k) in the goal — the wrong direction. The developer needed rewrite sym (+-assoc n m k) to rewrite occurrences of n + (m + k) to (n + m) + k, matching the goal. Five rewrite failures per proof attempt. The Agda developer on retainer diagnosed the rewrite direction mismatch and restructured using rewrite sym (+-assoc n m k) on the goal; the proof compiled with zero rewrite failures.

The work log entry read “fixed Vec associativity proof, 7h.” It names the task and duration. It cannot explain why rewrite +-assoc n m k fails while rewrite sym (+-assoc n m k) succeeds — the sym combinator reverses the direction of a propositional equality proof, converting a ≡ b to b ≡ a; the rewrite tactic substitutes equals-for-equals in the current goal, replacing occurrences of the left side of the equality argument with the right side; to rewrite n + (m + k) to (n + m) + k in the goal, the equality argument passed to rewrite must have n + (m + k) on the left — which is sym (+-assoc n m k), not +-assoc n m k. It cannot explain why Agda’s definitional equality makes this necessary — if _+_ were defined to reduce on either argument, n + (m + k) and (n + m) + k might be definitionally equal and no rewrite would be needed; the standard library’s _+_ is defined by recursion on the first argument only, so the two expressions do not reduce to a common normal form and propositional equality with explicit rewrite is required. It cannot explain the retainer’s use of cong to apply the equality inside a type constructor when the rewrite target was nested inside Vec A (...). The 7 hours of Agda proof term construction, rewrite direction analysis, and sym/cong application are invisible in the diff.

Agda dependent types: Vec A n, propositional equality, rewrite tactics, sym, cong, and with-clauses

Vec A n is Agda’s canonical length-indexed vector type: a vector of elements of type A whose length n is encoded as a Nat in the type itself. This encoding makes the length a static invariant: the type system prevents out-of-bounds access at compile time because any function that indexes into a Vec A n must supply a proof that the index is within bounds, and the type of head is Vec A (suc n) → A, requiring the caller to provide a vector with a length of at least one before head is even well-typed. There is no runtime bounds check and no runtime failure from indexing into an empty vector; the totality of the head function is guaranteed by the type index.

Propositional equality in Agda is the identity type _≡_, defined with a single constructor refl : a ≡ a, which proves that a term equals itself definitionally. To prove a ≡ b for terms a and b that are not definitionally equal — that is, terms that do not reduce to a common normal form under Agda’s reduction rules — a proof term must be explicitly constructed. The standard library provides sym : a ≡ b → b ≡ a for reversing an equality, trans : a ≡ b → b ≡ c → a ≡ c for chaining two equalities, and cong : (f : A → B) → a ≡ b → f a ≡ f b for lifting an equality through a function. The cong combinator is essential when the equality goal has the form F a ≡ F b for some type constructor F and proof p : a ≡ b is available — the goal follows from cong F p. When the equality is nested several type constructors deep, a chain of cong applications is required, each lifting the equality one level outward.

The rewrite tactic simplifies propositional equality proof construction by allowing goal transformation. Given a proof p : a ≡ b, rewrite p replaces all occurrences of a in the current goal with b, producing a new, simplified goal that may be easier to close. The direction is left-to-right: rewrite p rewrites a to b where p : a ≡ b. To rewrite in the opposite direction, rewrite sym p rewrites b to a. The rewrite tactic does not rewrite hypotheses in the context unless explicitly invoked on them; it operates only on the goal. Multiple rewrites can be chained in sequence or applied simultaneously.

Agda’s totality checker enforces that all functions are total: defined for all inputs and terminating on all inputs. Totality is checked by structural recursion analysis — recursive calls must be made on structurally smaller arguments. A function over Vec A (suc n) must pattern-match on the (x &cons; xs) constructor covering the non-empty case; omitting the [] case for the empty vector produces a totality error because the function is not defined for all Vec A n. When a case is statically unreachable — for example, a branch that would require zero ≡ suc n, which is uninhabited — the absurd pattern () signals to Agda that no proof of that case exists and no body is required, satisfying the totality checker without providing dead code. With-clauses extend Agda’s pattern matching with auxiliary pattern matching: a with expression pulls a subterm into the pattern match context, allowing dependent pattern matching on its structure while keeping the other terms in scope. The inspect idiom augments with pattern matching by retaining the equality proof f x ≡ c in the context when the branch matches f x to c, allowing the proof to be used in the body of the clause.

Agda module system and universe levels

Agda’s module system supports parameterized modules: module Vec (A : Set) declares a module where all declarations inside share the A type parameter without needing to thread it through every signature. The module is instantiated at use sites with open Vec ℕ using (...) or similar, substituting the concrete type for the parameter. Declarations inside a module can be marked private to prevent external importers from accessing them by name; private declarations are still used internally by other module members but are not exposed as part of the module’s public interface. Fine-grained control over which names are brought into scope is provided by open M using (f; g) (import only f and g) and open M renaming (f to f') (import f under the alias f'), both of which can be combined in a single open declaration.

Instance arguments, written {{x : X}}, enable automatic instance resolution: Agda searches for an in-scope value of type X and fills in the argument without explicit passing at call sites. This is Agda’s mechanism for type class-like dispatch, equivalent to Haskell’s type class instances. Common uses include Eq for decidable equality, Show for string conversion, and Decidable for decision procedures. When no instance is found in scope, Agda reports an unsolved instance meta rather than a type error, which can be addressed by importing the relevant instance declaration or providing the argument explicitly.

Universe levels address Girard’s paradox: in a type theory where Set : Set (the type of all types is itself a type), logical inconsistency arises. Agda stratifies types into a hierarchy: Set : Set⊂1, Set⊂1; : Set⊂2, and so on. Universe polymorphism allows definitions to be parameterized over a level: Set ℓ where ℓ : Level is a universe-polymorphic type, and ℓ-max : Level → Level → Level computes the maximum of two levels for definitions that combine types at different universe levels. Universe level constraints are solved by Agda’s constraint solver; when the constraints are unsatisfiable (for example, when a type at level ℓ is used where level ℓ + 1 is required), Agda reports a level mismatch that requires explicit level annotation or restructuring.

Agda was developed by Ulf Norell at Chalmers University of Technology in 2007 as the successor to the earlier Agda system by Catarina Coquand; it is an interactive proof assistant and dependently typed programming language based on Martin-Löf type theory. Its closest retainer-ecosystem relatives are Idris (also dependently typed, with a stronger focus on general-purpose programming and tactics) and Coq/Rocq (proof assistant with a tactic-based proving mode rather than direct proof term construction), but Agda’s direct proof term construction style, with-clause dependent pattern matching, and rewrite tactic discipline make retainer work distinct in propositional equality engineering, universe level management, and totality proof structuring.

How HourTab tracks Agda developer retainer hours

Agda retainer work carries the invisible-work problem of all dependent-type proof engineering, amplified by the gap between the visible artifact — a proof that type-checks — and the invisible hours of Martin-Löf type theory reasoning that produced it. Teams building mechanized mathematics or high-assurance verified software in Agda routinely encounter the rewrite direction pattern: a developer knows that an associativity lemma exists, applies it with rewrite, sees a failure, and spends hours determining that the issue is not the lemma itself but its orientation relative to the current goal. The five rewrite failures per attempt described above are five instances of the same underlying mismatch — the goal expects n + (m + k) on the left, the lemma places (n + m) + k on the left, and sym is required to invert the direction. The retainer work is the type theory reasoning that identifies the direction mismatch and the sym insertion that resolves it.

Agda retainers produce visible outcomes — rewrite failures: 5/attempt → 0; totality checker rejections: 3/function → 0 — but the hours that produce those outcomes appear in the work log as “fixed proof” or “resolved type error” without conveying the depth of reasoning involved. Proof term construction, rewrite direction analysis, with-clause auxiliary pattern matching design, universe level reasoning, and absurd-pattern totality structuring are all rendered invisible by a line that says “7h.” HourTab gives Agda developers a public retainer-hours URL per client retainer — one link, no login required, live burn-down visible to the client at any time. The work log attached to the burn-down transforms the invisible hours into evidence: each entry names the mechanism (Vec A n rewrite direction repair; totality absurd pattern addition; with-clause auxiliary pattern match design; universe level polymorphism; sym/cong/trans chain construction), the specific proof goal and equality lemma involved, and the before/after metric, so the client understands why seven hours of work on a single proof is not gold-plating but the irreducible cost of dependent type proof engineering.

The ideal customer profile for Agda developer retainers covers three groups: proof engineering teams at research institutions using Agda for mechanized mathematics (formalized number theory, category theory, type theory meta-theory); Agda developers at companies using dependent types for high-assurance software (verified compilers, certified cryptographic protocols, formally verified hardware descriptions); and Agda consultants advising teams on verified program construction, proof architecture, and migration from informal specifications to mechanically checked Agda proofs. In all three cases, the work log that HourTab exposes to the client is the primary evidence that the retainer hours are being spent on genuine proof engineering depth rather than routine maintenance — and it is the evidence that gets the retainer renewed.

FAQ: Agda developer retainers