data Fin : Nat -> Type where
FZ : Fin (S k)
FS : Fin k -> Fin (S k)
This code snippet defines Finite Sets (Fin) in Idris 2, which are used to represent bounded natural numbers (from $0$ to $n-1$) at the type level.
Here is a step-by-step breakdown of how it works and why it is so powerful:
1. The Type Signature¶
data Fin : Nat -> Type where
Finstands for "Finite set" (or a finite range of numbers).- It takes a parameter of type
Nat(a unary natural number likeZ,S Z,S (S Z), etc.) and returns aType. - This means
Finis a dependently typed structure: the type itself changes depending on the natural number $n$ you pass into it. For example,Fin 3is the type of all valid indices strictly less than $3$ (i.e., $0, 1,$ and $2$).
2. The Constructors¶
Every Fin n is constructed using one of two constructors:
A. FZ (Finite Zero)¶
FZ : Fin (S k)
FZrepresents the number zero ($0$).- Constraint: It can only be used for types where the upper bound is a successor, i.e.,
S k(meaning $n \ge 1$). - Why? You cannot have a valid index $0$ in an empty collection of size $0$ (
Fin Z). Zero is only valid if the size is at least $1$.
B. FS (Finite Successor)¶
FS : Fin k -> Fin (S k)
FSrepresents the successor of an existingFinindex (similar to howSrepresents the successor inNat).- If you have a valid index
kof typeFin n, thenFS kgives you a valid index of typeFin (S n)(essentially shifting the index up by $1$).
3. Step-by-Step Example: What does Fin 3 look like?¶
Because Fin 3 (where $3$ is S (S (S Z))) can only be built using combinations of FZ and FS, the only valid values of type Fin 3 are:
FZ(representing $0$)FS FZ(representing $1$)FS (FS FZ)(representing $2$)
Notice that there is no way to construct a Fin 3 that represents $3$ or higher. The type system makes it structurally impossible.
4. Why is this useful? (Safe Indexing)¶
As noted in the lecture notes, Fin is primarily used for safe vector indexing (index : Fin n -> Vect n a -> a).
When you write a lookup function using Fin:
- No out-of-bounds errors: You literally cannot pass an index that is too large because the compiler forces the index to be bound by the vector's length
n. - Exhaustive pattern matching: Because
Fin Zis uninhabited (you can't even construct a zero-sized finite set), the compiler knows that looking up an element in an empty vector (Nil) is an impossible case. You don't even have to write a pattern match forNil, and the compiler won't complain about missing cases!