在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仅返回头部。尾部3执行连接，同时在连接函数上递归以连接列表中的其他项目，中间使用字符串分隔符。但是，我不确定如何实现这一点，同时在尾部递归并尊重OCaml对每个语句评估表达式的需求。这在C或Java中是一个微不足道的问题，但无法弄清楚这一点，任何帮助或指针都表示赞赏

Answer 1

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

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

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

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

假设你想要在头部为“”时做一些不同的事情，那么你的代码不会对那种情况做任何递归。所以整个输出只是一个分隔符。

如果你继续编写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 rec 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

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