🎬 Traits & Generics Shared behaviour, static vs dynamic dispatch, zero-cost polymorphism.

📝 Text version (for readers / accessibility)

• Traits define shared behaviour — like interfaces but with default implementations

• Generics with trait bounds: fn process(item: T) — monomorphized at compile time

• Static dispatch (impl Trait) = zero cost; dynamic dispatch (dyn Trait) = runtime flexibility via vtable

• Blanket implementations apply traits to all types matching a bound

• Associated types and supertraits enable complex type relationships

780: Generic Structs Parameterised by const

Difficulty: 3 Level: Intermediate `struct Matrix<const R: usize, const C: usize>` — encode dimensions in the type so mismatched multiplication is a compile error.

The Problem This Solves

Matrix multiplication has a dimension constraint: you can multiply an `R×N` matrix by an `N×C` matrix, but not an `R×N` by an `M×C` unless `N == M`. Without const generics, you'd check this at runtime and panic or return `Err`. With const generics, mismatched dimensions are a type error — the code won't compile. This is the core promise of const generics: properties that are normally runtime-checked (array lengths, buffer sizes, state machine alphabet sizes) become part of the type. The compiler enforces them. No runtime cost, no runtime failure modes. `Matrix<2, 3>` and `Matrix<3, 2>` are different types; multiplying them in the wrong order is caught during compilation. Const generic structs appear in embedded Rust (fixed-size ring buffers, fixed-dimension matrices for robotics), crypto (fixed-length hash digests), and any domain where "this collection has exactly N elements" is a semantic invariant worth encoding in the type system.

The Intuition

`const N: usize` in a struct definition makes `N` part of the type, not an instance variable. `Matrix<2, 3>` and `Matrix<2, 4>` are as different as `u32` and `u64`. Methods can be restricted to specific const parameter values — `identity()` only makes sense when `R == N`, so it's implemented only for `Matrix<N, N>`. Matrix multiplication's type signature `fn mat_mul<R, N, C>(a: &Matrix<R, N>, b: &Matrix<N, C>) -> Matrix<R, C>` expresses the dimension constraint directly.

How It Works in Rust

// R rows, C columns — encoded in the type
#[derive(Debug, Clone, PartialEq)]
pub struct Matrix<const R: usize, const C: usize> {
 data: [[f64; C]; R],   // stack-allocated fixed-size array
}

impl<const R: usize, const C: usize> Matrix<R, C> {
 pub fn zero() -> Self { Self { data: [[0.0; C]; R] } }
 pub fn rows() -> usize { R }   // compile-time constant — no runtime cost
 pub fn cols() -> usize { C }
}

// Only square matrices have an identity
impl<const N: usize> Matrix<N, N> {
 pub fn identity() -> Self {
     let mut m = Self::zero();
     for i in 0..N { m.data[i][i] = 1.0; }
     m
 }
}

// Dimension constraint in the type signature:
// Matrix<R,N> × Matrix<N,C> → Matrix<R,C>
// If N doesn't match, the call won't compile
pub fn mat_mul<const R: usize, const N: usize, const C: usize>(
 a: &Matrix<R, N>,
 b: &Matrix<N, C>,
) -> Matrix<R, C> {
 let mut out = Matrix::<R, C>::zero();
 for r in 0..R {
     for c in 0..C {
         let mut sum = 0.0;
         for k in 0..N { sum += a.data[r][k] * b.data[k][c]; }
         out.data[r][c] = sum;
     }
 }
 out
}

// Usage: dimensions checked at compile time
let a: Matrix<2, 3> = /* ... */;
let b: Matrix<3, 4> = /* ... */;
let c: Matrix<2, 4> = mat_mul(&a, &b);   // ok: inner dims both 3
// let bad = mat_mul(&a, &a);            // compile error: Matrix<2,3> × Matrix<2,3> — 3 ≠ 2

`[[f64; C]; R]` is a stack-allocated fixed-size 2D array. For large matrices, you'd use heap storage (`Vec<f64>` with manual indexing), but const generics still encode the logical dimensions in the type.

What This Unlocks

