Concatenating strings in OCaml

Question

I'm writing a recursive OCaml function that concatenates strings in a string list joined by a separator without placing a separator on the last item but I'm running into some issues. I know that there's a string.concat function, but I prefer not to use that so as to learn how OCaml performs these operations under the hood. Here is what I have so far:

`

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

`

I'm using pattern matching to match the string list l and cover three cases: case 1 return nothing if the string list is empty; case 2 returns just the head if the list contains no tail. Tail three performs the concatenation while simultaneously recursing on the join function to concatenate the other items in the list with the string separator in between. However I'm unsure as to how to implement this while simultaneously recursing on the tail and paying respect to OCaml's need for every statement to evaluate to an expression. This is a trivial problem in C or Java, but can't figure this out and any help or pointers is appreciated

Answer 1

For what it's worth, I don't see why you want to behave differently when the head of the list is an empty string.

Here's what the built-in string concatenation function does for that case:

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

This looks pretty reasonable to me, and it's the same behavior as for a non-"" list head.

Assuming you do want to do something different when the head is "", your code doesn't do any recursion for that case. So the entire output will be just one separator.

If you just go ahead and write the else part with two uses of the ^ operator and a recursive call to join you should find that the code is just as easy in OCaml as in C or Java.

Answer 2

A naive join is straightforward:

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

This avoids spurious commas, which is what it seems you are trying to do. Note that this is not the behaviour of List.concat.

While a reasonable programming exercise for somebody new to OCaml, this version of join is not acceptable: it does work quadratic in the sum of the lengths of the strings. A linear time implementation might use 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

Which is uglier, but has acceptable time complexity.