Конкатенация строк в 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 и охватываю три случая: case 1 ничего не возвращает, если список строк пуст; Случай 2 возвращает только голову, если в списке нет хвоста. Хвост три выполняет конкатенацию, одновременно возвращаясь к функции соединения для конкатенации других элементов в списке с разделителем строк между ними. Однако я не уверен, как реализовать это, одновременно возвращаясь к хвосту и уважая потребность OCaml в каждом операторе для вычисления выражения. Это тривиальная проблема в C или Java, но не могу понять это, и любая помощь или указатели приветствуются

Answer 1

Наивный 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

Что более уродливо, но имеет приемлемую сложность по времени.

Answer 2

Для чего бы это ни стоило, я не понимаю, почему вы хотите вести себя иначе, когда заголовок списка - пустая строка.

Вот что делает встроенная функция конкатенации строк для этого случая:

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

Это выглядит довольно разумно для меня, и это такое же поведение, что и для не "" "заголовка списка.

Если вы хотите сделать что-то другое, когда голова "", ваш код не выполняет никакой рекурсии для этого случая. Таким образом, весь вывод будет только один разделитель.

Если вы просто напишите часть else с двумя операциями ^ и рекурсивным вызовом join, вы обнаружите, что код в OCaml так же прост, как в C или Java.