如何将整数插入到OCaml中的列表堆中？

Question

运行insert ls n时，应该返回接受ls并插入n的桩列表，以便将n添加到ls中前一个头大于或等于n的第一个桩的头上，或者如果不存在，则在ls末尾添加一个只包含n的新堆。例如,

insert [[4]; [5]] 3 = [[3;4]; [5]]
insert [[2]; [6]] 4 = [[2]; [4;6]]
insert [[3]] 4 = [[3]; [4]]

基本上，如果元素小于列表中的第一个元素，并且在这种情况下，只返回列表的其余部分，我就尝试使用sort助手函数追加到列表中。

let rec insert ls n =
  match n with
    | [] -> [x]
    | y::ys -> if x < y then x::y::ys else y::insert x ys;;

let rec sort n =
  match n with
    | [] -> []
    | x::xs -> insert x (sort xs);;

Answer 1

您一直在混淆insert函数中参数的顺序和类型。在文本描述和示例部分的后面，insert具有'a list list -> 'a -> 'a list list类型，但是当您试图编写insert函数时，可以将元素n与列表匹配。同样，当从insert调用sort时，将元素作为第一个参数传递。

接下来，insert函数将返回一个列表列表，但是在匹配的第一个分支[] -> [x]中，您只返回一个列表。此外，在此匹配或其他任何地方都没有绑定x变量，您可能指的是n。

最后，当您将输入列表的第一个元素与元素n进行比较时，您将比较整个堆，而不是堆的头。

所以让我们试着纠正这些问题，首先，我们必须在ls上而不是n上进行匹配，

let rec insert ls n = 
  match ls with 
(*      ^^
     ls not n! *)

接下来，如果我们有一个空的输入，那么我们需要返回一个包含一堆的列表，其中一堆就是一个列表本身，

  | [] -> [[n]] (* a list containing a list with a single element `n` *)

最后，当我们在输入列表的头上匹配时，我们必须记住，头是列表本身，也就是一堆，所以我们也需要打开它，

  | (x::xs)::ys -> 
 (* ^^^^^^^ 
    here x is the head of the pile, and x::xs is the whole pile *)

打包回去，

if n < x then (n::x::xs)::ys else (x::xs)::insert ys n
(*            ^^^^^^^^^^          ^^^^^^^
             extended pile      intact pile         *)

下一步将是使比赛完成，即，当堆本身是空的时候，想一想该怎么做(会吗？)以及当x等于n时该做什么。