OCaml中的字符串拼接

Question

我正在编写一个递归的OCaml函数，用于连接字符串列表中的字符串，并通过分隔符在最后一项上不放置分隔符。但我遇到了一些问题。我知道有一个string.concat函数，但我更愿意不使用它，以便了解OCaml如何在幕后执行这些操作。以下是我目前的代码：

let rec join (separator: string) (l: string list) : string =
  begin match l with 
  | []-> ""
  | [hd]-> hd
  | hd::tl-> if hd != "" then hd^separator else ..... 
  end

我正在使用模式匹配来匹配字符串列表l并涵盖三种情况：情况1，如果字符串列表为空，则不返回任何内容；情况2，如果列表中没有尾部，则仅返回头部。尾部三执行连接操作，同时在连接其他项目时递归调用join函数，并在它们之间用字符串分隔符连接。然而，我不确定如何在同时递归尾部和遵守OCaml需要每个语句都求值为表达式的情况下实现这一点。这在C或Java中是一个微不足道的问题，但我无法解决它，非常感谢任何帮助或指针。

- J_code

Answer 1

就我看来，我不明白为什么在列表头部是空字符串的情况下，您想要表现得与平常不同。

以下是针对该情况内置字符串连接函数的操作：

# String.concat "," [""; "yes"];;
- : string = ",yes"

我认为这看起来很合理，与非空列表头的行为相同。

假设您确实想在头部为空时执行某些不同的操作，则您的代码对该情况没有进行任何递归。因此，整个输出将仅是一个分隔符。

如果您只需编写else部分，使用两个^运算符和对join的递归调用，您会发现OCaml中的代码与C或Java一样容易。

- Jeffrey Scofield

---

但是，在同一个else块中如何能够进行递归调用和执行连接操作而不让OCaml抛出类型错误呢？ - J_code

你尝试了什么？像这样的递归调用 join separator tl 是合法的调用，并且它通过递归假设返回一个字符串类型的值。 - Jeffrey Scofield

我其实明白为什么这种递归调用会起作用，因为join接受两个参数。 - J_code

如果您展示出有问题的代码并解释其失败原因，您可能会得到更有用的答案。 - Jeffrey Scofield

Answer 2

一个简单的 join 如下所示：

let rec join separator = function
  | [] -> ""
  | [str] -> str
  | ""::strs -> join separator strs
  | str::strs -> str ^ separator ^ join separator strs

这可以避免不必要的逗号，这似乎是您试图做的。请注意，这不是 `List.concat` 的行为。

对于一个新接触OCaml编程的人来说，这个 `join` 版本虽然合理，但并不可接受：它的执行时间与字符串长度的总和成二次方关系。一个线性时间的实现可能会使用 `Buffer`。

let join separator = function
  | [] -> ""
  | [str] -> str
  | str::strs ->
    let buf = Buffer.create 0 in
    Buffer.add_string buf str;
    List.iter (function
        | "" -> ()
        | s ->
          Buffer.add_string buf separator;
          Buffer.add_string buf s)
      strs;
    Buffer.contents buf

这个算法虽然不太美观，但时间复杂度还是可以接受的。

- gsg