basic-structures.md

title
Basic Structures

Quick overview: Basic Structures

List

Lists are immutable, dynamically sized, homogeneous, and ordered collections of items. It is fast to add or remove elements from the front of a list, but random access is slow.

Reason lists have a very basic singly-linked implementation.

let listA = [1, 2, 3];

Add to the front using the spread operator ...:

let listB = [0, ...listA];
let listC = [-1, 0, ...listA];

Concatenate lists with the @ operator:

let listD = listA @ listB @ [7, 8];

Add to end

Adding to the end of a list is slow because the built-in list is singly linked. The expected syntax does not work and will not compile:

/* Syntax error */
let listB = [...listA, 100];

If you need to add to the end and do not care about the operation being slow, then use the concatenate operator:

let listB = listA @ [100];

A common workaround that remains performant is adding to the front of the list, then reversing the list at the end with List.rev.

Common Functions

• List Functions: module List

Map

Map over a list to change items according to some function:

let doubled = List.map(i => i * 2, list);

Fold / Reduce

Fold over a list to reduce it to one value (which may be another collection):

let max = List.fold_left(
  (result, item) => item > result ? item : result,
  initialValue,
  list,
);

Reverse

let reversed = List.rev(list);

Length

• Important: This is an O(n) operation, be careful when using this function. It is not constant time.

let n = List.length(list);

Is Empty

let isEmpty = list == [];

Pattern Matching

Pattern matching works with lists:

switch (list) {
| [first, second, ...rest] => "at least two"
| [first, ...rest] => "at least one"
| [] => "empty"
}

Array

Arrays are mutable, fixed sized, homogeneous, and ordered collections of items. Random access on an array is fast, but changing the size of an array requires recreating the entire structure.

let arrayA = [| 1, 2, 3 |];

Access elements using square brackets:

let first = arrayA[0];
let second = arrayA[1];

Update elements using assignment:

arrayA[2] = 23;

Common Functions

• Array Functions: module Array

Map

Map over an array to change items according to some function:

let doubled = Array.map(i => i * 2, array);

Fold / Reduce

Fold over an array to reduce it to one value (which may be another collection):

let max = Array.fold_left(
  (result, item) => item > result ? item : result,
  initialValue,
  array,
);

Concatenate

let combined = Array.append(arrayA, arrayB);
let combined = Array.concat([arrayA, arrayB, arrayC]);

Length

• Unlike lists this is a constant time operation. It is safe to use anywhere.

let n = Array.length(array);

Dynamic Creation

let zeroes = Array.make(length, 0);
let squares = Array.init(length, i => i * i);

Conversion to List

let list = Array.to_list(array);
let array = Array.of_list(list);

Pattern Matching

Pattern matching works with arrays, but there is no ...rest syntax like lists have:

switch (array) {
| [||] => "empty"
| [| first |] => "exactly one"
| [| first, second |] => "exactly two"
| _ => "at least three"
};

Tuple

Tuples are immutable, constant sized, and heterogeneous collections of items. They provide a way to group values together quickly.

let pair = (1, "hello");
let triple = ("seven", 8, '9');

Access specific items in a tuple using destructuring:

let (_, second) = pair;
let (first, _, third) = triple;

Or pattern matching over a tuple:

switch (pair) {
| ("hello", name) => print_endline("Hello " ++ name);
| ("bye", name) => print_endline("Goodbye " ++ name);
| (command, _) => print_endline("Unknown command: " ++ command);
};

• Note: If a tuple will have many items or be passed around often, then records should be preferred.

Records

Records are another basic structure that has named fields and heterogeneous values. There is a dedicated article on records: Records.