4

我有这个函数用于在 ocaml 中反转字符串，但是它说我的类型错误。我不确定为什么或我能做什么:(

任何有关调试的提示也将不胜感激！

  28 let reverse s =
  29   let rec helper i =
  30     if i >= String.length s then "" else (helper (i+1))^(s.[i])
  31   in
  32     helper 0

错误：此表达式的类型为 char，但表达式应为字符串类型

谢谢

4

3 回答 3

9

您的实现没有预期的（线性）时间和空间复杂度：它在时间和空间上都是二次的，因此它几乎不是所请求功能的正确实现。

字符串连接sa^sb分配一个新的 size 字符串length sa + length sb，并用两个字符串填充它；这意味着它的时间和空间复杂度在长度之和中都是线性的。当您对每个字符重复此操作一次时，您将得到一个二次复杂度的算法（分配的内存总大小和副本总数将为1+2+3+....+n）。

要正确实现此算法，您可以：

  • 分配一个预期大小的字符串，并用输入字符串的内容对其进行变异，颠倒

  • 创建一个string list由反向大小为一的字符串组成，然后用于String.concat一次连接所有字符串（分配结果并仅复制字符串一次）

  • 使用Buffer模块，该模块旨在迭代地累积字符或字符串而不会表现出二次行为（它使用动态调整大小策略，增加一个 char 摊销常数时间）

第一种方法既最简单又最快，但其他两种方法在您想要连接字符串的更复杂的应用程序中会变得更有趣，但是一步一步知道最终结果会是什么就不那么简单了。

于 2013-05-09T07:09:35.947 回答
4

我认为错误信息很清楚。该表达式s.[i]表示一个字符（字符串的i第 th 个字符）。但是该^运算符需要字符串作为其参数。

要解决问题，您可以使用String.make 1 s.[i]. 此表达式给出一个包含单个字符的 1 字符字符串s.[i]。

在 OCaml 中以递归方式处理字符串并没有想象中的那么好，因为没有很好的方法来解构字符串（将其分成几部分）。反转列表的等效代码看起来更漂亮。物有所值 ：-）

于 2013-05-09T06:02:35.600 回答
1

您也可以使用 3rd 方库来执行此操作。http://batteries.forge.ocamlcore.org/已经实现了一个反转字符串的函数

于 2013-05-16T10:48:03.810 回答