mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
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.
528 lines
24 KiB
HTML
528 lines
24 KiB
HTML
<!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:
|
||
"""Π(x:A). B(x) - dependent function type"""
|
||
param_name: str
|
||
param_type: 'Type'
|
||
result_type: Callable # Function from value to type
|
||
|
||
def __repr__(self):
|
||
return f"Π({self.param_name}:{self.param_type}). ..."
|
||
|
||
@dataclass
|
||
class Nat:
|
||
"""Natural number type"""
|
||
def __repr__(self):
|
||
return "Nat"
|
||
|
||
@dataclass
|
||
class Vec:
|
||
"""Length-indexed vector: Vec A n"""
|
||
elem_type: 'Type'
|
||
length: int
|
||
|
||
def __repr__(self):
|
||
return f"Vec {self.elem_type} {self.length}"
|
||
|
||
Type = Union[Nat, Vec, Pi]
|
||
|
||
# Example: replicate : Π(n:Nat). A → Vec A n
|
||
def replicate_type(A):
|
||
"""Type of replicate function"""
|
||
return Pi('n', Nat(), lambda n: FunctionType(A, Vec(A, n)))
|
||
|
||
# In Lean 4:
|
||
"""
|
||
def replicate {α : Type} (n : Nat) (x : α) : Vector α n :=
|
||
match n with
|
||
| 0 => []
|
||
| n+1 => x :: replicate n x
|
||
"""
|
||
|
||
print("replicate : Π(n:Nat). A → Vec A n")</code></pre>
|
||
<h3>Dependent Pair Types (Σ-types)</h3>
|
||
<p><strong>Σ-type</strong>: Σ(x:A). B(x) - pair where second component'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 > 0} ≅ Σ(x:Int). (x > 0)</li></ul>
|
||
<pre><code class="lang-python">@dataclass
|
||
class Sigma:
|
||
"""Σ(x:A). B(x) - dependent pair type"""
|
||
param_name: str
|
||
param_type: Type
|
||
result_type: Callable # Function from value to type
|
||
|
||
def __repr__(self):
|
||
return f"Σ({self.param_name}:{self.param_type}). ..."
|
||
|
||
@dataclass
|
||
class Pair:
|
||
"""Dependent pair value: (a, b) : Σ(x:A). B(x)"""
|
||
fst: any
|
||
snd: any
|
||
|
||
# Example: existential vector (vector with hidden length)
|
||
def existential_vector(A):
|
||
"""Σ(n:Nat). Vec A n"""
|
||
return Sigma('n', Nat(), lambda n: Vec(A, n))
|
||
|
||
# In Lean 4:
|
||
"""
|
||
structure ExVec (α : Type) where
|
||
length : Nat
|
||
data : Vector α length
|
||
|
||
-- Example
|
||
def myVec : ExVec Int := ⟨3, [1, 2, 3]⟩
|
||
"""
|
||
|
||
print("ExVec A ≅ Σ(n:Nat). Vec A n")</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:
|
||
"""Vec A n - vector of length n"""
|
||
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"Vec {self.elem_type} {self.length} {self.elements}"
|
||
|
||
# Operations preserving length
|
||
def vmap(f, vec):
|
||
"""map : (A → B) → Vec A n → Vec B n"""
|
||
return Vector(
|
||
elem_type='B',
|
||
length=vec.length,
|
||
elements=[f(x) for x in vec.elements]
|
||
)
|
||
|
||
def vappend(vec1, vec2):
|
||
"""append : Vec A m → Vec A n → Vec A (m+n)"""
|
||
return Vector(
|
||
elem_type=vec1.elem_type,
|
||
length=vec1.length + vec2.length,
|
||
elements=vec1.elements + vec2.elements
|
||
)
|
||
|
||
# Example
|
||
v1 = Vector('Int', 3, [1, 2, 3])
|
||
v2 = Vector('Int', 2, [4, 5])
|
||
v3 = vappend(v1, v2)
|
||
print(f"{v1} ++ {v2} = {v3}") # Vec Int 5 [1,2,3,4,5]
|
||
|
||
# In Lean 4:
|
||
"""
|
||
def Vector.append {α : Type} {m n : Nat} : Vector α m → Vector α n → Vector α (m + n)
|
||
| [], ys => ys
|
||
| x :: xs, ys => x :: xs.append ys
|
||
"""</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:
|
||
"""Equality type: a =_A b"""
|
||
type_: Type
|
||
lhs: any
|
||
rhs: any
|
||
|
||
def __repr__(self):
|
||
return f"{self.lhs} =_{self.type_} {self.rhs}"
|
||
|
||
@dataclass
|
||
class Refl:
|
||
"""Reflexivity: refl : a =_A a"""
|
||
value: any
|
||
|
||
def __repr__(self):
|
||
return f"refl {self.value}"
|
||
|
||
# Leibniz's law: if a = b, then P(a) → P(b)
|
||
def leibniz_subst(eq_proof, P, pa):
|
||
"""
|
||
subst : a =_A b → P(a) → P(b)
|
||
Transport along equality
|
||
"""
|
||
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:
|
||
"""
|
||
theorem leibniz_subst {α : Type} {a b : α} (h : a = b) (P : α → Prop) : P a → P b := by
|
||
rw [h]
|
||
"""
|
||
|
||
print("Equality allows transporting proofs along equalities")</code></pre>
|
||
<h3>Universe Levels</h3>
|
||
<p><strong>Type hierarchy</strong>: Type₀ : Type₁ : Type₂ : ...</p>
|
||
<pre><code class="lang-python">@dataclass
|
||
class Universe:
|
||
"""Type_i - universe at level i"""
|
||
level: int
|
||
|
||
def __repr__(self):
|
||
return f"Type_{self.level}"
|
||
|
||
# Examples:
|
||
# Nat : Type₀
|
||
# Type₀ : Type₁
|
||
# Vec : Type₀ → Nat → Type₀
|
||
# List : Type₀ → Type₀
|
||
|
||
# In Lean 4:
|
||
"""
|
||
#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 := ...
|
||
"""
|
||
|
||
print("Universes prevent Russell's paradox: Type : Type is inconsistent")</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):
|
||
"""
|
||
head : Π{n:Nat}. Vec A (n+1) → A
|
||
Only defined for non-empty vectors (n ≥ 1)
|
||
"""
|
||
if vec.length == 0:
|
||
raise ValueError("Cannot take head of empty vector")
|
||
return vec.elements[0]
|
||
|
||
# In Lean 4:
|
||
"""
|
||
def Vector.head {α : Type} {n : Nat} : Vector α (n+1) → α
|
||
| x :: _ => x
|
||
|
||
-- Pattern matching refines type:
|
||
-- Matching on `n+1` in index tells Lean vector is non-empty
|
||
"""
|
||
|
||
# Example: safe division (result type depends on divisor ≠ 0)
|
||
def safe_div(a, b):
|
||
"""
|
||
div : (a : Int) → (b : Int) → {b ≠ 0} → Int
|
||
Requires proof that b ≠ 0
|
||
"""
|
||
if b == 0:
|
||
raise ValueError("Division by zero")
|
||
return a // b
|
||
|
||
# In Lean 4:
|
||
"""
|
||
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
|
||
"""
|
||
|
||
print("Dependent pattern matching enables type-safe operations")</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 => ys
|
||
| cons x xs, ys => 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 < n) : α := ...
|
||
|
||
-- h : i < 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 < 3
|
||
example : Nat := lookup ⟨3, [1, 2, 3]⟩ 5 (by norm_num) -- Error: can't prove 5 < 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 < 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'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> |