Files
skills/public/dependent-types.html
zeekay 747dafba10 Register WebMCP tools on every page, and name each page's twin from site.py
Every page now loads /webmcp.js, scripts/webmcp.ts with its types
stripped (npm run webmcp). Where the browser has document.modelContext
it registers two read-only tools: search_skills over the published
skills index, and get_skill, which returns a skill's markdown checked
against the index digest. The markdown alternate link moves from
build.py to site.py, so CI holds every page to it.

The API catalog gains the site itself (llms.txt and the skills index)
and hanzo.ai/agents; the live discovery check now fetches every
catalog link. tests/site.mjs drives the tools through a recording
modelContext, and checks a browser without one loads clean.
2026-10-26 20:57:05 -07:00

528 lines
24 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<!doctype html>
<html lang="en"><head>
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
<title>dependent-types</title>
<meta name="color-scheme" content="dark">
<style>
/* Committed to one visual world: a dark instrument panel. No light variant —
the dot field and the hairline rules only read on black, and a naive
inversion would wash both out. Every colour is painted explicitly so the page
never borrows a host background. */
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
:root{
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
--font-zen-pixel-square:'Zen Pixel Square',monospace;
--mono:var(--font-zen-mono);
--sans:var(--font-zen-sans);
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
--r:999px; --r-soft:14px;
}
*{box-sizing:border-box}
html{-webkit-text-size-adjust:100%}
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
/* The dot field. A halftone made of one repeating radial-gradient, faded out
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
/* No overflow clip here: the dot field is inset to the box already, and a clip
would cut off the copy-prompt menu. */
.hero{position:relative;border-bottom:1px solid var(--line)}
.hero::before{content:"";position:absolute;inset:0;
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
background-size:7px 7px;
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
pointer-events:none}
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
nav{border-bottom:1px solid var(--line)}
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
justify-content:space-between;align-items:center;gap:1rem}
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--ink);text-decoration:none;
display:inline-flex;align-items:center;gap:.6rem}
.brand i{font-style:normal;color:var(--faint)}
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--soft);text-decoration:none}
nav a.up:hover{color:var(--ink)}
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
h1 em{font-style:normal;color:var(--faint)}
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
line-height:1.2;font-weight:400}
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
.btn.solid:hover{background:#d8d8d4}
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
/* Copy-prompt selector. Each row copies the prompt for its own target. */
.copy{position:relative;display:inline-flex}
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
padding:.4rem;display:flex;flex-direction:column;
box-shadow:0 12px 32px rgba(0,0,0,.75)}
.menu[hidden]{display:none}
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
white-space:nowrap}
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
.mi:hover .mark{color:var(--ink)}
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
letter-spacing:.1em;text-transform:uppercase}
/* Works-with bar: one scrolling row, name and mark per agent. */
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
display:flex;align-items:center}
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
-webkit-overflow-scrolling:touch;
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
.bar::-webkit-scrollbar{display:none}
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
text-decoration:none;background:var(--ground)}
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
.agent .mark{width:.95rem;height:.95rem}
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
p{margin:0 0 1rem;max-width:70ch}
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
li{margin:.22rem 0}
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
text-decoration-color:var(--line-hi)}
a:hover{text-decoration-color:var(--ink)}
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
display:block;overflow-x:auto}
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
.curl{display:block;background:var(--panel);border:1px solid var(--line);
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
white-space:pre;line-height:1.9}
.curl b{color:var(--ink);font-weight:400}
.curl i{font-style:normal;color:var(--faint)}
/* index */
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
#q:focus{outline:none;border-color:var(--soft)}
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
text-transform:uppercase;margin:0 0 2rem}
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
padding-bottom:.45rem}
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
border-radius:var(--r-soft);text-decoration:none}
.row:hover{background:#0a0a0a}
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
color:var(--faint);font-size:.85rem}
footer a{color:var(--soft)}
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
margin:0 0 2rem;font-size:.85rem}
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
border-bottom:1px solid var(--line);padding-bottom:.4rem}
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
.fmap a:hover{text-decoration:underline}
.fmap div{color:var(--faint);line-height:1.5}
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
@media (max-width:640px){
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
.btns{gap:.5rem}
.btn{padding:.75rem 1.15rem;font-size:.68rem}
.copy,.copy .btn{width:100%;justify-content:center}
.menu{left:0;right:0;min-width:0}
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
.strip b{border-right:0;padding-right:0}
.bar{width:100%}
}
</style>
<link rel="icon" href="/favicon.svg">
<link rel="canonical" href="https://hanzoskills.com/dependent-types">
<link rel="alternate" type="text/markdown" href="/dependent-types.md">
<script type="module" src="/webmcp.js"></script>
</head>
<!-- Reading this with a machine? Every page here is also plain markdown.
This one: https://hanzoskills.com/dependent-types.md
Index: https://hanzoskills.com/llms.txt
Corpus: https://hanzoskills.com/all.md
Append .md to any path for the markdown twin. -->
<body>
<nav><div class="in">
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
<a class="up" href="/">All skills</a>
</div></nav>
<div class="wrap">
<h1>dependent-types</h1><p class="lede">Dependent types including Π-types, Σ-types, indexed families, and proof assistants</p><h1>Dependent Types</h1>
<p><strong>Scope</strong>: Π-types, Σ-types, indexed families, equality types, proof assistants (Lean, Coq, Agda) <strong>Lines</strong>: ~400 <strong>Last Updated</strong>: 2025-10-25</p>
<h2>When to Use This Skill</h2>
<p>Activate this skill when:</p>
<ul><li>Implementing proof assistants or verified compilers</li><li>Working with Lean 4, Coq, Agda, or Idris</li><li>Encoding invariants in types (length-indexed vectors)</li><li>Proving program correctness via dependent types</li><li>Understanding Curry-Howard correspondence at type level</li><li>Designing expressive type systems for DSLs</li></ul>
<h2>Core Concepts</h2>
<h3>Dependent Function Types (Π-types)</h3>
<p><strong>Π-type</strong>: Π(x:A). B(x) - function type where result type depends on argument value</p>
<p><strong>Examples</strong>:</p>
<ul><li>Vector of length n: <code>Vec A n</code></li><li><code>replicate : Π(n:Nat). A → Vec A n</code></li></ul>
<pre><code class="lang-python">from dataclasses import dataclass
from typing import Union, Callable
# Dependent types representation (simplified)
@dataclass
class Pi:
&quot;&quot;&quot;Π(x:A). B(x) - dependent function type&quot;&quot;&quot;
param_name: str
param_type: &#x27;Type&#x27;
result_type: Callable # Function from value to type
def __repr__(self):
return f&quot;Π({self.param_name}:{self.param_type}). ...&quot;
@dataclass
class Nat:
&quot;&quot;&quot;Natural number type&quot;&quot;&quot;
def __repr__(self):
return &quot;Nat&quot;
@dataclass
class Vec:
&quot;&quot;&quot;Length-indexed vector: Vec A n&quot;&quot;&quot;
elem_type: &#x27;Type&#x27;
length: int
def __repr__(self):
return f&quot;Vec {self.elem_type} {self.length}&quot;
Type = Union[Nat, Vec, Pi]
# Example: replicate : Π(n:Nat). A → Vec A n
def replicate_type(A):
&quot;&quot;&quot;Type of replicate function&quot;&quot;&quot;
return Pi(&#x27;n&#x27;, Nat(), lambda n: FunctionType(A, Vec(A, n)))
# In Lean 4:
&quot;&quot;&quot;
def replicate {α : Type} (n : Nat) (x : α) : Vector α n :=
match n with
| 0 =&gt; []
| n+1 =&gt; x :: replicate n x
&quot;&quot;&quot;
print(&quot;replicate : Π(n:Nat). A → Vec A n&quot;)</code></pre>
<h3>Dependent Pair Types (Σ-types)</h3>
<p><strong>Σ-type</strong>: Σ(x:A). B(x) - pair where second component&#x27;s type depends on first</p>
<p><strong>Examples</strong>:</p>
<ul><li>Existential types: ∃(n:Nat). Vec A n (vector with unknown length)</li><li>Refinement types: {x:Int | x &gt; 0} ≅ Σ(x:Int). (x &gt; 0)</li></ul>
<pre><code class="lang-python">@dataclass
class Sigma:
&quot;&quot;&quot;Σ(x:A). B(x) - dependent pair type&quot;&quot;&quot;
param_name: str
param_type: Type
result_type: Callable # Function from value to type
def __repr__(self):
return f&quot;Σ({self.param_name}:{self.param_type}). ...&quot;
@dataclass
class Pair:
&quot;&quot;&quot;Dependent pair value: (a, b) : Σ(x:A). B(x)&quot;&quot;&quot;
fst: any
snd: any
# Example: existential vector (vector with hidden length)
def existential_vector(A):
&quot;&quot;&quot;Σ(n:Nat). Vec A n&quot;&quot;&quot;
return Sigma(&#x27;n&#x27;, Nat(), lambda n: Vec(A, n))
# In Lean 4:
&quot;&quot;&quot;
structure ExVec (α : Type) where
length : Nat
data : Vector α length
-- Example
def myVec : ExVec Int := ⟨3, [1, 2, 3]⟩
&quot;&quot;&quot;
print(&quot;ExVec A ≅ Σ(n:Nat). Vec A n&quot;)</code></pre>
<h3>Indexed Families</h3>
<p><strong>Indexed family</strong>: Family of types indexed by values</p>
<pre><code class="lang-python"># Length-indexed vectors in Python (conceptual)
class Vector:
&quot;&quot;&quot;Vec A n - vector of length n&quot;&quot;&quot;
def __init__(self, elem_type, length, elements):
self.elem_type = elem_type
self.length = length
self.elements = elements
assert len(elements) == length
def __repr__(self):
return f&quot;Vec {self.elem_type} {self.length} {self.elements}&quot;
# Operations preserving length
def vmap(f, vec):
&quot;&quot;&quot;map : (A → B) → Vec A n → Vec B n&quot;&quot;&quot;
return Vector(
elem_type=&#x27;B&#x27;,
length=vec.length,
elements=[f(x) for x in vec.elements]
)
def vappend(vec1, vec2):
&quot;&quot;&quot;append : Vec A m → Vec A n → Vec A (m+n)&quot;&quot;&quot;
return Vector(
elem_type=vec1.elem_type,
length=vec1.length + vec2.length,
elements=vec1.elements + vec2.elements
)
# Example
v1 = Vector(&#x27;Int&#x27;, 3, [1, 2, 3])
v2 = Vector(&#x27;Int&#x27;, 2, [4, 5])
v3 = vappend(v1, v2)
print(f&quot;{v1} ++ {v2} = {v3}&quot;) # Vec Int 5 [1,2,3,4,5]
# In Lean 4:
&quot;&quot;&quot;
def Vector.append {α : Type} {m n : Nat} : Vector α m → Vector α n → Vector α (m + n)
| [], ys =&gt; ys
| x :: xs, ys =&gt; x :: xs.append ys
&quot;&quot;&quot;</code></pre>
<h3>Equality Types</h3>
<p><strong>Identity type</strong>: a =_A b (proof that a equals b in type A)</p>
<pre><code class="lang-python">@dataclass
class Eq:
&quot;&quot;&quot;Equality type: a =_A b&quot;&quot;&quot;
type_: Type
lhs: any
rhs: any
def __repr__(self):
return f&quot;{self.lhs} =_{self.type_} {self.rhs}&quot;
@dataclass
class Refl:
&quot;&quot;&quot;Reflexivity: refl : a =_A a&quot;&quot;&quot;
value: any
def __repr__(self):
return f&quot;refl {self.value}&quot;
# Leibniz&#x27;s law: if a = b, then P(a) → P(b)
def leibniz_subst(eq_proof, P, pa):
&quot;&quot;&quot;
subst : a =_A b → P(a) → P(b)
Transport along equality
&quot;&quot;&quot;
match eq_proof:
case Refl(a):
# a = a, so P(a) = P(a)
return pa
# In practice, need full pattern matching on equality proofs
# In Lean 4:
&quot;&quot;&quot;
theorem leibniz_subst {α : Type} {a b : α} (h : a = b) (P : α → Prop) : P a → P b := by
rw [h]
&quot;&quot;&quot;
print(&quot;Equality allows transporting proofs along equalities&quot;)</code></pre>
<h3>Universe Levels</h3>
<p><strong>Type hierarchy</strong>: Type₀ : Type₁ : Type₂ : ...</p>
<pre><code class="lang-python">@dataclass
class Universe:
&quot;&quot;&quot;Type_i - universe at level i&quot;&quot;&quot;
level: int
def __repr__(self):
return f&quot;Type_{self.level}&quot;
# Examples:
# Nat : Type₀
# Type₀ : Type₁
# Vec : Type₀ → Nat → Type₀
# List : Type₀ → Type₀
# In Lean 4:
&quot;&quot;&quot;
#check Nat -- Nat : Type
#check Type -- Type : Type 1
#check Type 1 -- Type 1 : Type 2
universe u v
def MyVec (α : Type u) (n : Nat) : Type u := ...
&quot;&quot;&quot;
print(&quot;Universes prevent Russell&#x27;s paradox: Type : Type is inconsistent&quot;)</code></pre>
<h3>Dependent Pattern Matching</h3>
<p><strong>Match with dependent types</strong>: Result type depends on matched value</p>
<pre><code class="lang-python"># Example: head function for non-empty vectors
def vec_head(vec):
&quot;&quot;&quot;
head : Π{n:Nat}. Vec A (n+1) → A
Only defined for non-empty vectors (n ≥ 1)
&quot;&quot;&quot;
if vec.length == 0:
raise ValueError(&quot;Cannot take head of empty vector&quot;)
return vec.elements[0]
# In Lean 4:
&quot;&quot;&quot;
def Vector.head {α : Type} {n : Nat} : Vector α (n+1) → α
| x :: _ =&gt; x
-- Pattern matching refines type:
-- Matching on `n+1` in index tells Lean vector is non-empty
&quot;&quot;&quot;
# Example: safe division (result type depends on divisor ≠ 0)
def safe_div(a, b):
&quot;&quot;&quot;
div : (a : Int) → (b : Int) → {b ≠ 0} → Int
Requires proof that b ≠ 0
&quot;&quot;&quot;
if b == 0:
raise ValueError(&quot;Division by zero&quot;)
return a // b
# In Lean 4:
&quot;&quot;&quot;
def safeDiv (a b : Int) (h : b ≠ 0) : Int := a / b
-- Usage requires proof:
example : Int := safeDiv 10 2 (by norm_num) -- OK
example : Int := safeDiv 10 0 ?_ -- Error: need proof 0 ≠ 0
&quot;&quot;&quot;
print(&quot;Dependent pattern matching enables type-safe operations&quot;)</code></pre>
<hr>
<h2>Patterns</h2>
<h3>Pattern 1: Vectors with Length</h3>
<pre><code class="lang-lean">-- Lean 4
inductive Vector (α : Type u) : Nat → Type u where
| nil : Vector α 0
| cons (x : α) {n : Nat} (xs : Vector α n) : Vector α (n+1)
def Vector.append {α : Type} {m n : Nat} : Vector α m → Vector α n → Vector α (m+n)
| nil, ys =&gt; ys
| cons x xs, ys =&gt; cons x (xs.append ys)
-- Type ensures length correctness at compile time</code></pre>
<h3>Pattern 2: Dependent Records</h3>
<pre><code class="lang-lean">-- Lean 4
structure Matrix (α : Type) (rows cols : Nat) where
data : Vector (Vector α cols) rows
def Matrix.multiply {α : Type} [Mul α] [Add α] [Zero α]
{m n p : Nat} : Matrix α m n → Matrix α n p → Matrix α m p := ...
-- Matrix multiplication type: (m×n) · (n×p) = (m×p)
-- Dimension checking at type level!</code></pre>
<h3>Pattern 3: Proofs as Indices</h3>
<pre><code class="lang-lean">-- Lean 4
def lookup {α : Type} (vec : Vector α n) (i : Nat) (h : i &lt; n) : α := ...
-- h : i &lt; n is a proof that i is valid index
-- Eliminates runtime bounds checks!
example : Nat := lookup ⟨3, [1, 2, 3]⟩ 1 (by norm_num) -- OK: 1 &lt; 3
example : Nat := lookup ⟨3, [1, 2, 3]⟩ 5 (by norm_num) -- Error: can&#x27;t prove 5 &lt; 3</code></pre>
<hr>
<h2>Quick Reference</h2>
<h3>Dependent Types Hierarchy</h3>
<pre><code>Π-type (dependent function):
Simple function: A → B
Dependent function: Π(x:A). B(x)
Polymorphic: ∀(A:Type). ...
Σ-type (dependent pair):
Simple pair: A × B
Dependent pair: Σ(x:A). B(x)
Existential: ∃(x:A). P(x)</code></pre>
<h3>Lean 4 Syntax</h3>
<pre><code class="lang-lean">-- Π-type
def foo (n : Nat) : Vector Bool n := ...
-- Equivalent to: foo : Π(n:Nat). Vector Bool n
-- Σ-type
structure Sigma (α : Type u) (β : α → Type v) where
fst : α
snd : β fst
-- Equality type
example (a b : Nat) (h : a = b) : b = a := h.symm</code></pre>
<h3>Common Indexed Families</h3>
<p>| Family | Index | Example | |--------|-------|---------| | Vector | Nat (length) | Vector α n | | Matrix | Nat × Nat (dimensions) | Matrix α m n | | Fin | Nat (bound) | Fin n (numbers &lt; n) | | Eq | Values | a = b |</p>
<hr>
<h2>Anti-Patterns</h2>
<p>❌ <strong>Overusing dependent types</strong>: Not every function needs dependent types ✅ Use when invariants are critical (safety) or improve ergonomics</p>
<p>❌ <strong>Confusing Π and ∀</strong>: Π is dependent function, ∀ is logical quantifier (though related) ✅ In Lean: <code>∀(x:A). P(x)</code> is <code>Π(x:A). P(x)</code> where P(x) : Prop</p>
<p>❌ <strong>Ignoring universe levels</strong>: Can cause inconsistency ✅ Use universe polymorphism: <code>def foo {α : Type u} ...</code></p>
<p>❌ <strong>Fighting the type checker</strong>: Complex dependent types can be hard to work with ✅ Use tactics and automation (Lean&#x27;s <code>simp</code>, <code>omega</code>, etc.)</p>
<hr>
<h2>Related Skills</h2>
<ul><li><code>lambda-calculus.md</code> - Foundation for dependent λ-calculus</li><li><code>type-systems.md</code> - Simpler type systems (System F, HM)</li><li><code>curry-howard.md</code> - Proofs as programs via dependent types</li><li><code>formal/lean-proof-basics.md</code> - Practical dependent type proving in Lean</li><li><code>program-verification.md</code> - Using dependent types for verification</li></ul>
<hr>
<p><strong>Last Updated</strong>: 2025-10-25 <strong>Format Version</strong>: 1.0 (Atomic)</p>
<footer>
<div class="fmap">
<div><b>Build</b>
<a href="https://hanzo.app">hanzo.app</a> app builder
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
<div><b>Run</b>
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
<div><b>Account</b>
<a href="https://hanzo.id">hanzo.id</a> sign in
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
<div><b>Company</b>
<a href="https://hanzo.ai">hanzo.ai</a> canonical
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
</div>
<div class="fend"><a href="/dependent-types.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
</footer>
</div></body></html>