Functional Arrays

Conventional vs. functional arrays

Property	Conventional array	Functional array
Update	In-place: a.(k) <- x	Returns new array: update(A, k, x)
Old version	Destroyed	Persists unchanged
Style	Imperative	Pure functional
Lookup	O(1) (hardware)	O(log n)

Functional arrays are a finite map from integers to data, where every update produces a new array rather than mutating the existing one. The challenge is doing this efficiently without copying the entire array.

Braun trees

The representation, credited to W. Braun, stores array elements in a balanced binary tree where the path to element i is determined by the binary representation of i:

The subscript arithmetic:

if k = 1        → the root
if k mod 2 = 0  → go left, then recurse on k/2
if k mod 2 = 1  → go right, then recurse on k/2

Equivalently: write k in binary, discard the leading 1, reverse the remaining bits, and interpret 0 as “go left” and 1 as “go right”. This scheme guarantees a balanced tree, ensuring O(log n) access for all subscripts.

sub: array lookup

exception Subscript

let rec sub = function
  | Lf, _ -> raise Subscript
  | Br (v, t1, t2), k ->
      if k = 1 then v
      else if k mod 2 = 0 then
        sub (t1, k / 2)
      else
        sub (t2, k / 2)

Divides the subscript by 2 repeatedly until reaching 1. At each step, the parity determines which subtree to follow. If a leaf is reached before subscript 1, the position does not exist and Subscript is raised.

update: functional array update

let rec update = function
  | Lf, k, w ->
      if k = 1 then
        Br (w, Lf, Lf)        (* extend the array *)
      else
        raise Subscript        (* gap in the tree *)
  | Br (v, t1, t2), k, w ->
      if k = 1 then
        Br (w, t1, t2)         (* replace root value *)
      else if k mod 2 = 0 then
        Br (v, update (t1, k / 2, w), t2)
      else
        Br (v, t1, update (t2, k / 2, w))

Two cases for k = 1:

• At a leaf: extend the array by creating a new branch (the array grows).
• At a branch: replace the existing value (update in place functionally).

Like BST update, only the path from root to the target index is copied, giving O(log n) time and space. Unchanged subtrees are shared.

Why binary?

The subscript arithmetic works because binary decisions (left/right) reduce the search space by half at each step. This is the fundamental reason binary is important in computer science: an if-then-else leads to binary branching, which turns an O(n) cost into O(log n). Two is the smallest integer divisor that achieves this reduction.