OCaml website lists 99 basic problems. Here I give the solutions and explain them.

List

1. Write a function last : 'a list -> 'a option that returns the last element of a list. (easy)

In face, a loop in OCaml could be represented by a recursive function. We use match to consider different cases of list: empty, one element, more than one elements.

1
2
3
4
5
6
7
8
9
10
11
12
let rec last lst = 
match lst with
| [] -> []
| hd :: [] -> hd
| hd :: tl -> last tl
;;
(* or it is written as following (without parameter): *)
let rec last = function
| [] -> []
| hd :: [] -> hd
| hd :: tl -> last tl
;;

2. Find the last but one (last and penultimate) elements of a list. (easy)

This problem ask you return last two elements of a list if it has. It is similar to the first problem.

1
2
3
4
5
6
7
let last_two lst = 
match lst with
| [ ] -> None (* empty *)
| [_] -> None (* one element *)
| [h1;h2] -> Some (h1, h2) (* two element *)
| _ :: tl -> last_two tl (* more than two*)
;;

3. Find the k’th element of a list. (easy)

To solve this problem, it seem that we need a counter inside to compute the number of loops. When we traverse the list, assume the list is hd :: tl, if k is equal to 1, then return hd, otherwise traverse tl with k - 1.

1
2
3
4
5
6
7
let rec list_nth lst k =     
match lst with
| [] -> None
| hd :: tl ->
if k = 1 then Some hd
else list_nth tl (k - 1)
;;

OCaml List module provides List.nth function.

1
2
3
4
5
6
7
8
9
let nth l n =
if n < 0 then invalid_arg "List.nth" else
let rec nth_aux l n =
match l with
| [] -> failwith "nth"
| a :: l ->
if n = 0 then a
else nth_aux l (n-1)
in nth_aux l n

4. return the length of a list. (easy)

1
2
3
4
let length lst = 
match lst with
| [] -> 0
| hd :: tl -> 1 + (length tl)

5. Reverse a list. (easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let rev lst = 
match lst with
| [] -> []
| hd :: tl -> (rev tl) @ [hd]
;;

(* or it is written as following *)

let rev ls =
let rec rev_acc acc l=
match l with
| [] -> acc
| hd :: tl -> rev_acc (hd::acc) tl
in
rev_acc [] ls
;;

6. Find out whether a list is a palindrome. (easy)

1
2
let is_palindrome lst =
lst = (rev lst)

8. Eliminate consecutive duplicates of list elements. (medium)

1
2
3
4
5
6
7
8
let rec compress lst = 
match lst with
| [] -> []
| [x] -> [x]
| h1 :: h2 :: tl ->
if h1 = h2 then compress h2::tl
else [h1] @ (compress (h2 :: tl))
;;

9. Pack consecutive duplicates of list elements into sublists. (medium)

This problem is a little difficult. Usually, we will use local variables to store the temporary list and final list in C++. However, in OCaml, the idea is to define aux function with parameters. The parameters are regarded as local variables. In the code shown below, cur stores the current list store the same elements and acc store the whole list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pack ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"d";"e";"e";"e";"e"];;
- : string list list =
[["a"; "a"; "a"; "a"]; ["b"]; ["c"; "c"]; ["a"; "a"]; ["d"; "d"];
["e"; "e"; "e"; "e"]]

(********************************************)

let pack lst =
let rec aux cur acc ls =
match ls with
| [] -> []
| [x] -> (x :: cur) :: acc
| a :: b :: tl ->
if a = b then aux (a :: cur) acc (b :: tl)
else aux [] ( (a:: cur) :: acc) (b::tl) in
rev (aux [] [] lst)
;;

If you like C++ style, you can implement like this

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
let pack_v2 list = 
begin
let res = ref [] in
let tem = ref [] in
let rec pack_lst lst =
match lst with
| [] -> ()
| [x] -> (res := !res @ [[x] @ !tem])
| hd1 :: hd2 :: tl ->
if hd1 = hd2
then
(
tem := hd1 :: (!tem) ;
pack_lst (hd2::tl)
)
else
(
tem := hd1 :: (!tem);
res := !res @ [!tem];
tem := [];
pack_lst (hd2::tl)
)
in
pack_lst list;
!res
end

10. Run-length encoding of a list. (easy)

This problem is similar to the 9th problem.

1
2
3
4
5
6
7
8
9
10
11
12
encode ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];;
=
[(4, "a"); (1, "b"); (2, "c"); (2, "a"); (1, "d"); (4, "e")]

let encode list =
let rec aux count acc = function
| [] -> []
| [x] -> (count+1, x) :: acc
| a :: (b :: _ as t) ->
if a = b then aux (count + 1) acc t
else aux 0 ((count+1,a) :: acc) t in
rev (aux 0 [] list);;

11. Modified run-length encoding. (easy)

Modify the result of the previous problem in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N E) lists.

Since OCaml lists are homogeneous, one needs to define a type to hold both single elements and sub-lists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
encode ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];;
=
[Many (4, "a"); One "b"; Many (2, "c"); Many (2, "a"); One "d";
Many (4, "e")]
(*********************************)

type 'a rle =
| One of 'a
| Many of int * 'a;;

let encode lst =
let create_tuple cnt elem =
if cnt = 1 then One elem
else Many(cnt, elem) in
let rec aux count acc ls =
match ls with
| [] -> []
| [x] -> create_tuple (count+1 x) :: acc
| h1::(h2::_ as tl) ->
if (h1 = h2) then aux (count+1) acc tl
else aux 0 ((create_tuple (count + 1) h1) :: acc tl in
rev (aux 0 [] lst)
;;

12. Decode a run-length encoded list. (medium)

Given a run-length code list generated as specified in the previous problem, construct its uncompressed version.

tips: use variable acc (represented by a parameter) to store the result. If match One x; then add x into acc. If match Many (n x), then add x n times. One solution is to write a for loop. Or we write a recursive function.

1
2
3
let rec many acc n x = 
if n = 0 then acc
else many (x::acc) (n - 1) x

This loop adds x into acc n times and return acc.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
decode [Many (4,"a"); One "b"; Many (2,"c"); Many (2,"a"); One "d"; Many (4,"e")];;
=
["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "e"; "e"; "e"; "e"]

let decode lst =
let rec many acc n x =
if n = 0 then acc
else many (x :: acc) (n-1) x in
let aux count acc ls =
match ls with
| [] -> []
| One x :: tl ->auc ([x] :: acc) tl
| Many(n, x) :: tl -> aux (many acc n x) tl in
aux [] (rev lst)

13. Run-length encoding of a list (direct solution). (medium)

Implement the so-called run-length encoding data compression method directly. I.e. don’t explicitly create the sublists containing the duplicates, as in problem “9. Pack consecutive duplicates of list elements into sublists”, but only count them. As in problem “10. Modified run-length encoding”, simplify the result list by replacing the singleton lists (1 X) by X.

1
2
3
4
encode ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];;
- : string rle list =
[Many (4, "a"); One "b"; Many (2, "c"); Many (2, "a"); One "d";
Many (4, "e")]
1
2
3
4
5
6
7
8
9
10
11
12
13
let encode list =
let add count x =
if count = 0 then One x
else Many (count+1,x) in
let rec aux count acc lst =
match lst with
| [] -> []
| [x] -> add (count x) :: acc
| h1 :: (h2 :: _ as tl)->
if h1 = h2 then aux (count +1) acc tl
else aux 0 (add count h1) ::acc tl in
rev(aux 0 [] list)
;;