列表反向 Ocaml

Question

我正在创建一个反转列表的函数。我认为一切都很好，但编译器的意见不同...... 这是代码：

let reverse list_ =
 let rec support list_ =
 match list_ with
 | [] -> []
 | hd :: tl -> support tl :: hd in
 let return = support list_ in return

错误是：

| hd :: tl -> support tl :: hd in

Error: This expression has type 'a list
   but an expression was expected of type 'a
   The type variable 'a occurs inside 'a list`

我的想法是到达列表的末尾，然后我将从 [] 添加最新元素构建一个新列表。

Answer 1

运算符::不对称。它在左边有一个列表元素，在右边有一个列表。在这个表达式中：

support tl :: hd

您在左侧有一个列表（递归调用的结果），在右侧有一个列表元素。所以那是行不通的。

Answer 2

错误告诉您 support tl 的类型为 'a list，而 :: 运算符的工作方式如下：1 :: [2;3] = [1;2;3]。从概念上讲，您要尝试做的是 [3; 2] :: 1，这不是运算符的工作方式。

如果要在列表末尾添加 hd，则需要使用 @ 运算符（或 append 函数）：

let reverse list_ =
  let rec support list_ =
    match list_ with
    | [] -> []
    | hd :: tl -> support tl @ [hd] in
  let return = support list_ in return

现在的问题是时间复杂度，我们正在为每个元素遍历整个列表。为了解决这个问题，我们可以使用一个列表来累积元素：

let reverse list =
  let rec support acc list_ =
    match list_ with
    | [] -> acc
    | hd :: tl -> support (hd :: acc) tl in
  let return = support [] list in return

考虑到以下情况，可以稍微重写此代码：

表达式 let return = support [] list in return 与 support [] list
let some_fun some_val = match some_val with (* ... *) 可以写成 let some_fun = function (* ... *) 完全省略 some_val

let reverse list =
  let rec support acc = function
  | [] -> acc
  | hd :: tl -> support (hd :: acc) tl in
  support [] list

我想使用 match 或 function 只是个人喜好问题。

列表反向 Ocaml

List reverse Ocaml

ocaml

functional-programming