DEV Community

Andrey Frolov
Andrey Frolov

Posted on

Moving on Data structures

Lists

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

let l = ["i"; "am"; "list"];;
Enter fullscreen mode Exit fullscreen mode

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.

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.)
Enter fullscreen mode Exit fullscreen mode

Destructuring of a tuple

let (x,y) = a_tuple ;;

(**val x : int = 3
  val y : string = "three" *)
Enter fullscreen mode Exit fullscreen mode

Adding elements in front of list

"French" :: "Spanish" :: languages ;;
(** - : string list = ["French"; "Spanish"; "OCaml"; "Perl"; "C"] *)
Enter fullscreen mode Exit fullscreen mode

Concatenation of two lists

[1;2;3] @ [4;5;6] ;;
(** - : int list = [1; 2; 3; 4; 5; 6] *)
Enter fullscreen mode Exit fullscreen mode

Records

type point2d = { x : float; y : float }
Enter fullscreen mode Exit fullscreen mode

Destructuring of the record

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

Composing records

type circle_desc  = { center: point2d; radius: float }
type rect_desc    = { lower_left: point2d; width: float; height: float }
type segment_desc = { endpoint1: point2d; endpoint2: point2d }
Enter fullscreen mode Exit fullscreen mode

Variant types

type scene_element =
  | Circle  of circle_desc
  | Rect    of rect_desc
  | Segment of segment_desc
Enter fullscreen mode Exit fullscreen mode

Arrays

The mutable guy.

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|] *)
Enter fullscreen mode Exit fullscreen mode

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.

type running_sum =
  { mutable sum: float;
    mutable sum_sq: float; (* sum of squares *)
    mutable samples: int;
  }
Enter fullscreen mode Exit fullscreen mode

Let's write some imperative stuff

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> *)
Enter fullscreen mode Exit fullscreen mode

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.

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 *)
Enter fullscreen mode Exit fullscreen mode

Refs

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

let x = { contents = 0 } ;;
val x : int ref = {contents = 0}
x.contents <- x.contents + 1 ;;
- : unit = ()
x ;;
- : int ref = {contents = 1}
Enter fullscreen mode Exit fullscreen mode

Some syntactic sugar for ref

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 *)
Enter fullscreen mode Exit fullscreen mode

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

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> *)
Enter fullscreen mode Exit fullscreen mode

Discussion (0)