有没有功能版的.NET StringBuilder的开源(非通用公共授权)实现？

Question

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

欢迎对算法的建议。

Answer 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]

向字符串的转换要稍微复杂一些。但是，我认为您可以通过使用可变的LinkedList并在正确的位置插入单个字符，从而获得O( n )的复杂度。LinkedList的使用将本地化到toString，因此数据结构仍然是纯函数的。