OCAML Course

Lists

Go back

A list is an array of values. Every value in a list got the same type.

type 'a list = [] | (::) of 'a * 'a list
  • []: empty list
  • a::list: create a list with a then a list list

Notice that the type is 'a, meaning that we can create a list of int, float, ... or even a list of lists (if 'a = int list then we got int list list) with this constructor.


New list

As you read, a list is either an empty list or a value followed by a list, so we have

let empty_list = []
(* both are the same *)
let list_5 = 5::[]
let list_5 = [5]
(* Both are giving the same result *)
let list_7_5 = 7::list_5 (* append *)
let list_7_5 = [7;5] (* create *)

You may use @ to add a value at the end of the list such as [5;6]@[7], but my teachers are against this ("There is always a better way to do something, without using this sh*t").

  • []: empty list (result: [])
  • [a;b;...]: a list with a, b, ... (result: [a;b,...])
  • a::[]: add a to empty list (result: [a])
  • a::b::[]: add b then a to empty list (result: [a;b])
  • a::list: add a to the list list (result: [a;...])

Notice: the values are separated by a semi-colon (;), we are already using commas (,) for composite types after all 😱.


Some functions

let length = List.length [5;6] (* 2 *)
let merge = List.concat [[5;6];[7;8]] (* [5;6;7;8] *)
let reversed = List.rev [5;6] (* [6;5] *)
let head = List.hd [5;6] (* 5 *)
let tail = List.tl [5;6] (* [6] *)
let is_inside = List.mem 5 [5;6] (* true *)

(* higher-order function 🚀 *)
let plus_one = List.map (fun x -> x+1) [5;6] (* [6;7] *)
let remove_five = List.filter (fun x -> x <> 5) [5;6] (* [6] *)

You got the complete list of functions here.


Folds

If you are planning to call a function on every element of the list (such as List.map), but unlike with map, you need to update a result (accumulator), then you will use folds.

Examples

  • I want the min value in a list
    • I will store in an accumulator the first value ("init")
    • I will check every value, and update my accumulator if needed ("update")
  • I want the number of elements in a list (without List.length)
    • I will store 0 in an accumulator ("init")
    • Each time I will find an element, I will increase my accumulator by one ("update")

As "accumulator" is too wordy, I will go with "acc". You got either List.fold_left (terminal) or List.fold_right (non terminal).

$$ \[ \begin{split} f_{n}(f_{n-1}(...f_{2}(f_{1}(list))...))\quad \scriptsize\text{(fold left)}\\ \textbf{vs}\\ f_{1}(f_{2}(...f_{n-1}(f_{n}(x))...))\quad \scriptsize\text{(fold right)} \end{split} \]
  • List.fold_left: ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
  • List.fold_right: ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
List.length with fold

With a fold_left

let get_length l =
	List.fold_left
		(fun acc _ -> acc + 1) (* update *)
		0 (* init *)
		l (* what are we iterating? *)

With a fold_right

let get_length l =
	List.fold_right
		(fun acc _ -> acc + 1) (* update *)
		l (* what are we iterating? *)
		0 (* init *)
List.min with fold

With a fold_left

let get_min l =
	(* raise exception if not in the list *)
	if l = [] then raise Not_found
	(* else do your job *)
	else List.fold_left
		 (fun acc v -> if v < acc then v else acc) (* update *)
		 (List.hd l) (* init *)
		 l (* what are we iterating? *)

With a fold_right

let get_min l =
	(* raise exception if not in the list *)
	if l = [] then raise Not_found
	(* else do your job *)
	else List.fold_right
		 (fun v acc -> if v < acc then v else acc) (* update *)
		 l (* what are we iterating? *)
		 (List.hd l) (* init *)