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
  • Fin stands for "Finite set" (or a finite range of numbers).
  • It takes a parameter of type Nat (a unary natural number like Z, S Z, S (S Z), etc.) and returns a Type.
  • This means Fin is a dependently typed structure: the type itself changes depending on the natural number $n$ you pass into it. For example, Fin 3 is 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)
  • FZ represents 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)
  • FS represents the successor of an existing Fin index (similar to how S represents the successor in Nat).
  • If you have a valid index k of type Fin n, then FS k gives you a valid index of type Fin (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:

  1. FZ (representing $0$)
  2. FS FZ (representing $1$)
  3. 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 Z is 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 for Nil, and the compiler won't complain about missing cases!