functional-programming - Ocaml 模式匹配问题

Question

关于 Ocaml 中的模式匹配，我遇到了一些问题。

基本上，我需要编写一个名为 reversed 的函数，它接受一个列表并检查它是否按相反的顺序排列。

至今：

let rec reversed (x:int list):bool =
   match x with
   | [] -> true
   | y::z::tl -> if y < z then false else reversed tl;
   | y::[] -> true;;

有用！（实际上令我惊讶：P）但是我可以看到一个缺陷，即如果没有更多的 tl，它将不匹配。测试这个返回真：

  reversed [5;4;3;1;2];;

这是完全可以理解的，因为没有更多的尾巴，它只是匹配 y::[]

我将如何解决这个问题？

PS：这是我在 Ocaml 的第一天。对不起，如果问题很简单：D

PPS：我故意只使用 Core。（无模块）

PPPS：我理解这种情况，如果我做的事情根本上是错误的，请指出来。

score 4 · Accepted Answer

您的功能中的问题在这里：

| y::z::tl -> if y < z then false else reversed tl;

让我们看看你的清单：[5;4;3;1;2]

它是这样分解的：

| 5::4::[3;1;2]

然后你比较 5 和 4，然后用 [3;2;1] 调用 reverted。这意味着4和3之间的比较没有完成！（您可以尝试使用 [5;4;99;98;97] 之类的列表，这是您得到的意外结果）。

您应该做的是在 z 上进行测试，然后使用列表的其余部分调用 reverted。但是，如果您尝试类似：

| y::z::_ -> if y < z then false else reversed z;

编译器对你大喊大叫，因为 z 是一个 int （不再是一个 int 列表）。为了解决这个问题，您可以通过在 tl 前面添加 z 来“重建”列表：

| y::z::tl -> if y < z then false else reversed (z::tl)

或者在 y （包含 z）之后命名列表，同时仍然提取 z ：

| y::(z::_ as tl) -> if y < z then false else reversed tl

至于你对这个问题的猜测，我理解你的逻辑，但实际上它不是那样工作的。[] 可以在您的分解中“命名”，就像它是一个常规节点一样。

看这个例子，一个（坏的）函数测试是否到达列表的末尾：

let is_end l = match l with | a -> false | [] -> true;;

如果您尝试将其放入口译员中，您应该会收到以下消息： Warning 11: this match case is unused.

那是因为 [] 已经在第一个匹配案例中被捕获。你可以试试is_end []，它返回false。

处理此问题的正确方法是您在代码中的操作方式：

let is_end l = match l with | x::_ -> false | [] -> true;;

score 2 · Accepted Answer

你的程序逻辑是错误的。您想检查列表是否反转（减少？）。但是您的程序在输入时失败

[5;3;4;2;1]

告诉你它是反转/减少的。这是因为你过早地放弃了 3。你的中间子句应该是：

   | y::z::tl -> if y < z then false else reversed (z::tl);

score 1 · Accepted Answer

你应该使用| y::z::tl -> if y < z then false else reversed (z::tl).

如果 y > z，则不应将 z 从下一轮列表中删除，因为 z 尚未与下一个项目进行比较。

你也不需要；在那一行。

正确的代码是

let rec reversed = function
  | [] -> true
  | hd::[] -> true
  | hd1::hd2::tl ->
    if hd1 < hd2 then false
    else reversed (hd2::tl)

score 1 · Accepted Answer

这是使用其他一些概念（如模式保护和通配符）编写它的另一种方法：

let rec reversed = function
  | [] | [_] -> true
  | hd1::hd2::_ when hd1 < hd2 -> false
  | _::tl -> reversed tl;;

这样一来，一种情况为真，一种情况为假，一种情况为递归。

4 回答 4