FP作业。是否可以使用嵌套模式匹配而不是辅助函数来定义函数？

Question

我正在用ocaml解决哈佛CS51编程课程的编程问题。问题是定义一个函数，它可以将字符列表压缩成对的列表，其中每个对包含列表中字符和字符本身的若干后续出现，即在将该函数应用于列表'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。在这种情况下，我们如何存储已经传递的元素的计数器状态？

Answer 1

你实现to_run_length的方式是正确的，可读的，高效的。这是一个很好的解决方案。(唯一的吹毛求疵：in后面的缩进是错误的)

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

• 空列表的游程编码是空列表
• 列表x::xs的游程编码是，
  • 如果xs的游程编码以x开始，则...
  • 如果不是，则(x,1) ::的游程编码为xs

的游程编码

​

(我故意不提供源代码来让您了解细节，但不幸的是，对于这些相对简单的函数，没有什么可隐藏的。)

在这种情况下，您的原始函数不是尾递归函数。当参数/结果流只“向下”递归调用(返回它们，而不是重用它们来构建更大的结果)时，函数是尾递归的。在您的实现中，流同时“向下”(整数计数器)和“向上”(编码结果)。

编辑:根据原帖的要求，以下是我的解决方案：

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

Answer 2

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

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

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

2)你可以在你的函数中添加参数来存储一些数据。你可以在谷歌搜索延续传递风格时找到一些例子。

黑客快乐！

附言:我仍然想强调的是，您当前的解决方案是OK的，您不需要改进它！