Существует ли реализация функциональной версии .NET StringBuilder с открытым исходным кодом (не GPL)?

Преимущество StringBuilder над string связано с минимальными ассигнованиями. Он предварительно выделяет буфер, чтобы избежать выделения для каждой вставки/добавления. Это требует изменчивости — какой-то объект должен владеть буфером (и изменять его).

Кстати, System.String уже подходит (насколько я могу судить) под ваше описание: он неизменяем и поддерживает конкатенацию, вставка^MSDN и удаление^MSDN.

ОБНОВИТЬ

Идея Томаса меня заинтриговала. Принимая его идею, вот что я придумал

type StringBuilder =
  private
  | Empty
  | StringBuilder of int * string * int * StringBuilder
  member this.Length =
    match this with 
    | Empty -> 0
    | StringBuilder(_, _, n, _) -> n
  override this.ToString() =
    let rec rev acc = function
      | Empty -> acc
      | StringBuilder(idx, str, _, bldr) -> rev ((idx, str)::acc) bldr
    let buf = ResizeArray(this.Length)
    for idx, str in rev [] this do buf.InsertRange(idx, str)
    System.String(buf.ToArray())

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
[<RequireQualifiedAccess>]
module StringBuilder =
  let empty = Empty
  let length (bldr:StringBuilder) = bldr.Length
  let insert index str bldr = 
    if index < 0 || index > (length bldr) then invalidArg "index" "out of range"
    StringBuilder(index, str, str.Length + bldr.Length, bldr)
  let create str = insert 0 str empty
  let append str bldr = insert (length bldr) str bldr
  let remove index count (bldr:StringBuilder) = create <| bldr.ToString().Remove(index, count)

использование

let bldr = 
  StringBuilder.create "abcdef"
  |> StringBuilder.insert 1 "xyz"
  |> StringBuilder.append "123"
  |> StringBuilder.remove 1 2

bldr.ToString() //azbcdef123

Он постоянный, а вставка - O (1).

Я не знаю ни о какой реализации, которая делала бы именно то, что вы хотите. Однако я не думаю, что вы когда-либо сможете получить сложность O (1) вставки (по произвольному индексу) и сложность O (n) итерации по результатам.

Если вы готовы пожертвовать сложностью вставки, вы можете использовать только string, как предлагает Дэниел. С другой стороны, если вы готовы пожертвовать сложностью toString, вы можете создать неизменяемую структуру данных с вставкой O(1) в любом месте, используя список строк и индексов:

type InsertList = IL of (int * string) list 

// Insert string 'str' at the specified index 
let insertAt idx str (IL items) = IL (idx, str)::items

// Create insert list from a string
let ofString str = IL [str]

Преобразование в строку немного сложнее. Однако я думаю, что вы можете получить сложность O (n log n), используя изменяемый LinkedList и вставляя отдельные символы в нужное место, повторяя вставки с конца. Использование LinkedList будет локализовано до toString, так что структура данных останется чисто функциональной.