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

Question

我正在为ocaml中的Harvard CS 51编程课程解决编程方面的问题.问题是定义一个函数,它可以将字符列表压缩为对列表,其中每对包含列表中字符和字符本身的许多后续发生,即在将此函数应用于列表['a'之后;'a';'a';'a';'a';'b';'b';'b';'c';'d';'d';'d';'d']我们应该得到[(5,'a');(3,'b');(1,'c');(4,'d')]的列表.我想出了使用辅助功能的功能去解决这个问题:

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
          | [] -> []

我的问题是:是否可以使用嵌套模式匹配定义递归函数to_run_length,而无需定义辅助函数go.在这种情况下,我们如何存储已传递元素的计数器状态？

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