Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 40 ยท Lists, Arrays and Records

Arrays in OCaml

Use OCaml's fixed-size mutable arrays: literals, indexing, Array.make and init, updating with <-, the Array module, 2D arrays, aliasing pitfalls and when to choose arrays over lists.

An array is a fixed-size, mutable sequence stored in one contiguous block of memory. Reading or writing any element takes constant time, unlike a list, where reaching element i costs O(i). Arrays are the tool for numeric work, lookup tables, dynamic programming, and anything that needs fast index access. Like lists, all elements have the same type.

Creating arrays

OCAML
# [| 1; 2; 3 |];;
- : int array = [|1; 2; 3|]
# Array.make 4 0;;
- : int array = [|0; 0; 0; 0|]
# Array.init 5 (fun i -> i * i);;
- : int array = [|0; 1; 4; 9; 16|]
# [||];;
- : 'a array = [||]

The literal syntax is [| ... |] with semicolons. Array.make n x creates n copies of x; Array.init n f computes element i as f i.

Indexing and updating

Use .( ) to read and <- to write. Indexing starts at 0:

OCAML
let a = [| 10; 20; 30 |]
let first = a.(0)          (* 10 *)
let () = a.(1) <- 99       (* a is now [|10; 99; 30|] *)
let n = Array.length a     (* 3 *)

a.(i) <- v is an expression of type unit. It changes the array in place. (This is one of the places where OCaml is imperative: see the later chapter on imperative features.)

Access outside the range raises an exception instead of reading arbitrary memory:

OCAML
# a.(3);;
Exception: Invalid_argument "index out of bounds".

Looping over arrays

OCAML
let () =
  for i = 0 to Array.length a - 1 do
    Printf.printf "a.(%d) = %d\n" i a.(i)
  done

for i = lo to hi do ... done includes both ends and has type unit; downto counts down. Higher-order helpers avoid index arithmetic:

OCAML
let () = Array.iter (fun x -> Printf.printf "%d " x) a
let () = Array.iteri (fun i x -> Printf.printf "%d:%d " i x) a

The Array module

OCAML
# Array.map (fun x -> x * 2) [|1; 2; 3|];;
- : int array = [|2; 4; 6|]
# Array.fold_left (+) 0 [|1; 2; 3|];;
- : int = 6
# Array.to_list [|1; 2; 3|];;
- : int list = [1; 2; 3]
# Array.of_list [1; 2; 3];;
- : int array = [|1; 2; 3|]
# Array.append [|1|] [|2; 3|];;
- : int array = [|1; 2; 3|]
# Array.sub [|10; 20; 30; 40|] 1 2;;
- : int array = [|20; 30|]
# Array.exists (fun x -> x > 2) [|1; 2; 3|];;
- : bool = true

Array.map, iter, fold_left, exists, for_all, mem and filter exist as for lists. Sorting an array happens in place:

OCAML
let b = [| 5; 2; 9; 1 |]
let () = Array.sort compare b      (* b is now [|1; 2; 5; 9|] *)

Array.copy makes a fresh array with the same elements:

OCAML
let c = Array.copy b

Binary search by hand

Because index access is O(1), binary search on a sorted array is O(log n):

OCAML
let binary_search a target =
  let rec go lo hi =
    if lo > hi then None
    else
      let mid = lo + (hi - lo) / 2 in
      if a.(mid) = target then Some mid
      else if a.(mid) < target then go (mid + 1) hi
      else go lo (mid - 1)
  in
  go 0 (Array.length a - 1)

Aliasing: arrays are references

Assigning an array to another name does not copy it:

OCAML
let x = [| 1; 2; 3 |]
let y = x
let () = y.(0) <- 100
(* x.(0) is also 100 *)

Both names point to the same block. Use Array.copy when you need an independent array.

A subtle trap is Array.make with a mutable element, since it fills with the same object:

OCAML
let grid = Array.make 3 (Array.make 3 0)    (* WRONG: three rows are one array *)
let () = grid.(0).(0) <- 1
(* every row now starts with 1 *)

Create each row separately with Array.init:

OCAML
let grid = Array.init 3 (fun _ -> Array.make 3 0)
let () = grid.(0).(0) <- 1       (* only the first row changes *)

A 2D array is an array of arrays; access it with grid.(r).(c).

Lists or arrays?

list array
access element i O(i) O(1)
add at the front O(1) O(n) (new array)
change one element O(n) (rebuild) O(1) in place
size any, grows by consing fixed at creation
immutable yes no
pattern matching natural limited (fixed shapes)

Choose lists for recursive, functional code with data of unknown size, and arrays for numeric loops and random access. A growable array exists as Dynarray in OCaml 5.2+.

Float arrays and bytes

An array of floats is stored unboxed, so float array is compact and fast; Bytes is the mutable counterpart of string. Both are useful for numerical and binary data.

A stand-in: aliasing and copying

JavaScript arrays are mutable references like OCaml arrays, so the aliasing pitfalls match. Run the stand-in to see the shared-rows bug and its fix.

JS Stand-in: shared rows and copies

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How do you set the element at index 2 of array a to 7?

    Arrays use a.(i) for reading and a.(i) <- v for writing.
  2. 2. What happens on a.(10) for an array of length 3?

    Bounds are checked at run time and violations raise an exception.
  3. 3. Why is Array.make 3 (Array.make 3 0) a wrong way to build a 3x3 grid?

    Array.make repeats the same value, so mutable elements are shared. Use Array.init.
  4. 4. Which statement is true?

    Arrays are mutable blocks of fixed size with constant-time indexing; Array.sort sorts in place.

Summary

  • Arrays are fixed-size, mutable and indexed in O(1): [| 1; 2 |], a.(i), a.(i) <- v.
  • Create with Array.make and Array.init; use Array.copy to duplicate.
  • The Array module offers map, iter, fold_left, sort, sub, append and conversions.
  • Bounds are checked; aliasing means two names can share one array.
  • Choose lists for recursion and arrays for random access and numeric work.

Next: Records