OCaml合并排序错误？

Question

我正在学习OCaml,它给了我一些问题.我正在尝试实现merge_sort函数,但它在给定代码的第5行上不断给出错误.我只是完全混淆为什么它给我错误,如果有人能启发我,我会非常感激.我甚至不确定我是否正确设置模式匹配(匹配语句),所以如果你能看一下,那真的很有帮助.

let rec merge_sorted (l1:int list) (l2:int list) : int list =
let end_list = [] in
begin match l1, l2 with 
    | [], [] -> end_list
    | h1::t1, h2::t2 -> if h1 < h2 then merge_sorted t1 t2 (h1 :: end_list) else merge_sorted t1 t2 h2::end_list, h1::end_list
end

我得到的错误是:

错误:此函数适用于太多参数,也许您忘记了一个`;' merge_sorted:int list - > int list - > int list

在它说"如果h1 <h2然后merge_sorted t1 t2 ......"的部分

我还想知道是否有学习OCaml语法的地方？我一直在尝试使用Jason Hickey的书,但有些事情并没有深入探讨(例如这种多重/并行模式匹配).我只用Java编写,所以在OCaml中编码对我来说是一个令人沮丧的新体验.

Answer 1

您已声明merge_sorted为类型函数int list -> int list -> int list,或者将两个int列表作为参数并返回另一个int列表的函数.

您遇到的问题是因为您merge_sorted使用三个 int list参数进行调用:

h1::t1, h2::t2 -> if h1 < h2 then merge_sorted t1 t2 (h1 :: end_list) else merge_sorted t1 t2 h2::end_list, h1::end_list

具体来说,merge_sorted t1 t2(h1 :: end_list).您没有为函数定义中的结果列表提供任何条件.

你需要修改你的函数定义,可能是这样的:

let rec merge_sorted l1 l2 results =
  (* code code code *)

关于你的第二个问题,可以在这里找到一套体面的教程.

编辑

回应你的评论 -

首先,::运营商有两个目的.一,它创建了一个新的列表,其中包含一个新的头部和一个现有的尾部 - 1 :: [2]收益[1; 2].其次,它分解现有的列表中匹配模式- match [1; 2] with x :: xs将绑定x到1和y到[2].

要解决这一问题,您的方法中有一些方法可以在Java中正常工作,但在OCaml中根本不起作用.首先,end_list在每次递归调用函数时,您将重新声明为空列表.

其次,因为你的列表连接与你的递归调用在同一行上merge_sorted,编译器将(别无选择)认为你正在指定第三个函数调用.你可能意味着:

h1::t1, h2::t2 -> if h1 < h2 then
                      merge_sorted t1 t2
                      h1 :: end_list
                  else
                      merge_sorted t1 t2
                      h2 :: end_list
                      h1 :: end_list

但!这不是你的解决方案,请继续阅读.

第三,更重要的是,OCaml不会这样工作.默认情况下,OCaml列表(实际上所有变量)都是不可变的 - 也就是说,一旦将值绑定到1,就无法更改它.当你说(h1 :: end_list)时,你没有改变结束列表; 你真正在做的是创建一个新的列表,其中h1为头,end_list为尾.因为你把这一切都放在同一行上,所以编译器认为你merge_sorted(t1, t2, new List(h1, end_list))在你所定义的Java-land中做了相同的操作merge_sorted(List t1, List t2).

由于您无法就地修改列表,因此此条带的函数式语言具有不同的列表处理惯用语.在这种情况下,大多数函数式程序员都会定义其函数以获取额外的累加器参数.例如:

let rec map f data acc =
    match data with
    | []      -> List.rev acc
    | x :: xs -> map f xs ((f x) :: acc);;

map (fun x -> x + 1) [1; 2; 3;] [];;  (* yields [2; 3; 4] *)

这是规范map函数,它接受列表和函数,将列表中的每个项目应用于该函数,并返回包含结果的新列表.正如你所看到的,在应用的每个项目的结果data,以f存储在acc和结果传递给下一个呼叫,只有当要返回data为空.通过这种方式,我们可以实现一系列列表修改,而无需改变变量.

如果您不喜欢函数签名中的额外参数,可以将其隐藏在嵌套函数中,如下所示:

let map f data =
    let rec loop d acc =
        match d with
        | []      -> List.rev acc
        | x :: xs -> loop xs ((f x) :: acc)
    in
        loop data []

我希望这对你有意义 - 从命令式转变为功能性习语可能真正让人心旷神色,对于那些刚接触它的人来说,不变性似乎是一种残酷和随意的限制 - 我保证函数式编程的好处和美感将会体现出来如果你坚持下去,你自己!