Source

John Whitington, OCaml from the Very Beginning, Chapter 4: Making Lists

Contents

Question 1

Write a function evens which does the opposite to odds, returning the even numbered elements in a list. For example, evens [2; 4; 2; 4; 2] should return [4; 4]. What is the type of your function?

The function’s type is α list because it can operate over a list of items of any data type (it only inspects the list items, it does not perform operations on them).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

let rec length l =
    match l with [] -> 0
    | _::t -> 1 + length t

let rec even_elts l =
    if length l < 2 then [] else
    match l with [] -> []
        | _::b::t -> b :: even_elts t
        | _ -> l

let _ =
    assert (    [] = even_elts []);
    assert (    [] = even_elts [0]);
    assert (   [1] = even_elts [0; 1]);
    assert (   [1] = even_elts [0; 1; 2]);
    assert ([1; 3] = even_elts [0; 1; 2; 3]);
    assert ([4; 4] = even_elts [2; 4; 2; 4; 2]);
    ;;

Hint provided: “Consider three cases: (1) the argument list is empty, (2) the argument list has one element, (3) the argument list has more than one element a::b::t. In the last case, which element do we need to miss out?”

Question 2

Write a function count_true which counts the number of true elements in a list. For example, count_true [true; false; true] should return 2. What is the type of your function? Can you write a tail recursive version?

Type is bool list -> int because we are testing for Boolean values and returning an integer value representing the quantity of Boolean values in the list.

1
2
3
4
5
6
7
8
9
10
11
12
13

let rec count_true l n =
    match l with [] -> n
        | h::t -> match h with
            true -> count_true t (n + 1)
        | _ -> count_true t n

let _ = 
    assert (0 = count_true [] 0);
    assert (0 = count_true [false] 0);
    assert (0 = count_true [false; false] 0);
    assert (1 = count_true [false; true] 0);
    assert (2 = count_true [true; false; true] 0);
    ;;

Question 3

Write a function which, given a list, builds a palindrome from it. A palindrome is a list which equals its own reverse. You can assume the existence of rev and @. Write another function which determines if a list is a palindrome.

Using List.rev since that can be assumed:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

let palindrome l =
    if l = [] then l else l @ (List.rev l)

let is_palindrome l =
    l = (List.rev l)

let _ =
    assert ([] = palindrome []);
    assert ([1; 1] = palindrome [1]);
    assert ([1; 2; 2 ;1] = palindrome [1; 2]);
    assert (is_palindrome []);
    assert (is_palindrome [1]);
    assert (is_palindrome [1; 2; 1]);
    assert (is_palindrome [1; 2; 2; 1]);
    assert (not (is_palindrome [1; 2]));
    assert (not (is_palindrome [1; 2; 3]));
    ;;

Question 4

Write a function drop_last which returns all but the last element of a list. If the list is empty, it should return the empty list. So, for example, drop_last [1; 2; 4; 8] should return [1; 2; 4]. What about a tail recursive version?

My solution assumes that for a list containing a single element, that element should be dropped.

1
2
3
4
5
6
7
8
9
10
11

let rec drop_last l =
    match l with [] -> []
    | [a] -> []
    | h::t -> h :: drop_last t

let _ =
    assert ([] = drop_last []);
    assert ([] = drop_last [1]);
    assert ([1; 2] = drop_last [1; 2; 3]);
    assert ([1; 2; 4] = drop_last [1; 2; 4; 8]);
    ;;

Tail recursive version takes the length of the list as an argument.

1
2
3
4
5
6
7
8
9
10
11
12
13

let rec drop_last_tr n l =
    if n = 0 then l else
    match l with
    | [] -> []
    | [a] -> []
    | h::t -> h :: drop_last_tr (n - 1) t

let _ =
    assert ([] = drop_last_tr 0 []);
    assert ([] = drop_last_tr 1 [1]);
    assert ([1; 2] = drop_last_tr 3 [1; 2; 3]);
    assert ([1; 2; 4] = drop_last_tr 4 [1; 2; 4; 8]);
    ;;

(To avoid having to pass the length of the list, one could call the function length defined in my solution for Question 1 above.)

Question 5

Write a function member of type α → α list → bool which returns true if an element exists in a list, or false if not. For example, member 2 [1; 2; 3] should evaluate to true, but member 3 [1; 2] should evaluate to false.

