如何计算字符列表中重复出现的字符数？

Question

我的目标是获取如下字符列表：

['a'; 'a'; 'a'; 'a'; 'a'; 'b'; 'b'; 'b'; 'a'; 'd'; 'd'; 'd'; 'd']

计算重复字符的数量并将其转换为这样的 (int * char) 列表：

[(5, 'a'); (3, 'b'); (1, 'a'); (4, 'd')]

我完全迷路了，而且对 OCaml 也非常陌生。这是我的代码：

let to_run_length (lst : char list) : (int * char) list =
  match lst with
  | [] -> []
  | h :: t -> 
    let count = int 0 in
    while t <> [] do
      if h = t then
        count := count + 1;
    done;

我正在努力研究如何检查列表，就像检查 C 或 Python 中的数组一样。我不允许使用折叠函数或地图或类似的东西。

编辑：更新代码，在 List.nth 上产生异常：

let rec to_run_length (lst : char list) : (int * char) list =
  let n = ref 0 in
  match lst with
  | [] -> []
  | h :: t -> 
    if h = List.nth t 0 then n := !n + 1 ;
              (!n, h) :: to_run_length t ;;

编辑：添加嵌套匹配导致函数不起作用...但没有错误！

let rec to_run_length (lst : char list) : (int * char) list =
  match lst with
  | [] -> []
  | h :: t -> 
    match to_run_length t with
    | [] -> []
    | (n, c) :: tail -> 
      if h <> c then to_run_length t
      else (n + 1, c) :: tail ;;

最终编辑：终于得到代码运行完美！

let rec to_run_length (lst : char list) : (int * char) list =
  match lst with
  | [] -> []
  | h :: t -> 
    match to_run_length t with
    | (n, c) :: tail when h = c -> (n + 1, h) :: tail
    | tail -> (1, h) :: tail ;;

Answer 1

回答您问题的一种方法是指出 OCaml 中的列表不像 C 或 Python 中的数组。没有（恒定时间）方法可以像数组一样索引 OCaml 列表。

如果你想以命令式风格编码，你可以像 C 中的 list 一样对待 OCaml 列表，即，可以从一个方向遍历的链接结构从头到尾。

要完成这项工作，您确实需要一个 while 语句，该语句仅在列表非空时才继续。在每一步中，您都检查列表的头部并相应地更新您的输出。然后用列表的尾部替换列表。

为此，您可能希望使用引用来保存输入和输出。（作为旁注，在你有 int 0 的地方，你几乎肯定想要 ref 0。也就是说，你想使用一个引用。没有名为 int 的预定义 OCaml 函数或运算符。）

然而，学习OCaml的通常原因是学习函数式风格。在那种情况下，你应该考虑一个递归函数来计算你想要的值。

为此，您需要一个基本案例和一种将非基本案例简化为可以递归求解的较小案例的方法。一个很好的基本案例是一个空列表。此输入的所需输出（大概）也是一个空列表。

现在假设（通过递归假设）你有一个有效的函数，并且给你一个非空列表。您可以在列表的尾部调用您的函数，它（根据假设）为您提供尾部的运行长度编码版本。您需要对这个结果做什么才能在前面再添加一个字符？这就是你必须弄清楚的。

更新

如您所说，您的代码越来越近了。

你需要问问自己如何在编码值的开头添加一个新字符。在你的代码中你有这个，例如：

. . .
match to_run_length t with
| [] -> []
. . .

如果尾部为空，这表示 return 一个空编码。但这没有意义。您知道输入中有一个字符（即 h）。您应该 returning 某种包含 h.

的结果

一般来说，如果 returned 列表以 h 开头，您希望将第一组的计数加 1。否则，您想将一个新组添加到 returned 列表的前面。

如何计算字符列表中重复出现的字符数？

How to count the number of recurring character repetitions in a char list?

ocaml