algorithm - 计划生育作业。是否可以使用嵌套模式匹配而不是辅助函数来定义函数？

Question

我正在用 ocaml 解决哈佛 CS 51 编程类(class)的编程问题。问题是定义一个函数，该函数可以将字符列表压缩为对列表，其中每对包含列表中字符和字符本身的多个后续出现，即在将此函数应用于列表 ['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