4

我正在解决 ocaml 中哈佛 CS 51 编程课程的编程课程。问题是定义一个函数，该函数可以将字符列表压缩为对列表，其中每对包含列表中字符和字符本身的许多后续出现，即在将此函数应用于列表 ['a' ;'a';'a';'a';'a';'b';'b';'b';'c';'d';'d';'d';'d'] 我们应该得到 [(5,'a');(3,'b');(1,'c');(4,'d')] 的列表。我想出了使用辅助函数 go 来解决这个问题的函数：

let to_run_length (lst : char list) : (int*char) list =
  let rec go i s lst1 =
    match lst1 with
      | [] -> [(i,s)]
      | (x::xs) when s <> x ->  (i,s) :: go 0 x lst1
      | (x::xs) -> go (i + 1) s xs
        in match lst with
          | x :: xs -> go 0 x lst
          | [] -> []

我的问题是：是否可以在不定义辅助函数 go 的情况下使用嵌套模式匹配定义递归函数 to_run_length。在这种情况下，我们如何存储已通过元素的计数器状态？

4

2 回答 2

6

您实现的方式to_run_length是正确的、可读的和高效的。这是一个很好的解决方案。（只挑剔：后面的缩进in是错误的）

如果要避免中间函数，则必须改用递归调用返回中的信息。这可以用稍微抽象一点的方式来描述：

  • 空列表的运行长度编码是空列表
  • 列表的运行长度编码x::xs是，
    • 如果运行长度编码以xs开头x，则...
    • 如果不是，则(x,1) ::运行长度编码为xs

（我故意不提供源代码让您了解细节，但不幸的是，这些相对简单的功能没有太多可隐藏的。）

深思：在考虑尾递归和非尾递归函数时，您通常会遇到这种技术（我所做的类似于将 tail-rec 函数转换为非尾递归形式）。在这种特殊情况下，您的原始函数不是尾递归的。当参数/结果流仅“向下”递归调用（您返回它们，而不是重用它们来构建更大的结果）时，函数是尾递归的。在我的函数中，参数/结果流只会“向上”递归调用（调用具有尽可能少的信息，并且所有代码逻辑都是通过检查结果来完成的）。在您的实现中，流既“向下”（整数计数器）又“向上”（编码结果）。

编辑：根据原始海报的要求，这是我的解决方案：

let rec run_length = function
  | [] -> []
  | x::xs ->
    match run_length xs with
      | (n,y)::ys when x = y -> (n+1,x)::ys
      | res -> (1,x)::res
于 2012-10-23T10:11:44.420 回答
0

我认为编写这个函数不是一个好主意。目前的解决方案是好的。

但是，如果您仍然想这样做，您可以使用两种方法之一。

1）不改变你的函数的参数。您可以定义一些顶级可变值，这些值将包含现在在您的辅助函数中使用的累加器。

2）您可以在函数中添加参数来存储一些数据。在搜索延续传递风格时，您可以找到一些示例。

快乐黑客！

PS 我仍然想强调一下，您当前的解决方案是可以的，您不需要改进它！

于 2012-10-23T10:15:03.230 回答