f# - .NET StringBuilder 的功能版本是否有开源(非 GPL)实现？

Question

我正在寻找 StringBuilder 或等效物的功能性(如非命令性)实现。我见过几个函数式数组实现，但它们本身不支持插入。开源，非(L？A？)GPL 的奖励，F# 的奖励，但如果需要，我可以从 Haskell/OCaml/SML 进行翻译。

欢迎对算法提出建议。

Answer 1

StringBuilder比string的优势是由于最小化分配。它预先分配一个缓冲区以避免为每个插入/追加分配。这需要可变性——某些对象必须拥有(并改变)缓冲区。

顺便说一句，System.String已经符合(我可以做出的)您的描述:它是不可变的并且支持连接，insertion^MSDN , 和 removal^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)。