This was tricky for me, for some reason. To match the argument e with the head h of the list l, I first tried the expression match h with e -> true. Print debugging (I tried ocamldebug and found it impossible to use at this point, with my limited knowledge) confirmed that this did not match the values of those integer variables — perhaps it was matching only their types?

The expression that works is match (h, e) with (a, b) when a = b -> true.

Which the book’s explanation of pattern matching had not prepared me to understand. Either there is an easier way to implement this answer to this question, within the scope of this chapter’s coverage, or the question is not solvable within that scope.

This code includes an example of print debugging using Printf.printf and #trace. (I tried diving into ocamldebug but ahem.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

let rec member e l =
    match l with [] -> false
    | h::t ->
        (* let () = Printf.printf "h=%i, e=%i\n" h e in *)
        match (h, e) with (a, b) when a = b -> true
        | _ -> member e t
    ;;

(* #trace member;; *)

let _ =
    assert (not (member 1 []));
    assert (member 1 [1]);
    assert (not (member 1 [2]));
    assert (member 2 [1; 2]);
    assert (not (member 2 [1; 3]));
    assert (member 2 [1; 2; 3]);
    assert (not (member 3 [1; 2]));
    assert (member 'a' ['a'; 'b']);
    assert (member 'b' ['a'; 'b']);
    assert (not (member 'c' ['a'; 'b']));
    ;;

Question 6

Use your member function to write a function make_set which, given a list, returns a list which contains all the elements of the original list, but has no duplicate elements. For example, make_set [1; 2; 3; 3; 1] might return [2; 3; 1]. What is the type of your function?

The function’s type is α list because it can operate over a list of items of any data type (it only inspects the list items, it does not perform operations on them).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

let rec make_set l =
    match l with [] -> []
    | [a] -> [a]
    | h::t ->
        if member h t then make_set t else h :: make_set t
    ;;

let _ =
    assert ([] = make_set []);
    assert ([1] = make_set [1]);
    assert ([1; 2] = make_set [1; 2]);
    assert ([1; 2; 3] = make_set [1; 2; 3]);
    assert ([1] = make_set [1; 1]);
    assert ([1; 2] = make_set [1; 1; 2; 2]);
    assert ([1; 2] = make_set [1; 2; 2]);
    assert ([1; 2] = make_set [1; 2; 2; 2]);
    assert ([2; 3; 1] = make_set [1; 2; 3; 3; 1]);
    assert (['a'; 'c'; 'b'] = make_set ['a'; 'b'; 'a'; 'c'; 'c'; 'b'; 'b'])
    ;;

Question 7

Can you explain why the rev function we defined is inefficient? How does the time it takes to run relate to the size of its argument? Can you write a more efficient version using an accumulating argument? What is its efficiency in terms of time taken and space used?

The rev function defined in the chapter is inefficient because in processing the list, the head of the list is appended to the tail using the @ operator, which takes time proportional to the length of its first argument. For this reason, the time the rev function takes to run is proportional to the square of the length of the list.

My tail-recursive solution, using an accumulating argument, takes time proportional to the length of the list alone.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

let rec rev_l l acc =
    match l with [] -> acc
    | h::t -> rev_l t (h::acc)
    ;;

let rev l = rev_l l [];;

let _ =
    assert ([] = rev []);
    assert ([0] = rev [0]);
    assert ([1; 0] = rev [0; 1]);
    assert ([2; 1; 0] = rev [0; 1; 2]);
    assert ([5; 4; 3; 2; 1; 0] = rev [0; 1; 2; 3; 4; 5]);
    ;;

Hint provided: “Consider in which order the @ operators are evaluated in the reverse function. How long does each append take? How many are there?”

Solution presented in book is identical to mine:

1
2
3
4
5
6
7
8

let rec rev_inner a l =
    match l with [] -> a
    | h::t -> rev_inner (h::a) t

let rev_bk l = rev_inner [] l

let _ =
    assert ([5; 4; 3; 2; 1; 0] = rev_bk [0; 1; 2; 3; 4; 5]);

Execute this file

$ codedown ocaml < 2022-12-28-pattern-matching.md | grep . | ocaml -stdin