Source

John Whitington, OCaml from the Very Beginning, Chapter 5: Sorting Things

Contents

Question 1

In msort, we calculate the value of the expression length l / 2 twice. Modify msort to remove this inefficiency.

My solution

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

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

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

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

let rec merge x y =
    match x, y with [], l -> l
    | l, [] -> l
    | hx::tx, hy::ty ->
        if hx < hy then hx :: merge tx (hy :: ty)
        else hy :: merge (hx :: tx) ty

(*
  Change was made here, in the addition of the line
  `let half = (length l / 2) in`.
*)
let rec msort l =
    let half = (length l / 2) in
    match l with [] -> []
        | [x] -> [x]
        | _ -> let left = take half l in
                   let right = drop half l in
                       merge (msort left) (msort right)

let _ =
    assert ([] = msort []);
    assert ([0] = msort [0]);
    assert ([0; 0] = msort [0; 0]);
    assert ([0; 1] = msort [1; 0]);
    assert ([0; 1; 2] = msort [0; 1; 2]);
    assert ([0; 1; 2] = msort [2; 1; 0]);
    assert ([0; 1; 2] = msort [2; 0; 1]);
    assert ([0; 1; 2] = msort [1; 0; 2]);
    assert ([0; 1; 2] = msort [0; 2; 1]);
    assert ([0; 2; 4] = msort [2; 4; 0]);
    assert (['a'; 'b'; 'c'] = msort ['c'; 'a'; 'b']);
    assert ([0; 1; 2; 3; 4; 5] = msort [5; 0; 2; 4; 3; 1]);
    assert ([0; 1; 2; 3; 4; 4; 5; 5] = msort [5; 0; 2; 5; 4; 3; 1; 4]);
    assert ([33; 43; 45; 99; 192; 875; 985] = msort [99; 192; 33; 985; 875; 45; 43]);
    assert ([2; 6; 9; 19; 53] = msort [53; 9; 2; 6; 19]);
    ;;

Solution given in book

The added line of code is the same, but the book’s solution positions it more sensibly than I did:

Simply add an extra let to define a name representing the number we will take or drop:

1
2
3
4
5
6
7

let rec msort l =
    match l with [] -> []
        | [x] -> [x]
        | _ -> let x = (length l / 2) in
                   let left = take x l in
                       let right = drop x l in
                           merge (msort left) (msort right)

Question 2

We know that take and drop can fail if called with incorrect arguments. Show that this is never the case in msort.

My answer

The expression match l with [] -> [] | [x] -> [x] ensures that take and drop are never called with lists of length less than two.

Answer provided in book

The argument to take or drop is length l / 2 which is clearly less than or equal to length l for all possible values of l. Thus, take and drop always succeed. In our case, take and drop are only called with [sic] length l is more than 1, due to the pattern matching.

Question 3

Write a version of insertion sort which sorts the argument list into reverse order.

My solution

The only change necessary is in the comparison operator in the insert function: where insert has if x <= h..., the new function insertrev has if x >= h...:

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
27
28
29

let rec insertrev x l =
    match l with [] -> [x]
    | h::t ->
        if x >= h then x :: h :: t
        else h :: insertrev x t
    ;;

let _ =
    assert ([0] = insertrev 0 []);
    assert ([1; 0] = insertrev 1 (insertrev 0 []));
    assert ([1; 0; 2] = insertrev 1 [0; 2]);
    assert ([3; 1; 1; 2; 3; 5; 9] = insertrev 3 [1; 1; 2; 3; 5; 9]);
    ;;

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

let _ =
    assert ([] = sortrev []);
    assert ([0] = sortrev [0]);
    assert ([1; 0] = sortrev [0; 1]);
    assert ([2; 1; 0] = sortrev [2; 1; 0]);
    assert ([2; 1; 0] = sortrev [2; 0; 1]);
    assert ([2; 1; 0] = sortrev [1; 0; 2]);
    assert ([2; 1; 0] = sortrev [1; 2; 0]);
    assert ([53; 19; 9; 6; 2] = sortrev [53; 9; 2; 6; 19]);
    ;;

Solution provided in book

Identical to mine.

Question 4

Write a function to detect if a list is already in sorted order.

My solution

Pass the first element of the list as an argument along with the list itself.

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

let rec is_sorted first_elt l =
    match l with [] -> true
    | h::t ->
        if first_elt > h then false
        else is_sorted h t

