OCaml merge sort function

Question

So this is a merge sort function I'm playing with in OCaml. The funny thing is the code delivers what I expect, which means, it sorts the list. But then raises some errors. So can someone please check my code and tell me what's going on and why these errors? And how do I eliminate them? I'm a OCaml newbie but I really want to get what's going on:

(* Merge Sort *)
(* This works but produces some extra error. Consult someone!! *)
let rec length_inner l n =
    match l with
    [] -> n
    | h::t -> length_inner t (n + 1)
;;

let length l = length_inner l 0;;

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
;;

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

msort [53; 9; 2; 6; 19];;

In the terminal, I get:

        OCaml version 4.00.1

# #use "prac.ml";;
val length_inner : 'a list -> int -> int = <fun>
val length : 'a list -> int = <fun>
File "prac.ml", line 13, characters 2-44:
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
val take : int -> 'a list -> 'a list = <fun>
File "prac.ml", line 19, characters 2-39:
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
val drop : int -> 'a list -> 'a list = <fun>
val merge : 'a list -> 'a list -> 'a list = <fun>
val msort : 'a list -> 'a list = <fun>
- : int list = [2; 6; 9; 19; 53]
#

Jeffrey Scofield Jeffrey Scofield · Accepted Answer · 2013-11-15T21:50:52

The compiler is telling you that your pattern matches aren't exhaustive. In fact it's telling exactly what to try to see the problem. For example, you might try:

drop 2 []

To fix the problem you need to decide what to do with empty lists in your functions. Here's a definition of drop with exhaustive matches:

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

If this isn't clear: your code doesn't say what to do with an empty list. Your matches only say what to do if the list has the form h :: t. But an empty list doesn't have this form. You need to add a case for [] to your matches.

OCaml merge sort function

1 Answers