Moving on Data structures
Tags: ocaml, newbie, howto, tutorial
Published: 2021-08-10 14:40:58

### Lists

Lists are immutable. Lists let you hold any number of items of the same type.

```ocaml
let l = ["i"; "am"; "list"];;
```

### Tuples

A tuple is an ordered collection of values that can each be of a different type. You can create a tuple by joining values together with a comma.   

```ocaml
let a_tuple = (3,"three") ;;
val a_tuple : int * string = (3, "three")
let another_tuple = (3,"four",5.) ;;
val another_tuple : int * string * float = (3, "four", 5.)
```

Destructuring of a tuple

```ocaml
let (x,y) = a_tuple ;;

(**val x : int = 3
  val y : string = "three" *)
```

Adding elements in front of list

```ocaml
"French" :: "Spanish" :: languages ;;
(** - : string list = ["French"; "Spanish"; "OCaml"; "Perl"; "C"] *)
```
Concatenation of two lists

```ocaml
[1;2;3] @ [4;5;6] ;;
(** - : int list = [1; 2; 3; 4; 5; 6] *)
```

### Records

```ocaml
type point2d = { x : float; y : float }
```

Destructuring of the record

```ocaml
let magnitude { x = x_pos; y = y_pos } =
Float.sqrt (x_pos **. 2. +. y_pos **. 2.)
;;
(* val magnitude : point2d -> float = <fun> *)
```

Composing records

```ocaml
type circle_desc  = { center: point2d; radius: float }
type rect_desc    = { lower_left: point2d; width: float; height: float }
type segment_desc = { endpoint1: point2d; endpoint2: point2d }
```

Variant types

```ocaml
type scene_element =
  | Circle  of circle_desc
  | Rect    of rect_desc
  | Segment of segment_desc
```

### Arrays

The mutable guy.

```ocaml
let numbers = [| 1; 2; 3; 4 |] ;;
(* val numbers : int array = [|1; 2; 3; 4|] *)

numbers.(2) <- 4 ;;
(* - : unit = () )*
numbers ;;

(* - : int array = [|1; 2; 4; 4|] *)
```

The .(i) syntax is used to refer to an element of an array, and the <- syntax is for modification. Because the elements of the array are counted starting at zero, element .(2) is the third element.

What is Unit? Unit it's just a placeholder similar to void in other more mainstream languages

### Mutable records

Records, which are immutable by default, can have some of their fields explicitly declared as mutable. Here’s an example of a mutable data structure for storing a running statistical summary of a collection of numbers. 

```ocaml
type running_sum =
  { mutable sum: float;
    mutable sum_sq: float; (* sum of squares *)
    mutable samples: int;
  }
```

Let's write some imperative stuff

```ocaml
let mean rsum = rsum.sum /. Float.of_int rsum.samples
let stdev rsum =
  Float.sqrt (rsum.sum_sq /. Float.of_int rsum.samples
-. (rsum.sum /. Float.of_int rsum.samples) **. 2.)
;;
(* val mean : running_sum -> float = <fun> *)
(* val stdev : running_sum -> float = <fun> *)

let create () = { sum = 0.; sum_sq = 0.; samples = 0 }
let update rsum x =
  rsum.samples <- rsum.samples + 1;
  rsum.sum     <- rsum.sum     +. x;
  rsum.sum_sq  <- rsum.sum_sq  +. x *. x
;;
(* val create : unit -> running_sum = <fun> *)
(* val update : running_sum -> float -> unit = <fun> *)
```

Take a look into semicolons to sequence operations. When you are working purely functionally, this wasn’t necessary, but you start needing it when you’re writing imperative code.

```ocaml
let rsum = create () ;;
val rsum : running_sum = {sum = 0.; sum_sq = 0.; samples = 0}
List.iter [1.;3.;2.;-7.;4.;5.] ~f:(fun x -> update rsum x) ;;
(* - : unit = () *)
mean rsum ;;
(* - : float = 1.33333333333333326 *)
stdev rsum ;;
(* - : float = 3.94405318873307698 *)
```

### Refs

Ref is a single mutable variable (hi ma react boys)

```ocaml
let x = { contents = 0 } ;;
val x : int ref = {contents = 0}
x.contents <- x.contents + 1 ;;
- : unit = ()
x ;;
- : int ref = {contents = 1}
```

Some syntactic sugar for ref

```ocaml
let x = ref 0  (* create a ref, i.e., { contents = 0 } *) ;;
(* val x : int ref = {Base.Ref.contents = 0} *)
!x             (* get the contents of a ref, i.e., x.contents *) ;;
(* - : int = 0 *)
x := !x + 1    (* assignment, i.e., x.contents <- ... *) ;;
(* - : unit = () *)
!x ;;
(* - : int = 1 *)
```

Nothing magic here, let's implement the ref by ourselves

```ocaml
type 'a ref = { mutable contents : 'a } ;;
type 'a ref = { mutable contents : 'a; }
let ref x = { contents = x } ;;
(* val ref : 'a -> 'a ref = <fun> *)
let (!) r = r.contents ;;
(* val ( ! ) : 'a ref -> 'a = <fun> *)
let (:=) r x = r.contents <- x ;;
(* val ( := ) : 'a ref -> 'a -> unit = <fun> *)
```