Idris Pattern Matching with Existential Types Explained

Idris’ type checker demands explicit constructor matching when pattern matching on existential types like EqNat to refine dependent goals and access embedded equality proofs. Swapping Just (Same _) for Just _ triggers a type mismatch because the wildcard skips deconstructing the existential package, so the proof that two Nat values are equal never enters scope—regardless of EqNat having just one constructor, Same. This setup ensures proofs propagate precisely, preventing silent type errors in dependent contexts.

Contents

• Idris Pattern Matching Fundamentals
• Existential Types and Dependent Pairs
• EqNat: A Single-Constructor Existential
• Why Just _ Breaks Type Refinement
• Dependent Matching and Name Alignment
• Workarounds: rewrite, with, and Views
• Common Pitfalls in Idris Existentials
• Sources
• Conclusion

Idris Pattern Matching Fundamentals

Pattern matching in Idris isn’t just syntactic sugar—it’s the engine driving type refinement, especially with dependent types. You match on data constructors to peel back layers, letting the type checker infer equalities and shrink goals automatically. But throw in existentials, and things get picky fast.

Take a simple case: case someValue of Just x => .... Here, x gets typed as the payload inside Just. Easy. Now imagine that payload is an existential like a dependent pair (x ** p) where p proves something about x. A plain wildcard? It hides everything, no refinement happens. The type checker shrugs and says, “Prove it yourself.”

Why care? Because Idris erases proofs at runtime but checks them rigorously upfront. Matching Just (MkDPair x p) explicitly binds x and p, so later goals like “show this list has length x” become trivial—p handles it. Skip the constructor, and you’re stuck proving lengths from scratch. It’s like handing the checker a locked box without the key.

This behavior shines in proofs. Idris’ official docs on pattern matching proofs explain how equality proofs refine types on the fly. Match on plus_commutes_S k (S j), and rewrite kicks in automatically if you name it right.

Existential Types and Dependent Pairs

Existentials in Idris pack a witness and its proof together—think sigma types, (x : A) ** (P x). They’re everywhere: Maybe (x ** proof), filter results on vectors, even IO under the hood. Formally, they’re existential quantification: “there’s some x such that P x holds.”

Pattern matching them? You must crack open the constructor to grab both parts. The types and functions tutorial nails this: for filter p (x :: xs) with (filter p xs) | (_ ** xs') => ..., the wildcard on the first part loses the length proof. Boom—your Vect turns into a plain List, and lengths don’t match up.

Why so strict? Type refinement relies on scoping the proof. Hide it behind _, and unification can’t bridge A x to A y without evidence. Humans might think “only one constructor, so whatever,” but the checker doesn’t guess—it demands you say “unpack this Same proof here.”

Picture data EqNat : Nat -> Nat -> Type where Same : (x = y) -> EqNat x y. That’s your existential: witness is the proof x = y. Matching Just (Same prf) binds prf : x = y, refining everything downstream. Just _? No prf, no magic.

EqNat: A Single-Constructor Existential

EqNat packs equality as an existential: data EqNat : Nat -> Nat -> Type where Same : {x, y : Nat} -> (x = y) -> EqNat x y. Single constructor, sure. But that {x = y} proof is the star—it’s what lets you swap indices in dependent types.

In a function like:

eqNatCase : (n, m : Nat) -> EqNat n m -> Vect n a -> Vect m a
eqNatCase n m (Same Refl) xs = xs -- refinement works!

The Same Refl match gives n = m for free, so Vect n a becomes Vect m a. Replace with Same _? Still binds the proof implicitly. But Just (Same _) in a Maybe EqNat? It scopes the equality.

Now, Just _? The payload stays opaque. No proof scopes, so if your goal needs Vect n a to prove Vect m a, you’re toast—type mismatch city.

Even single-constructor types demand this. Builtin docs confirm: dependent pairs need constructor deconstruction; wildcards erase the existential’s punch.

Why Just _ Breaks Type Refinement

Here’s the heart of your question. Say you’ve got case maybeEq of Just eq => useVect eq xs | Nothing => []. With eq : EqNat n m, but if maybeEq : Maybe (EqNat n m), then:

• Just (Same prf) binds prf : n = m, refines useVect to accept xs : Vect n a for Vect m a.

• Just _ binds something, but not the proof. The type checker sees “some unknown EqNat p q”, not tied to n, m. Unification fails: can’t prove Vect n a matches Vect ?p a.

Even with one constructor, _ doesn’t invoke it. It’s like peeking without opening the envelope—the proof’s there, but unscoped. Result? “Type mismatch between Vect n a (Functional 0) and Vect m a (Functional 0).”

Tried it yourself? You’ll see the error pinpoints the case branch. The checker simulates coverage but bails on refinement.

Dependent Matching and Name Alignment

Names matter a lot. GitHub issue #4538 exposes this: data A : a -> Type where Ca : (x : y) -> A x. Matching f (Ca x) = ... works if x matches the signature’s binder. Ca y? Mismatch: A y vs A x.

For existentials, binders must align for proof propagation. Same {auto x y} prf—use x, y in patterns, or lose scoping.

This catches sloppy code early. Wildcard dodges naming but skips refinement entirely.

Workarounds: rewrite, with, and Views

Stuck? Don’t fight—use tools.

rewrite: rewrite prf in goal swaps types using equality. From proofs docs: rewrite plus_commutes_S k j in Refl.

with-rule: For dependent intermediates. Views tutorial: foo n m with (succ n) | 2 with (succ m) refines scopes.

Views: Custom patterns for existentials. Define a view cracking EqNat, match uniformly.

Explicit always wins for clarity. case mb of Just (Same {x} {y} prf) => rewrite prf in ....

Common Pitfalls in Idris Existentials

1. Wildcard laziness: _ hides proofs—always name constructors first.

2. Name shadows: Binders must match datatypes exactly.

3. Runtime erasure: Patterns check statically; no voodoo at runtime.

4. Single constructor myth: One con doesn’t mean auto-wildcard. Idris2 issue #499 gripes about irrelevant singles needing full matches.

5. Type vs data: Can’t match Type directly—Stack Overflow warns: constructors only.

Debug tip: :printdef your function, see refined types per branch. Game‑changer.

And yeah, it feels finicky at first. But once it clicks? Proofs flow effortlessly.

Sources

1. Pattern Matching Proofs — Official documentation on equality refinement in patterns: https://docs.idris-lang.org/en/latest/proofs/patterns.html
2. Types and Functions — Tutorial on dependent pairs and existential matching: https://docs.idris-lang.org/en/latest/tutorial/typesfuns.html
3. Dependant type requires matching name — GitHub issue detailing binder alignment in patterns: https://github.com/idris-lang/Idris-dev/issues/4538
4. Views and the “with” rule — Guide to refining dependent patterns with with-rule: https://docs.idris-lang.org/en/latest/tutorial/views.html
5. Builtin — Documentation on dependent pairs and existential deconstruction: https://test.idris-lang.org/Idris2/prelude/docs/Builtin.html

Conclusion

Idris’ type checker treats existential pattern matching as a proof gateway—explicit constructors like Same unlock refinements that wildcards bury. That Just _ mismatch? It’s by design, forcing you to handle proofs head‑on, even for single‑constructor types. Master this, and dependent programming feels like magic; ignore it, and you’re wrestling types endlessly. Dive into the docs, experiment in REPL, and it’ll stick.