OCaml合并排序函数

Question

这是我在OCaml中使用的合并排序函数。有趣的是，代码提供了我所期望的，这意味着，它对列表进行排序。但随后引发了一些错误。那么，请有人检查一下我的代码，告诉我发生了什么，为什么会出现这些错误？我怎样才能消除它们？我是OCaml的新手，但我真的很想知道发生了什么：

(* 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];; 

在终点站，我得到：

        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]
# 

Answer 1

编译器告诉您，您的模式匹配并非详尽无遗。事实上，它确切地告诉我们该如何看待这个问题。例如，您可以尝试：

drop 2 []

要解决这个问题，您需要决定如何处理函数中的空列表。以下是包含详尽匹配的drop的定义：

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

如果这一点不清楚:您的代码没有说明如何处理空列表。如果列表有h :: t表单，则匹配方只会说该做什么。但是一个空的列表没有这个表单。您需要将[]的大小写添加到匹配项中。