Dimension-safe linear algebra — matrix types where `mat_mul(a: &Matrix<R,N>, b: &Matrix<N,C>)` won't compile for mismatched inner dimensions; the nalgebra crate uses exactly this pattern.
Impl specialization via const constraints — `impl<const N: usize> Matrix<N, N>` restricts methods to square matrices only; the same technique applies to power-of-two constraints, zero-length guards, etc.
Zero-overhead fixed-size structures — `[[T; C]; R]` is allocated on the stack with no heap overhead, and the size is known at compile time for efficient copy/comparison.

Key Differences

Concept	OCaml	Rust
Type-level naturals	GADTs with `zero`/`succ` types	`const N: usize` — direct integer in type param
Fixed-size arrays	Bigarray with dimensions	`[[f64; C]; R]` — stack-allocated, bounds-checked
Method on subset	No direct equivalent	`impl<const N: usize> Matrix<N, N>` restricts to square
Dimension mismatch	Runtime error	Compile error — wrong `N` is a type mismatch

//! # Const Generic Struct
//!
//! Structures parameterized by compile-time constants.

/// Fixed-capacity ring buffer
#[derive(Debug)]
pub struct RingBuffer<T, const CAP: usize> {
    data: [Option<T>; CAP],
    head: usize,
    tail: usize,
    len: usize,
}

impl<T: Copy, const CAP: usize> RingBuffer<T, CAP> {
    pub fn new() -> Self {
        RingBuffer {
            data: [None; CAP],
            head: 0,
            tail: 0,
            len: 0,
        }
    }

    pub const fn capacity(&self) -> usize {
        CAP
    }

    pub const fn len(&self) -> usize {
        self.len
    }

    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub const fn is_full(&self) -> bool {
        self.len == CAP
    }

    pub fn push(&mut self, item: T) -> Result<(), T> {
        if self.is_full() {
            return Err(item);
        }
        self.data[self.tail] = Some(item);
        self.tail = (self.tail + 1) % CAP;
        self.len += 1;
        Ok(())
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }
        let item = self.data[self.head].take();
        self.head = (self.head + 1) % CAP;
        self.len -= 1;
        item
    }

    pub fn peek(&self) -> Option<&T> {
        if self.is_empty() {
            None
        } else {
            self.data[self.head].as_ref()
        }
    }
}

impl<T: Copy, const CAP: usize> Default for RingBuffer<T, CAP> {
    fn default() -> Self {
        Self::new()
    }
}

/// Bit set with compile-time size (stored as array of u64 words)
/// The number of u64 words is passed as a const generic WORDS parameter.
#[derive(Debug, Clone, Copy)]
pub struct BitSet<const BITS: usize, const WORDS: usize> {
    data: [u64; WORDS],
}

impl<const BITS: usize, const WORDS: usize> BitSet<BITS, WORDS> {
    pub fn new() -> Self {
        BitSet { data: [0; WORDS] }
    }

    pub const fn bits(&self) -> usize {
        BITS
    }

    pub fn set(&mut self, idx: usize) {
        if idx < BITS {
            self.data[idx / 64] |= 1 << (idx % 64);
        }
    }

    pub fn clear(&mut self, idx: usize) {
        if idx < BITS {
            self.data[idx / 64] &= !(1 << (idx % 64));
        }
    }

    pub fn get(&self, idx: usize) -> bool {
        if idx < BITS {
            (self.data[idx / 64] >> (idx % 64)) & 1 != 0
        } else {
            false
        }
    }

    pub fn count_ones(&self) -> usize {
        self.data.iter().map(|&x| x.count_ones() as usize).sum()
    }
}

impl<const BITS: usize, const WORDS: usize> Default for BitSet<BITS, WORDS> {
    fn default() -> Self {
        Self::new()
    }
}

/// Fixed-size string
#[derive(Debug, Clone, Copy)]
pub struct FixedString<const N: usize> {
    data: [u8; N],
    len: usize,
}

impl<const N: usize> FixedString<N> {
    pub const fn new() -> Self {
        FixedString { data: [0; N], len: 0 }
    }

    pub const fn capacity(&self) -> usize {
        N
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn as_str(&self) -> &str {
        std::str::from_utf8(&self.data[..self.len]).unwrap_or("")
    }

    pub fn push_str(&mut self, s: &str) -> bool {
        let bytes = s.as_bytes();
        if self.len + bytes.len() <= N {
            self.data[self.len..self.len + bytes.len()].copy_from_slice(bytes);
            self.len += bytes.len();
            true
        } else {
            false
        }
    }
}

impl<const N: usize> Default for FixedString<N> {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_ring_buffer() {
        let mut rb: RingBuffer<i32, 4> = RingBuffer::new();
        assert_eq!(rb.capacity(), 4);
        
        rb.push(1).unwrap();
        rb.push(2).unwrap();
        assert_eq!(rb.pop(), Some(1));
        assert_eq!(rb.pop(), Some(2));
    }

    #[test]
    fn test_ring_buffer_wrap() {
        let mut rb: RingBuffer<i32, 3> = RingBuffer::new();
        rb.push(1).unwrap();
        rb.push(2).unwrap();
        rb.push(3).unwrap();
        assert!(rb.push(4).is_err()); // Full
        
        assert_eq!(rb.pop(), Some(1));
        rb.push(4).unwrap(); // Now there's room
        assert_eq!(rb.pop(), Some(2));
    }

    #[test]
    fn test_bitset() {
        // BitSet<100, 2> means 100 bits stored in 2 u64 words (128 bits capacity)
        let mut bs: BitSet<100, 2> = BitSet::new();
        assert_eq!(bs.bits(), 100);
        
        bs.set(0);
        bs.set(50);
        bs.set(99);
        
        assert!(bs.get(0));
        assert!(bs.get(50));
        assert!(bs.get(99));
        assert!(!bs.get(1));
        assert_eq!(bs.count_ones(), 3);
    }

    #[test]
    fn test_fixed_string() {
        let mut s: FixedString<16> = FixedString::new();
        assert!(s.push_str("hello"));
        assert_eq!(s.as_str(), "hello");
        assert!(s.push_str(" world"));
        assert_eq!(s.as_str(), "hello world");
    }
}

(* Generic structs parameterised by const in OCaml — using functors *)

module type DIMS = sig val rows : int val cols : int end

module Matrix (D : DIMS) = struct
  type t = { data: float array array }

  let create () =
    { data = Array.init D.rows (fun _ -> Array.make D.cols 0.0) }

  let get m r c = m.data.(r).(c)
  let set m r c v = m.data.(r).(c) <- v

  let rows = D.rows
  let cols = D.cols

  let identity () =
    assert (D.rows = D.cols);
    let m = create () in
    for i = 0 to D.rows - 1 do set m i i 1.0 done;
    m

  let print m =
    for r = 0 to D.rows - 1 do
      for c = 0 to D.cols - 1 do
        Printf.printf " %6.2f" (get m r c)
      done;
      print_newline ()
    done
end

(* Multiply M1(R×N) × M2(N×C) → M3(R×C) *)
module MatMul (R : sig val n : int end)
              (N : sig val n : int end)
              (C : sig val n : int end) = struct
  module MA = Matrix(struct let rows = R.n let cols = N.n end)
  module MB = Matrix(struct let rows = N.n let cols = C.n end)
  module MC = Matrix(struct let rows = R.n let cols = C.n end)

  let multiply a b =
    let c = MC.create () in
    for r = 0 to R.n - 1 do
      for col = 0 to C.n - 1 do
        let s = ref 0.0 in
        for k = 0 to N.n - 1 do
          s := !s +. MA.get a r k *. MB.get b k col
        done;
        MC.set c r col !s
      done
    done;
    c
end

module D2 = struct let n = 2 end
module D3 = struct let n = 3 end

module M2x3 = Matrix(struct let rows = 2 let cols = 3 end)
module M3x2 = Matrix(struct let rows = 3 let cols = 2 end)
module Mul23 = MatMul(D2)(D3)(D2)

let () =
  let a = M2x3.create () in
  M2x3.set a 0 0 1.0; M2x3.set a 0 1 2.0; M2x3.set a 0 2 3.0;
  M2x3.set a 1 0 4.0; M2x3.set a 1 1 5.0; M2x3.set a 1 2 6.0;
  Printf.printf "A (2×3):\n"; M2x3.print a