在 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 中的一个微不足道的问题，但无法弄清楚这一点，任何帮助或指针表示赞赏

Answer 1

对于它的价值，当列表的头部是一个空字符串时，我不明白为什么你想要表现不同。

下面是内置字符串连接函数在这种情况下的作用：

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

这对我来说看起来很合理，它与非“”列表头的行为相同。

假设您确实想在 head 为 "" 时做一些不同的事情，那么您的代码不会对这种情况进行任何递归。所以整个输出将只是一个分隔符。

如果您继续编写else使用^运算符的两次使用和对join您的递归调用的部分，您应该会发现 OCaml 中的代码与 C 或 Java 中的代码一样简单。

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

哪个更难看，但时间复杂度可以接受。