纯文本编辑器的function数据结构
文本编辑器有什么好的纯function数据结构？ 我希望能够将单个字符插入到文本中，并以可接受的效率从文本中删除单个字符，并希望能够保留旧版本，以便轻松地撤消更改。
我应该只使用一个string列表，并重新使用从版本到版本不变的行？
Vector[Vector[Char]]可能是一个不错的select。 这是一个IndexedSeq因此具有体面的更新/ IndexedSeq /更新性能，不像你提到的List 。 如果你看性能特征 ，这是唯一不变的收集提到有效的恒定时间更新。
我不知道这个build议对于“好”的复杂定义是否“好”，但是这很容易和有趣。 我经常设置一个练习来编写Haskell中的文本编辑器的核心，并链接到我提供的渲染代码。 数据模型如下。
首先，我定义一个x元素列表中的光标，光标处的信息有一些typesm 。 （ x会变成Char或String 。）
type Cursor xm = (Bwd x, m, [x])
这Bwd事情就是落后的“狙击名单”。 我想要保持强大的空间直觉，所以我把我的代码中的东西，而不是我的头。 这个想法是，最接近光标的东西是最容易访问的。 这是拉链的精神。
data Bwd x = B0 | Bwd x :< x deriving (Show, Eq)
我提供一个免费的单例types来充当光标的可读标记。
data Here = Here deriving Show
…因此，我可以说是什么在一个String某个地方
type StringCursor = Cursor Char Here
现在，为了表示一个多行的缓冲区，我们需要在游标的上面和下面的String ，以及中间的StringCursor ，我们正在编辑的行。
type TextCursor = Cursor String StringCursor
这个TextCursortypes是我用来表示编辑缓冲区的状态。 这是一个双层拉链。 我向学生提供代码，以便在启用ANSI-escape的shell窗口中的文本上渲染视口，确保视口包含光标。 他们所要做的就是实现更新TextCursor来响应按键的代码。
handleKey :: Key -> TextCursor -> Maybe (Damage, TextCursor)
如果keystroke是无意义的，那么handleKey应该返回Nothing ，但是除此之外， Just提供一个更新的TextCursor和一个“损害报告”，后者是
data Damage = NoChange -- use this if nothing at all happened | PointChanged -- use this if you moved the cursor but kept the text | LineChanged -- use this if you changed text only on the current line | LotsChanged -- use this if you changed text off the current line deriving (Show, Eq, Ord)
（如果您想知道返回Nothing和返回Just (NoChange, ...)之间的区别是Nothing ，请考虑是否还希望编辑器发出嘟嘟声。）损坏报告告诉渲染器需要做多less工作使显示的图像保持最新。
Keytypes仅为可能的按键提供可读的数据表示，从原始ANSI转义序列中抽象出来。 这并不显眼。
我通过提供以下这些工具包为学生提供了一个关于这个数据模型的重要线索：
deactivate :: Cursor x Here -> (Int, [x]) deactivate c = outward 0 c where outward i (B0, Here, xs) = (i, xs) outward i (xz :< x, Here, xs) = outward (i + 1) (xz, Here, x : xs)
deactivatefunction用于将焦点移出Cursor ，给你一个普通的列表，但是告诉你光标在哪里。 相应的activatefunction试图将光标放在列表中的给定位置：
activate :: (Int, [x]) -> Cursor x Here activate (i, xs) = inward i (B0, Here, xs) where inward _ c@(_, Here, []) = c -- we can go no further inward 0 c = c -- we should go no further inward i (xz, Here, x : xs) = inward (i - 1) (xz :< x, Here, xs) -- and on!
我为学生提供了一个故意不正确和不完整的handleKey定义
handleKey :: Key -> TextCursor -> Maybe (Damage, TextCursor) handleKey (CharKey c) (sz, (cz, Here, cs), ss) = Just (LineChanged, (sz, (cz, Here, c : cs), ss)) handleKey _ _ = Nothing
它只是处理普通的字符按键，但却使文字向后出来。 很容易看到字符c出现在Here 。 我邀请他们修复这个bug，并为箭头键，退格键，删除，返回等等添加function。
它可能不是最有效的表示，但它是纯粹的function，使代码具体地符合我们对正在编辑的文本的空间直觉。
我们在Yi中使用了一个文本拉链，这是Haskell中一个严肃的文本编辑器实现。
下面描述不可变状态types的实现，
records/fulltext/local_94979.pdf
records/fulltext/local_72549.pdf
和其他文件。
- Fingertrees
- 罗普斯
- scala.collection.immutable.IndexSeq
我build议使用拉链结合基于手指树的 Data.Sequence.Seq 。 所以你可以把当前状态表示为
data Cursor = Cursor { upLines :: Seq Line , curLine :: CurLine , downLines :: Seq Line }
这给你O（1）复杂的上下移动光标的单行，并且由于splitAt和(><) （union）同时具有O（log（min（n1，n2）））复杂度，所以你会得到O （log（L））复杂度，用于向上/向下跳过L行。
CurLine可以有一个类似的拉链结构来保存游标之前，之后和之后的一系列字符。
Line可能是空间有效的，比如ByteString 。
我为我的vty-ui库实现了一个拉链。 你可以看看这里：
https://github.com/jtdaugherty/vty-ui/blob/master/src/Graphics/Vty/Widgets/TextZipper.hs
Clojure社区正在将RRB树 （Relaxed Radix Balanced）看作是可以高效地连接/切片/插入的数据向量的持久数据结构。
它允许在O（log N）时间内连接，插入索引和拆分操作。
我想象一个专门用于字符数据的RRB树将非常适合大型的“可编辑的”文本数据结构。
想到的可能性是：
-
带有数字索引的“文本”types。 它将文本保存在一个链接的缓冲区列表中（内部表示是UTF16），所以理论上它的计算复杂度通常是链表（例如索引是O（n）），实际上它比传统链接快得多列出你可能只是忘记了n的影响，除非你将整个维基百科存储在你的缓冲区。 试试一百万字符的文字，看看我是否正确（我没有真正做过的事情，顺便说一句）。
-
文本拉链：将光标之后的文本存储在一个文本元素中，将光标之前的文本存储在另一个文本元素中。 将光标传输文本从一侧移到另一侧。