let _ =
    assert (is_sorted 0 []);
    assert (is_sorted 1 [1]);
    assert (is_sorted 0 [0; 1]);
    assert (is_sorted 0 [0; 1; 2]);
    assert (is_sorted 0 [0; 1; 2; 3; 4; 5]);
    assert (is_sorted 'a' ['a'; 'b'; 'c'; 'd'; 'e'; 'f']);
    assert (false = is_sorted 0 [1; 0]);
    assert (false = is_sorted 0 [1; 0; 2]);
    assert (false = is_sorted 0 [2; 0; 1]);
    assert (false = is_sorted 0 [0; 1; 2; 3; 4; 5; 1]);
    assert (false = is_sorted 'a' ['a'; 'b'; 'c'; 'd'; 'e'; 'a']);
    ;;

Solution provided in book

I had not thought to use the expression a::b::t, as here:

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

let rec is_sorted_book l =
    match l with a::b::t -> a <= b && is_sorted_book(b::t)
    | _ -> true
let _ =
    assert (is_sorted_book []);
    assert (is_sorted_book [1]);
    assert (is_sorted_book [0; 1]);
    assert (is_sorted_book [0; 1; 2]);
    assert (is_sorted_book [0; 1; 2; 3; 4; 5]);
    assert (is_sorted_book ['a'; 'b'; 'c'; 'd'; 'e'; 'f']);
    assert (false = is_sorted_book [1; 0]);
    assert (false = is_sorted_book [1; 0; 2]);
    assert (false = is_sorted_book [2; 0; 1]);
    assert (false = is_sorted_book [0; 1; 2; 3; 4; 5; 1]);
    assert (false = is_sorted_book ['a'; 'b'; 'c'; 'd'; 'e'; 'a']);
    ;;

Question 5

We mentioned that the comparison functions like <  work for many OCaml types. Can you determine, by experimentation, how they work for lists? For example, what is the result of [1; 2] < [2; 3]? What happens when we sort the following list of type char list list? Why?

[['o'; 'n'; 'e']; ['t'; 'w'; 'o']; ['t'; 'h'; 'r'; 'e'; 'e']]

My solution

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

let _ =
    assert ([] = []);
    assert ([0; 1] = [0; 1]);
    assert ([0] < [1]);
    assert (false = ([1] < [0]));
    assert ([0; 1] < [1; 2]);
    assert (false = ([0; 1] > [1; 2]));
    assert ([0; 1; 2] < [1; 2]);
    assert ([1; 1; 2] < [1; 2]);
    assert (false = ([1; 1; 2] < [1; 1]));
    (*
    My hypothesis at this point is that each element in the first list is 
    compared with the element at the corresponding position in the second
    list.
    *)
    assert (false = ([0; 0] < [0; 0]));
    assert ([0; 0] < [0; 1]);
    assert (false = ([0; 0] < [0]));
    assert (false = ([0; 1; 2] < [0; 1; 2]));
    assert ([0; 1; 2] < [0; 1; 3]);
    assert (false = ([0; 1; 2; 3; 4; 5; 6; 7] < [0; 1; 2; 3; 4; 5; 6; 7]));
    assert ([0; 1; 2; 3; 4; 5; 6; 7] < [0; 1; 2; 3; 4; 5; 6; 8]);
    ;;

If each element in the first list is compared with the element at the corresponding position in the second list, then when the list of lists specified in the question is sorted, the result should be the following, because the character o evaluates to lesser than the character t, and the character h evaluates to lesser than the character w.

[['o'; 'n'; 'e']; ['t'; 'h'; 'r'; 'e'; 'e']]; ['t'; 'w'; 'o']

Solution provided in book

Confirms my hypothesis:

Lists are compared starting with their first elements. If the elements differ, they are compared, and that is the result of the comparison. If both have the same first element, the second elements are considered, and so on. (144)

Question 6

Combine the sort and insert functions into a single sort function.

My solution

Simply nest the insert function inside sort:

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

let rec isort l =
    let rec insert x l =
        match l with [] -> [x]
        | h::t ->
            if x <= h then x :: h :: t
            else h :: insert x t
    in match l with [] -> []
    | h::t -> insert h (isort t)
    ;;

let _ =
    assert ([] = isort []);
    assert ([0] = isort [0]);
    assert ([0; 1] = isort [0; 1]);
    assert ([0; 1] = isort [1; 0]);
    assert ([0; 1; 2] = isort [2; 1; 0]);
    assert ([0; 1; 2] = isort [2; 0; 1]);
    assert ([0; 1; 2] = isort [1; 0; 2]);
    assert ([0; 1; 2] = isort [1; 2; 0]);
    assert ([2; 6; 9; 19; 53] = isort [53; 9; 2; 6; 19]);
    ;;

Solution provided in book

Identical to mine.

Execute this file

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