IDisposable Thoughts

I really like ML languages (OCaml, Elm, F#). Recently I was doing the problems in 99 problems in OCaml and found my lack of understanding in some basic patterns with lists.

I decided to reimplement some basic functions and structures in OCaml from scratch as an exercise. I usually do this in a Jupyter notebook but I took my notes and I will be publishing them in my blog from now on (as a way to remember where I put that bloody notebook). You can practice and redo this samples with the Jupyter kernel for OCaml, in fact, I already have a small docker image with it ready for you to try if you want to, go and pull it from Docker Hub.

The definition of sequences

Let’s start defining a sequence, we will call it seq:

type 'a seq =
  | End
  | Next of 'a * 'a seq

type 'a seq = Nil | Next of 'a * 'a seq

As you can see we use a generic parameter 'a for the value of the sequence. We can create a sequence with numbers from 0 to 3 and an empty sequence:

let sample = Next(1, Next(2, Next(3, End))) ;;
let empty = End

val sample : int seq = Next (1, Next (2, Next (3, End)))
val empty : 'a seq = End

Basic operations

Let’s create the simplest operations in town: length, head, tail, cons and nth

let seq_length x =
  let rec length' acc = function
    | End -> acc
    | Next (_, t) -> length' (acc + 1) t
  in
  length' 0 x
;;

seq_length sample ;;
seq_length empty

val seq_length : 'a seq -> int = <fun>
- : int = 3
- : int = 0

This pattern is very common in OCaml, I call it inner accumulator loop. There is a variation of this pattern and we will see later.

The standard library in OCaml and Caml has the function length in the List module

Now it is time for the head operator, or well, it is named hd in the List module in Caml, it will return only the first element of a sequence or throw an invalid argument if the sequence is empty.

let seq_head = function
  | End -> raise (Invalid_argument "seq_head")
  | Next (x, _) -> x
;;

seq_head sample

val seq_head : 'a seq -> 'a = <fun>
- : int = 1

The contrapart of this operator is its brother tail, or tl in the List module.

let seq_tail = function
  | End -> raise (Invalid_argument "seq_tail")
  | Next (_, t) -> t
;;

seq_tail sample

val seq_tail : 'a seq -> 'a seq = <fun>
- : int seq = Next(2, Next(3, End))

Easy!

It is time for the cons operator, this is basically adding an element to the head of the sequence, in OCaml and Standard ML is denoted as well with the operator ::

let seq_cons x al = Next(x, l) ;;

seq_cons 0 sample

val seq_cons : 'a -> 'a seq -> 'a seq = <fun>
- : int seq = Next(0, Next(1, Next(2, Next(3, End))))

Last but not least, it is time to implement the nth operator, it will return the element at the index n starting from 0.

let seq_nth n l =
  if n < 0 then raise (Invalid_argument "nth") else
  match l with
    | End -> raise (Failure "nth")
    | Next (x, tl) -> if n = 0 then x else nth_seq (n - 1) tl
;;

seq_nth 0 sample ;;
seq_nth 2 sample

val seq_nth : int -> 'a seq -> 'a
- : int = 1
- : int = 3

Interestinly, this function had the potential to use the inner accumulator loop but if we see clearly it is not needed, remember, if we discard the value of a function when it returns in a recursive call it is basically tail recursive, and here we do nothing with the return value of the function until we need it.

An easy way to check if a function call is tail recursive is asking the compiler to tell us so (available since OCaml 4.04)

let seq_nth n l =
  if n < 0 then raise (Invalid_argument "nth") else
  match l with
    | End -> raise (Failure "nth")
    | Next (x, tl) -> if n = 0 then x else ((nth_seq [@tailcall]) (n - 1) tl)

In this case, if that marked call is not tail recursive (the place where we suspect is not), the compiler will throw a warning.

That is all for today, we will continue another day!.

NOTE: If somebody is interested in the Jupyter notebook for this blog post (and the whole series), it is located in my GitHub repository.