775 Fundamental

775-const-array-size — Const Array Size

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "775-const-array-size — Const Array Size" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Heap-allocated `Vec<T>` is versatile but has overhead: a pointer, length, and capacity word, plus a heap allocation. Key difference from OCaml: 1. **Stack vs heap**: Rust's `StackVec<T, CAP>` is stack

Tutorial

The Problem

Heap-allocated Vec<T> is versatile but has overhead: a pointer, length, and capacity word, plus a heap allocation. For collections with a small, known maximum size (network packet fields, audio samples, fixed-size queues), a stack-allocated vector with a compile-time capacity bound eliminates all this overhead. StackVec<T, CAP> provides Vec-like operations with a static capacity guarantee, failing gracefully when the capacity is exceeded rather than allocating more space.

🎯 Learning Outcomes

• Implement StackVec<T: Copy + Default, const CAP: usize> with data: [T; CAP] and a len: usize runtime counter

• Provide push() -> Result<(), T> that returns the item on overflow instead of panicking

• Implement pop() -> Option<T>, get(i), and as_slice() for Vec-like ergonomics

• Verify size: size_of::<StackVec<u8, 64>>() = 64 + 8 (len) bytes — no heap pointer

• See real-world applications: heapless::Vec in embedded Rust, arrayvec crate

Code Example

pub struct StackVec<T: Copy + Default, const CAP: usize> {
    data: [T; CAP],
    len: usize,
}

let mut v: StackVec<i32, 4> = StackVec::new();
v.push(1)?;

(* Array with runtime capacity check *)
type 'a stack_vec = {
  data: 'a array;
  mutable len: int;
}

let create cap default = {
  data = Array.make cap default;
  len = 0;
}

Key Differences

Stack vs heap: Rust's StackVec<T, CAP> is stack-allocated for small CAP; OCaml arrays are always heap-allocated.

Overflow handling: Rust returns Err(item) on overflow, giving callers control; OCaml would raise an exception.

Embedded use: heapless::Vec (Rust crate) is used in no_std embedded firmware; OCaml cannot target microcontrollers without GC.

Type system: StackVec<u8, 64> and StackVec<u8, 128> are different Rust types; OCaml arrays of different sizes are the same type.

OCaml Approach

OCaml has no stack-allocated arrays of generic size. All arrays (Array.make n x) are heap-allocated. For fixed-size buffers, OCaml uses Bytes.create n (mutable) or Bigarray (C-backed). The Cstruct library in MirageOS provides a StackVec-like interface over C-allocated buffers for network packet processing. OCaml's GADT-based length-indexed lists provide type-level length tracking but are heap-allocated.

Full Source

#![allow(clippy::all)]
//! # Const Array Size
//!
//! Using const generics for array sizes.

/// Stack-allocated vector with compile-time capacity
#[derive(Debug, Clone)]
pub struct StackVec<T: Copy + Default, const CAP: usize> {
    data: [T; CAP],
    len: usize,
}

impl<T: Copy + Default, const CAP: usize> StackVec<T, CAP> {
    pub fn new() -> Self {
        StackVec {
            data: [T::default(); CAP],
            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, value: T) -> Result<(), T> {
        if self.len < CAP {
            self.data[self.len] = value;
            self.len += 1;
            Ok(())
        } else {
            Err(value)
        }
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len > 0 {
            self.len -= 1;
            Some(self.data[self.len])
        } else {
            None
        }
    }

    pub fn get(&self, index: usize) -> Option<&T> {
        if index < self.len {
            Some(&self.data[index])
        } else {
            None
        }
    }

    pub fn as_slice(&self) -> &[T] {
        &self.data[..self.len]
    }

    pub fn clear(&mut self) {
        self.len = 0;
    }
}

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

/// Create an array from a function
pub fn array_from_fn<T: Copy, const N: usize>(f: impl Fn(usize) -> T) -> [T; N] {
    std::array::from_fn(f)
}

/// Sum of array elements
pub fn sum<const N: usize>(arr: &[i32; N]) -> i32 {
    arr.iter().sum()
}

/// Product of array elements
pub fn product<const N: usize>(arr: &[i32; N]) -> i32 {
    arr.iter().product()
}

/// Zip two arrays
pub fn zip_arrays<T: Copy, U: Copy, const N: usize>(a: &[T; N], b: &[U; N]) -> [(T, U); N] {
    std::array::from_fn(|i| (a[i], b[i]))
}

/// Map over array
pub fn map_array<T: Copy, U: Copy + Default, const N: usize>(
    arr: &[T; N],
    f: impl Fn(T) -> U,
) -> [U; N] {
    std::array::from_fn(|i| f(arr[i]))
}

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

    #[test]
    fn test_stack_vec() {
        let mut v: StackVec<i32, 4> = StackVec::new();
        assert_eq!(v.capacity(), 4);
        assert!(v.is_empty());

        v.push(1).unwrap();
        v.push(2).unwrap();
        assert_eq!(v.len(), 2);
        assert_eq!(v.as_slice(), &[1, 2]);
    }

    #[test]
    fn test_stack_vec_full() {
        let mut v: StackVec<i32, 2> = StackVec::new();
        assert!(v.push(1).is_ok());
        assert!(v.push(2).is_ok());
        assert!(v.push(3).is_err());
    }

