时间戳

首页 > 解决方案 > ocaml 中的递归函数和模式匹配

recursion - ocaml 中的递归函数和模式匹配

问题描述

以下代码片段来自 OCaml 官方网站：

# let rec compress = function
| a :: (b :: _ as t) -> if a = b then compress t else a :: compress t
| smaller -> smaller;;
val compress : 'a list -> 'a list = <fun>

上述函数“压缩”具有连续重复元素的列表，例如：

# compress ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];;

- : string list = ["a"; "b"; "c"; "a"; "d"; "e"]

我很想理解上述代码的逻辑。我习惯于命令式地编码，所以这种递归的、函数式的方法，结合 OCamls 简洁但晦涩的语法让我很挣扎。

例如，基本情况在哪里？是smaller -> smaller吗？我知道smaller是一个变量或一个标识符，但它返回的是什么（甚至在 OCaml 中返回正确的术语来说明这里发生的事情）？

我知道 OCaml 中的列表是单链接的，所以我也想知道是否正在生成新列表，或者是否正在剪切现有列表的元素？由于 OCaml 是功能性的，我倾向于认为列表是不可变的——对吗？如果您想更改列表，您基本上需要生成一个新列表，其中包含您要添加的元素（或您要删除的元素）。这是一个正确的理解吗？

标签： recursionfunctional-programmingocaml

解决方案

是的，基本情况是这样的：

| smaller -> smaller

表达式的第一个模式match匹配任何长度为 2 或更大的列表。（最好确保你明白为什么会这样。）

由于 OCaml 按顺序匹配模式，因此基本情况匹配长度为 0 和 1 的列表。这就是程序员选择 name 的原因smaller。他们在想“这是一些较小的清单”。

match 语句的部分通常如下所示：

| pattern -> result

模式中的任何名称都绑定到与模式匹配的值的一部分（如您所说）。所以smaller绑定到整个列表。所以总而言之，第二部分match说如果列表的长度为 0 或 1，结果应该只是列表本身。

OCaml 中的列表是不可变的，因此函数的结果不可能是列表的修改版本。结果是一个新列表，除非该列表已经是一个短列表（长度为 0 或 1）。

所以，你所说的 OCaml 列表的不变性是完全正确的。

推荐阅读