    #[test]
    fn test_sum() {
        assert_eq!(sum(&[1, 2, 3, 4, 5]), 15);
    }

    #[test]
    fn test_product() {
        assert_eq!(product(&[1, 2, 3, 4]), 24);
    }

    #[test]
    fn test_zip_arrays() {
        let a = [1, 2, 3];
        let b = ['a', 'b', 'c'];
        let zipped = zip_arrays(&a, &b);
        assert_eq!(zipped, [(1, 'a'), (2, 'b'), (3, 'c')]);
    }

    #[test]
    fn test_map_array() {
        let arr = [1, 2, 3, 4];
        let doubled = map_array(&arr, |x| x * 2);
        assert_eq!(doubled, [2, 4, 6, 8]);
    }
}

(* Fixed-size containers with module-level size in OCaml *)

module type CAPACITY = sig val cap : int end

(* Ring buffer *)
module RingBuffer (C : CAPACITY) = struct
  type 'a t = {
    mutable data: 'a array;
    mutable head: int;
    mutable size: int;
    default: 'a;
  }

  let create default =
    { data = Array.make C.cap default; head = 0; size = 0; default }

  let push rb v =
    let tail = (rb.head + rb.size) mod C.cap in
    rb.data.(tail) <- v;
    if rb.size < C.cap then rb.size <- rb.size + 1
    else rb.head <- (rb.head + 1) mod C.cap

  let to_list rb =
    List.init rb.size (fun i -> rb.data.((rb.head + i) mod C.cap))

  let capacity = C.cap
end

module Cap5 = struct let cap = 5 end
module Ring5 = RingBuffer(Cap5)

let () =
  let rb = Ring5.create 0 in
  Printf.printf "Capacity: %d\n" Ring5.capacity;
  for i = 1 to 7 do Ring5.push rb i done;
  (* Only last 5 should remain *)
  Printf.printf "Contents: [%s]\n"
    (String.concat "; " (List.map string_of_int (Ring5.to_list rb)))

✓ Tests Rust test suite

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

    #[test]
    fn test_stack_vec() {
        let mut v: StackVec<i32, 4> = StackVec::new();
        assert_eq!(v.capacity(), 4);
        assert!(v.is_empty());

        v.push(1).unwrap();
        v.push(2).unwrap();
        assert_eq!(v.len(), 2);
        assert_eq!(v.as_slice(), &[1, 2]);
    }

    #[test]
    fn test_stack_vec_full() {
        let mut v: StackVec<i32, 2> = StackVec::new();
        assert!(v.push(1).is_ok());
        assert!(v.push(2).is_ok());
        assert!(v.push(3).is_err());
    }

    #[test]
    fn test_sum() {
        assert_eq!(sum(&[1, 2, 3, 4, 5]), 15);
    }

    #[test]
    fn test_product() {
        assert_eq!(product(&[1, 2, 3, 4]), 24);
    }

    #[test]
    fn test_zip_arrays() {
        let a = [1, 2, 3];
        let b = ['a', 'b', 'c'];
        let zipped = zip_arrays(&a, &b);
        assert_eq!(zipped, [(1, 'a'), (2, 'b'), (3, 'c')]);
    }

    #[test]
    fn test_map_array() {
        let arr = [1, 2, 3, 4];
        let doubled = map_array(&arr, |x| x * 2);
        assert_eq!(doubled, [2, 4, 6, 8]);
    }
}

Deep Comparison

OCaml vs Rust: Const Array Size

Stack-Allocated Vec

Rust

pub struct StackVec<T: Copy + Default, const CAP: usize> {
    data: [T; CAP],
    len: usize,
}

let mut v: StackVec<i32, 4> = StackVec::new();
v.push(1)?;

OCaml

No direct equivalent. Would need:

(* Array with runtime capacity check *)
type 'a stack_vec = {
  data: 'a array;
  mutable len: int;
}

let create cap default = {
  data = Array.make cap default;
  len = 0;
}

Array Functions with Size

Rust

pub fn sum<const N: usize>(arr: &[i32; N]) -> i32 {
    arr.iter().sum()
}

pub fn zip_arrays<T, U, const N: usize>(a: &[T; N], b: &[U; N]) -> [(T, U); N] {
    // Size match guaranteed at compile time!
}

OCaml

(* Runtime size check *)
let zip a b =
  if Array.length a <> Array.length b then
    invalid_arg "different lengths";
  Array.init (Array.length a) (fun i -> (a.(i), b.(i)))

Key Differences

Aspect	OCaml	Rust
Size guarantee	Runtime check	Compile-time
Stack allocation	Not controllable	Explicit with `[T; N]`
Type errors	Runtime	Compile-time
No allocation	Arrays copy	Arrays are inline

Exercises

Implement extend_from_slice(slice: &[T]) -> Result<(), ()> that copies all slice elements into the StackVec or fails if there is insufficient capacity.

Add sort(&mut self) using self.data[..self.len].sort() and verify it works correctly with the length boundary.

Implement StackVec::from_slice<const N: usize>(s: &[T; N]) -> Option<Self> that creates a StackVec from a fixed array, returning None if N > CAP.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust